使用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]

这个方法可以工作，但需要大约一秒钟的时间。有没有更快的方法来生成完整列表？

- ramcdougal

Answer 1

我想对于这种问题，最快和空间效率最高的数据结构应该是使用前缀树。当单词集合被解析成树形结构后，查找时间应该非常快速。甚至有一个Python实现似乎已经存在了。

- Bas Swinckels

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) 

然后使用此功能查找完成内容：

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

在我的情况下，这样可以很快地得出结果，但它会使用大量的内存。

- ramcdougal

---

内存问题不是绝对的绊脚石，但我真的更喜欢一个更友好的内存解决方案。 - ramcdougal

第一个代码块可以简化为words_by_first3 = defaultdict(set); for word in word_set: words_by_first3[word[:3]].add(word)。 - Bas Swinckels

Answer 3

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

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

- Alagappan Ramu

---

这是 Web 服务后端的一部分。我希望尽快呈现完整的结果。 - ramcdougal

Answer 4

如果你的数据集比较小，暴力线性搜索不会太糟糕。然而，对于大型数据集（就像在这种情况下），你很快就会遇到内存和速度限制。

正如其他答案所提到的，用于此目的的最佳数据结构是 Trie -- 它将允许您有效地进行前缀搜索。

然而，在纯 Python 中实现一个内存高效的 Trie 很困难（特别是如果您想支持更新）。如果您不介意使用通过 Python 客户端访问的外部进程，您可以使用 Typesense：https://github.com/typesense/typesense

- jeffreyveon

---

它真的能够实现搜索词建议吗？我在API或文档中找不到任何提及此事的内容。如何实现？ - vladimir.gorea

我猜你想要从用户查询日志中索引搜索词，并将其作为自动完成建议进行搜索？还是你想从现有数据（如标题）生成合成的搜索词建议？ - jeffreyveon

我正在寻找从现有数据中生成术语建议的方法，这在 Elasticsearch 中很容易实现。 - vladimir.gorea

Answer 5

您可能想要查看我开源的一个库：https://github.com/seperman/fast-autocomplete

它非常易于使用：

>>> from fast_autocomplete import AutoComplete
>>> words = {'book': {}, 'burrito': {}, 'pizza': {}, 'pasta':{}}
>>> autocomplete = AutoComplete(words=words)
>>> autocomplete.search(word='b', max_cost=3, size=3)
[['book'], ['burrito']]
>>> autocomplete.search(word='bu', max_cost=3, size=3)
[['burrito']]
>>> autocomplete.search(word='barrito', max_cost=3, size=3)  # mis-spelling
[['burrito']]

- Seperman