python - 自动完成样式前缀查找

Question

做一个具体的例子:

• 您有一份美国所有名字的列表。
• 您想在 GUI 中自动提示完成。

显而易见的事情是使用基数树来获取给定前缀的名称列表。但是，这没有考虑频率信息。因此，我想要最常见的 5 个名字，而不是仅仅让前 5 个结果成为第一个词汇结果:

例如对于前缀 dan

 (5913, 'Daniel')
 (889, 'Danny')
 (820, 'Dana')
 (272, 'Dan')
 (60, 'Dane')

是否有我错过的特里树算法？当然，在我看来，理想的实现(如果存在的话)是在 python 中。

更新: 总体上对 Paddy3113 提出的建议感到满意，但我会说当我向它提供 2.6GB 的文件时它会完全崩溃，这是我正在减少的文件之一。查看输出的细节可以提供一些见解:

samz;Samzetta|Samzara|Samzie
samza;Samzara
samzar;Samzara
samzara;Samzara
samze;Samzetta
samzet;Samzetta
samzett;Samzetta
samzetta;Samzetta
samzi;Samzie
samzie;Samzie

# Format - PREFIX;"|".join(CHOICES).

我们在悬赏方面还有几天的时间，所以我仍在寻找 killer 级解决方案。因为这不仅涉及减少，还涉及事物的查找方面。

Answer 1

是的，我们可以使用 trie。 trie 节点的最常见名称是 (1) 该 trie 节点处的名称或 (2) trie 节点的子节点的最常见名称。这是一些可以玩的 Python 代码。

from collections import defaultdict


class trie:
    __slots__ = ('children', 'freq', 'name', 'top5')

    def __init__(self):
        self.children = defaultdict(trie)
        self.freq = 0
        self.name = None
        self.top5 = []

    def __getitem__(self, suffix):
        node = self
        for letter in suffix:
            node = node.children[letter]
        return node

    def computetop5(self):
        candidates = []
        for letter, child in self.children.items():
            child.computetop5()
            candidates.extend(child.top5)
        if self.name is not None:
            candidates.append((self.freq, self.name))
        candidates.sort(reverse=True)
        self.top5 = candidates[:5]

    def insert(self, freq, name):
        node = self[name]
        node.freq += freq
        node.name = name


root = trie()
with open('letter_s.txt') as f:
    for line in f:
        freq, name = line.split(None, 1)
        root.insert(int(freq.strip()), name.strip())
root.computetop5()
print(root['St'].top5)