4

做一个具体的例子：

  • 你有一个美国每个名字的列表。
  • 您想在 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).

我们在赏金方面还有几天的时间，所以我仍在寻找杀手级解决方案。因为这不仅与减少有关，还与事物的查找有关。

4

5 回答 5

4

是的，我们可以使用 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)
于 2012-05-30T13:59:34.487 回答
2

对调整没有任何想法，我首先假设我有一个名称及其频率列表，然后构造一个字典，将前缀映射到具有该前缀的一组名称，然后将每个集合转换为仅包含前 5 个名称的列表频率。

使用从这里推导出来的男孩名字列表来创建一个文本文件，其中每一行都是一个整数出现频率，一些空格，然后是这样的名字：

8427    OLIVER 
7031    JACK 
6862    HARRY 
5478    ALFIE 
5410    CHARLIE 
5307    THOMAS 
5256    WILLIAM 
5217    JOSHUA 
4542    GEORGE 
4351    JAMES 
4330    DANIEL 
4308    JACOB 
...

以下代码构造字典：

from collections import defaultdict

MAX_SUGGEST = 5

def gen_autosuggest(name_freq_file_name):
    with open(name_freq_file_name) as f:
        name2freq = {}
        for nf in f:
            freq, name = nf.split()
            if name not in name2freq:
                name2freq[name] = int(freq)
    pre2suggest = defaultdict(list)
    for name, freq in sorted(name2freq.items(), key=lambda x: -x[1]):
        # in decreasing order of popularity
        for i, _ in enumerate(name, 1):
            prefix = name[:i]
            pre2suggest[prefix].append((name, name2freq[name]))
    # set max suggestions
    return {pre:namefs[:MAX_SUGGEST]
            for pre, namefs in pre2suggest.items()}

if __name__ == '__main__':
    pre2suggest = gen_autosuggest('2010boysnames_popularity_engwales2.txt')

如果你给字典你的前缀，那么它会返回你的建议（在这种情况下连同它们的频率，但如果需要，可以丢弃这些建议：

>>> len(pre2suggest)
15303
>>> pre2suggest['OL']
[('OLIVER', 8427), ('OLLIE', 1130), ('OLLY', 556), ('OLIVIER', 175), ('OLIWIER', 103)]
>>> pre2suggest['OLI']
[('OLIVER', 8427), ('OLIVIER', 175), ('OLIWIER', 103), ('OLI', 23), ('OLIVER-JAMES', 16)]
>>>

看没有尝试:-)

时间杀手

如果运行需要很长时间，那么您可以预先计算 dict 并将其保存到文件中，然后在需要时使用 pickle 模块加载预先计算的值：

>>> import pickle
>>> 
>>> savename = 'pre2suggest.pcl'
>>> with open(savename, 'wb') as f:
    pickle.dump(pre2suggest, f)


>>> # restore it
>>> with open(savename, 'rb') as f:
    p2s = pickle.load(f)


>>> p2s == pre2suggest
True
>>>
于 2012-05-29T20:25:04.427 回答
0

这是有关如何执行此操作的想法：

构造一个字符串 trie 并将一个整数与树中的每个节点一起存储。此节点指示使用该节点的名称的数量。因此，当将该名称插入到 trie 中时，您将递增该名称的所有节点。

然后，您可以通过贪婪地选择具有最高值的名称来确定最高名称。

形式上，它与任何字符串 trie 构造算法相同，但增加了递增整数的步骤。

于 2012-05-24T19:40:20.493 回答
0

如果您想要快速查找，唯一真正的解决方案是预先计算任何给定前缀的答案。这在数据不变的情况下很好，但您需要一种方法来保持加载时间较短。

我建议使用 DBM 来存储预先计算的字典。这基本上是一个字典，其中的内容存储在磁盘上，并在您引用项目时进行查找。有关详细信息，请参阅http://docs.python.org/library/anydbm.html。唯一的缺点是值必须是字符串，因此您需要存储前 5 个条目的逗号分隔列表，并在查找时将其拆分。

这将比 pickle 具有更快的启动时间，因为不需要加载数据库。它也比使用 sqlite 简单得多。

于 2012-05-31T13:53:51.817 回答
0

您基本上可以增加一个 trie 实现，以按流行顺序而不是字母顺序存储它的子节点，也就是说，您还必须将流行度存储在 trie 的每个节点中。

于 2012-05-24T16:37:02.530 回答