使用Python快速生成自动填充建议

我有一套约为650万字的集all_words。如何使用Python快速生成以给定字符串开头的单词列表？使用Python快速生成自动填充建议

很显然，我可以这样做

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

这工作，但它需要一秒钟的量级。什么是更快的方式来生成完整列表？

来源

2014-03-24 ramcdougal

我想这种问题最快和最节省空间的数据结构是使用prefix tree。在将您的单词集合解析到树中之后，查找时间应该非常快。那里似乎甚至有一个python implementation。

来源

2014-03-24 18:33:40

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

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

来源

2014-03-24 16:37:37

这是网络服务后端的一部分。我想尽快呈现完整的结果。 – ramcdougal

的一个快速方法是由第一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)

，然后用它来寻找完井：

def completions(word): 
    ell = len(word) 
    return set(w for w in words_by_first3[word[:3]] if w[: ell] == word)

在我的情况下，这给出了结果非常快，但它使用了大量的内存。

来源

2014-03-24 16:42:59 ramcdougal

内存问题不是一个绝对的交易断路器，但我真的更喜欢更友善的内存解决方案。 – ramcdougal

第一个代码块可以通过'words_by_first3 = defaultdict（set）来简化。 word_set：word_by_first3 [word [：3]] .add（word）' –

使用Python快速生成自动填充建议

回答

相关问题