举例说明:
你有一张美国每个名字的名单。
您想在gui中自动建议完成。
很明显,要做的是使用基数树来获取给定前缀的名称列表。然而,这并没有考虑到频率信息。所以,我不想让前5个结果成为第一个词法结果,而是希望得到最常见的5个名称:
例如,前缀dan

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

有没有我错过的trie树算法?当然,理想的实现(如果有的话)是在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).

我们还有几天的悬赏时间,所以我还在寻找解决办法。因为这不仅仅是减少,而且是查找方面的问题。

最佳答案

是的,我们可以用试纸。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)

10-05 21:20
查看更多