在Python中，查找长排序字符串列表中以特定子字符串开头的最快方法是什么？

Question

我已经进行了很多谷歌搜索，但是没有找到任何东西，所以如果我只是在搜索错误的东西，我真的很抱歉。

我正在编写MIT编程导论第5次作业的Ghost实现。

作为其中的一部分，我需要确定一个字符字符串是否是任何有效单词的开头。我有一个有效单词列表（"wordlist"）。

更新：我可以使用一些每次都会遍历列表的东西，例如Peter的简单建议：

def word_exists(wordlist, word_fragment):
return any(w.startswith(word_fragment) for w in wordlist)

我之前有：

wordlist = [w for w in wordlist if w.startswith(word_fragment)]

(来自这里)将列表缩小为以该片段开头的有效单词列表，并且如果wordlist为空，则认为是损失。我采取这种方法的原因是，我（错误地，请参见下文）认为这样可以节省时间，因为随后的查找只需要在较小的列表中搜索。

我意识到，这是在检查原始单词列表（38,000个左右的单词）中的每个项目的开头。当wordlist有序时，这似乎很愚蠢，并且理解可以在遇到单词片段之后停止。我尝试了这个：

newlist = []
for w in wordlist:
    if w[:len(word_fragment)] > word_fragment:
        # Take advantage of the fact that the list is sorted
        break
    if w.startswith(word_fragment):
        newlist.append(w)
return newlist

但是我认为这大约是因为列表理解作为编译代码运行的缘故，速度差不多？

然后我想，更有效的方法可能是在列表中使用某种形式的二分查找来查找匹配单词的块。这是正确的方法吗，还是我漏掉了什么非常明显的东西？

显然，在这种情况下并不是真正的大问题，但我刚开始学习编程，希望做好每一件事。

更新：

我已经用简单测试脚本测试了以下建议。虽然Peter的二分搜索/ bisect在单次运行中显然更好，但我对缩小列表是否会在一系列片段中获胜感兴趣。实际上，它没有：

The totals for all strings "p", "py", "pyt", "pyth", "pytho" are as follows:
In total, Peter's simple test took 0.175472736359
In total, Peter's bisect left test took 9.36985015869e-05
In total, the list comprehension took 0.0499348640442
In total, Neil G's bisect took 0.000373601913452

创建第二个列表等操作的开销显然比搜索更长的列表花费更多时间。事后看来，这可能是最好的方法，因为“减少列表”的方法增加了第一次运行的时间，这是最坏的情况。

感谢大家提供的出色建议，Peter做出了最佳答案，干得好！

- Hooloovoo

---

二分查找在这里如何帮助？ - Senthil Kumaran

感谢您的评论，Senthil。请查看下面对您评论的回答。列表的线性搜索需要线性时间，而二分搜索只需要log(n)时间。这在像我的长单词列表中显然会产生巨大的差异。 - Hooloovoo

Answer 1

生成器表达式是惰性求值的，因此如果您只需要确定单词是否有效，我希望以下内容更加高效，因为它不一定会强制构建完整列表一旦找到匹配项：

def word_exists(wordlist, word_fragment):
    return any(w.startswith(word_fragment) for w in wordlist)

请注意，缺少方括号对于此操作很重要。

然而，在最坏情况下，这仍然是线性的。你是正确的，二分查找会更有效率；你可以使用内置的“bisect”模块进行操作。它可能看起来像这样：

from bisect import bisect_left
def word_exists(wordlist, word_fragment):
    try:
        return wordlist[bisect_left(wordlist, word_fragment)].startswith(word_fragment)
    except IndexError:
        return False # word_fragment is greater than all entries in wordlist

bisect_left 的时间复杂度为 O(log(n))，因此对于大型单词列表来说速度会更快。编辑：如果你的单词片段非常常见（比如 't'），那么你给出的例子可能会失去优势，因为它可能会花费大量时间来组装一个有效单词的大列表，并且只需要对列表进行部分扫描所获得的收益微不足道。虽然很难确定，但这有点学术性，因为二分查找无论如何都更好。

- Peter

---

你的第一个例子实际上不是列表推导式，而是生成器表达式，这是两个不同的概念。你应该更明确地说明这一点。 - Ant

此外，您可以使用 any 代替 True in …。 - Neil G

