在长的排序字符串列表中用Python快速查找'startswith'子串的方法

Question

我在网上查了很多资料，但还是没找到合适的东西，所以如果我搜索的方向错了，真的很抱歉。

我正在为麻省理工学院的编程入门课程，第五次作业写一个鬼游戏的实现。

在这个过程中，我需要判断一串字符是否是任何有效单词的开头。我有一个有效单词的列表（“wordlist”）。

更新：我可以使用一些方法，每次都遍历这个列表，比如彼得的简单建议：

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为空就算输。之所以这样做，是因为我（错误地，见下文）认为这样可以节省时间，因为后续的查找只需要在更小的列表中搜索。

但我意识到，这样做是要检查原始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

但速度差不多，我想这可能是因为列表推导式运行时像编译过的代码？

接着我想，可能更有效的方式是用某种形式的二分查找来找到匹配单词的块。这是正确的方向吗，还是我漏掉了什么明显的东西？

显然在这种情况下这并不是大问题，但我刚开始学习编程，想把事情做好。

更新：

我已经用下面的建议测试了一个简单的测试脚本。虽然彼得的二分查找/插入法在单次运行中显然更好，但我想知道缩小列表是否在一系列片段中会更胜一筹。结果并没有：

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

创建第二个列表等的开销显然花费了比搜索更长列表更多的时间。回想起来，这可能是最好的方法，因为“缩小列表”的方法反而增加了第一次运行的时间，这正是最糟糕的情况。

感谢大家提供的优秀建议，彼得的回答真是太棒了！！！

Answer 1

正如彼得所建议的，我会使用Bisect模块。特别是当你需要从一个很大的单词文件中读取数据时。

如果你真的需要速度，可以创建一个守护进程（如何在Python中创建守护进程？），它会有一个为这个任务准备好的预处理数据结构。

我建议你可以使用“前缀树”。

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

有很多算法和数据结构可以用来索引和搜索文本中的字符串，其中一些已经包含在标准库中，但并不是所有的；前缀树就是一个很好的例子，它并不在标准库里。

假设“word”是一个单独的字符串，而“dictionary”是一个很大的单词集合。如果我们有一个字典，并且需要知道某个单词是否在字典中，前缀树是一种可以帮助我们的数据结构。但是你可能会问：“如果集合和哈希表也能做到这一点，为什么还要用前缀树呢？”主要有两个原因：

• 前缀树可以在O(L)的时间内插入和查找字符串（L代表单个单词的长度）。这比集合要快得多，而且比哈希表也快一点。
• 集合和哈希表只能找到与我们要查找的单词完全匹配的字典中的单词；而前缀树允许我们找到只有一个字符不同、共享前缀、缺少一个字符等的单词。

前缀树在TopCoder的问题中很有用，但在软件工程中也有很多应用。例如，考虑一下网页浏览器。你知道网页浏览器是如何自动完成你的文本或给你展示很多可能的文本选项的吗？没错，使用前缀树可以做到这一点，非常快。你知道拼写检查器是如何检查你输入的每个单词是否在字典中的吗？同样也是前缀树。你还可以用前缀树来建议文本中存在但不在字典中的单词的纠正。

一个例子是：

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']，这就是你想要的所有单词。

要构建它，你可以遍历你的单词列表，对于每个单词，遍历字符，在需要的地方添加一个新的默认字典。

Answer 2

你说得对，因为这个列表是排好序的，所以可以更有效地处理。

我在@Peter的回答基础上继续讲，Peter的回答是返回一个单独的元素。我注意到你想要的是所有以特定前缀开头的单词。下面是实现的方法：

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

这个方法会返回你原始排序列表中的一部分。

Answer 3

生成器表达式是懒惰评估的，这意味着如果你只想判断一个单词是否有效，我认为下面的方式会更高效，因为它在找到匹配项后不一定会强制构建完整的列表：

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'），那么你给出的例子可能就不太好用了，因为在这种情况下，它可能会花费大部分时间来组装一个有效单词的大列表，而仅仅进行部分扫描所带来的好处几乎可以忽略不计。很难确定，但这有点学术，因为二分查找反正更好。