如何在Python中创建特里

Question

我对尝试和DAWG（直接非循环字图）感兴趣，并且已经阅读了很多有关它们的信息，但我不知道输出trie或DAWG文件应该是什么样。

• 特里应该是嵌套词典的对象吗？每个字母分为几个字母，依此类推？
• 如果存在100k或500k条目，对这样的词典执行的查找会很快吗？
• 如何实现由多个单词组成的单词块，用-空格或空格分隔？
• 如何将单词的前缀或后缀链接到结构的另一部分？（对于DAWG）

我想了解最佳的输出结构，以便弄清楚如何创建和使用一个结构。

我也希望DAWG和trie一起输出。

我不想看到带有彼此链接的气泡的图形表示，我想知道将一组单词转换为尝试或DAWG后的输出对象。

Answer 1

展开实际上是正确的，因为有许多不同的方法可以实现Trie。对于大型，可伸缩的特里，嵌套字典可能会变得很麻烦-或至少在空​​间上效率低下。但是，由于你才刚刚入门，因此我认为这是最简单的方法；你trie只需几行就可以编写一个简单的代码。首先，一个构造特里的函数：

>>> _end = '_end_'
>>> 
>>> def make_trie(*words):
...     root = dict()
...     for word in words:
...         current_dict = root
...         for letter in word:
...             current_dict = current_dict.setdefault(letter, {})
...         current_dict[_end] = _end
...     return root
... 
>>> make_trie('foo', 'bar', 'baz', 'barz')
{'b': {'a': {'r': {'_end_': '_end_', 'z': {'_end_': '_end_'}}, 
             'z': {'_end_': '_end_'}}}, 
 'f': {'o': {'o': {'_end_': '_end_'}}}}

如果你不熟悉setdefault，它只会在字典中查找一个键（此处为letter或_end）。如果键存在，则返回关联的值；否则，返回0。如果不是，它将为该键分配一个默认值并返回值（{}或_end）。（就像它的一个版本一样get，也会更新字典。）

接下来，一个测试单词是否在特里的函数：

>>> def in_trie(trie, word):
...     current_dict = trie
...     for letter in word:
...         if letter not in current_dict:
...             return False
...         current_dict = current_dict[letter]
...     return _end in current_dict
... 
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'baz')
True
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'barz')
True
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'barzz')
False
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'bart')
False
>>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'ba')
False

我将把插入和拔出留给你作为练习。

当然，Unwind的建议不会难得多。在速度方面可能存在一点缺点，即找到正确的子节点需要进行线性搜索。但是搜索将限于可能的字符数-如果包括，则为27 _end。而且，按照他的建议，创建大量节点并按索引访问它们并不会获得任何好处。你最好只嵌套列表。

最后，我要补充一点，创建有向无环词图（DAWG）会有些复杂，因为你必须检测当前词与结构中另一个词共享后缀的情况。实际上，这可能会变得相当复杂，具体取决于你要如何构造DAWG！你可能需要学习一些有关Levenshtein 距离的知识才能正确处理。