举例说明:
你有一张美国每个名字的名单。
您想在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)