使用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快速生成自動填充建議

回答

相關問題