谢谢，我已经适当地更新了。我有一种感觉，应该有比“True in ...”更清晰的方法，但我无法清楚地表达出来以便进行搜索。 - Peter

eyquem：你不需要这样做 :) 他对问题的描述只是说他需要知道列表是否为空，目前他正在通过构建一个列表并查看它是否为空来实现。链接到“Ghost”游戏的描述似乎也不需要完整的单词列表。 - Peter

@Peter 是的，他写道：“我需要确定一个字符串是否是有效单词列表（“wordlist”）中任何有效单词的开头”，但这是为了描述在约简“wordlist”的推导列表中的条件**if w.startswith(word_fragment)**，这个条件明确地被称为“作为一部分”。问题是要知道Hooloowoo是否真的想要遵循其他帖子中给出的相同算法，还是他编写的游戏遵循另一种算法，其中他只需要得到一个True/False答案，你的解决方案非常好。 - eyquem

Answer 2

考虑到列表已排序，因此您可以更有效地完成此操作。

我在@Peter的回答基础上继续建设，他返回一个单一元素。我知道您想要以给定前缀开头的所有单词。以下是如何实现：

from bisect import bisect_left
wordlist[bisect_left(wordlist, word_fragment):
         bisect_left(wordlist, word_fragment[:-1] + chr(ord(word_fragment[-1])+1))]

这将返回您原始已排序列表的切片。

- Neil G

---

不，它并没有——我一开始就想过这个了。尝试使用wordlist = [ 'abcd'，'abce'，'abcf']和word_fragment ='abc'——bisect_left和bisect_right都返回0。 - Peter

@Neil G 这并没有返回以 word_fragment 开头的单词切片。如果在 wordlist 中存在，这将返回 word_fragment 的单词切片。 - eyquem

Answer 3

正如Peter建议的那样，我会使用Bisect模块。特别是当你从一个大文件中读取单词时。

如果你真的需要速度，你可以创建一个守护进程（如何在Python中创建守护进程？），该进程具有适合该任务的预处理数据结构。

我建议你可以使用“tries”。

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries

有许多算法和数据结构可以索引和搜索文本中的字符串，其中一些包含在标准库中，但并非全部；trie 数据结构是一个很好的例子。

假设 word 是单个字符串，dictionary 是一个大型词汇集。如果我们有一个 dictionary，并且需要知道单个 word 是否在 dictionary 中，则 trie 是一种可以帮助我们的数据结构。但您可能会问自己，“为什么使用 trie，如果 set 和哈希表可以做到同样的事情？”有两个主要原因：

- trie 可以在 O(L) 时间内插入和查找字符串（其中 L 表示单个单词的长度）。这比 set 快得多，但比哈希表略快。 - set 和哈希表只能在字典中查找与我们正在查找的单个单词完全匹配的单词；trie 允许我们查找具有单个字符不同、共同前缀、缺少字符等的单词。

Trie 在 TopCoder 问题中可能很有用，但在软件工程中也有许多应用。例如，考虑一个 Web 浏览器。您知道 Web 浏览器如何自动完成您的文本或显示您可能正在编写的文本的许多可能性吗？是的，使用 trie 您可以非常快速地实现。您知道拼写检查器如何检查您输入的每个单词是否在字典中吗？再次是 trie。您还可以使用 trie 来建议对文本中存在但不在字典中的单词进行更正。

一个例子是：

start={'a':nodea,'b':nodeb,'c':nodec...}
nodea={'a':nodeaa,'b':nodeab,'c':nodeac...}
nodeb={'a':nodeba,'b':nodebb,'c':nodebc...}
etc..

如果你想要以ab开头的所有单词，你只需要遍历start['a']['b']，那就是你想要的所有单词。

要构建它，你可以遍历你的单词列表，对于每个单词，迭代字符并在必要时添加一个新的默认字典。

- Rusty Rob

Answer 4

如果使用二分查找（假设单词列表已排序），我正在考虑以下内容：

wordlist = "ab", "abc", "bc", "bcf", "bct", "cft", "k", "l", "m"
fragment = "bc"
a, m, b = 0, 0, len(wordlist)-1
iterations = 0

