使用Python快速生成自动完成建议

Question

我有一套大约650万字的all_words。如何使用Python快速生成以给定字符串开头的单词列表？在

很明显，我可以做一些

def completions(word_start):
    ell = len(word_start)
    return [w for w in all_words if w[: ell] == word_start]

这是可行的，但它需要一秒钟的时间。生成完整列表的更快方法是什么？在

Answer 1

您可以使用Python生成器（https://wiki.python.org/moin/Generators）。在

你不必在开始使用它们之前生成所有的单词。假设您有一个按字典顺序排序的列表，您可以获取最初的几个结果并开始使用它们。并“按需”获得更多结果。在

Answer 2

一种快速的方法是通过第一个n字符预索引：

words_by_first3 = {}
for word in word_set:
    first3 = word[:3]
    if first3 not in words_by_first3:
        words_by_first3[first3] = set()
    words_by_first3[first3].add(word) 

然后用它来找到补全：

^{2}$

在我的例子中，这会很快给出结果，但它会占用大量内存。在

Answer 3

我想对于这类问题，最快和最节省空间的数据结构是使用prefix tree。将单词集合解析到树中之后，查找时间应该很快。似乎还有一个python implementation。在