while True:
    if (a + b) / 2 == m: break # endless loop = nothing found
    m = (a + b) / 2
    iterations += 1
    if wordlist[m].startswith(fragment): break # found word
    if wordlist[m] > fragment >= wordlist[a]: a, b = a, m
    elif wordlist[b] >= fragment >= wordlist[m]: a, b = m, b

if wordlist[m].startswith(fragment):
    print wordlist[m], iterations
else:
    print "Not found", iterations

它将找到一个匹配的单词，或者没有。然后你需要在它左右寻找其他匹配的单词。我的算法可能不正确，这只是我想法的粗略版本。

- Andrey Kuzmin

---

这基本上与Peter建议使用bisect相同，只是我不知道存在这样的模块。使用bisect比我的建议更好、更干净。 - Andrey Kuzmin

Answer 5

这是我最快的方法，将列表wordlist缩小到以给定片段开头的有效单词列表： sect()是一个生成器函数，它使用了优秀的Peter的想法来使用和islice()函数：

from bisect import bisect_left
from itertools import islice

from time import clock

A,B = [],[]


iterations = 5
repetition = 10

with open('words.txt') as f:
    wordlist = f.read().split()

wordlist.sort()
print 'wordlist[0:10]==',wordlist[0:10]


def sect(wordlist,word_fragment):
    lgth = len(word_fragment)
    for w in islice(wordlist,bisect_left(wordlist, word_fragment),None):
        if w[0:lgth]==word_fragment:
            yield w
        else:
            break


def hooloo(wordlist,word_fragment):
    usque = len(word_fragment)
    for w in wordlist:
        if w[:usque] > word_fragment:
            break
        if w.startswith(word_fragment):
            yield w


for rep in xrange(repetition):
    te = clock()
    for i in xrange(iterations):
        newlistA = list(sect(wordlist,'VEST'))
    A.append(clock()-te)

    te = clock()
    for i in xrange(iterations):
        newlistB = list(hooloo(wordlist,'VEST'))
    B.append(clock() - te)


print '\niterations =',iterations,'   number of tries:',repetition,'\n'
print newlistA,'\n',min(A),'\n'
print newlistB,'\n',min(B),'\n'

结果

wordlist[0:10]== ['AA', 'AAH', 'AAHED', 'AAHING', 'AAHS', 'AAL', 'AALII', 'AALIIS', 'AALS', 'AARDVARK']

iterations = 5    number of tries: 30 

['VEST', 'VESTA', 'VESTAL', 'VESTALLY', 'VESTALS', 'VESTAS', 'VESTED', 'VESTEE', 'VESTEES', 'VESTIARY', 'VESTIGE', 'VESTIGES', 'VESTIGIA', 'VESTING', 'VESTINGS', 'VESTLESS', 'VESTLIKE', 'VESTMENT', 'VESTRAL', 'VESTRIES', 'VESTRY', 'VESTS', 'VESTURAL', 'VESTURE', 'VESTURED', 'VESTURES'] 
0.0286089433154 

['VEST', 'VESTA', 'VESTAL', 'VESTALLY', 'VESTALS', 'VESTAS', 'VESTED', 'VESTEE', 'VESTEES', 'VESTIARY', 'VESTIGE', 'VESTIGES', 'VESTIGIA', 'VESTING', 'VESTINGS', 'VESTLESS', 'VESTLIKE', 'VESTMENT', 'VESTRAL', 'VESTRIES', 'VESTRY', 'VESTS', 'VESTURAL', 'VESTURE', 'VESTURED', 'VESTURES'] 
0.415578236899

sect()比holloo()快14.5倍。

附：

我知道有timeit，但是在这种情况下，clock()已经足够了。

- eyquem

Answer 6

在列表中进行二分查找并不能保证你什么。我也不确定那该如何工作。

你有一个被排序的列表，这是个好消息。无论哪种情况，算法性能复杂度是O(n)，这并不差，你只需要遍历整个单词列表一次即可。

但在第二种情况下，性能（工程性能）应该更好，因为你在找到剩余情况不适用时就停止循环。尝试使用一个1号元素匹配，而其余38000-1个元素不匹配的列表，你会发现第二个将会战胜第一个。

- Senthil Kumaran

---

假设列表中每个单词的匹配概率为1/1000，那么在没有使用二分查找的情况下，您预计平均要检查几百个单词。而使用二分查找，您预计只需进行约log(n)次检查（我假设n>>1000）。 - Rusty Rob