如何在Python中创建一个trie树

我对 trie 和 DAWG（直接非循环字图）感兴趣，并且阅读了很多有关它们的内容，但我不明白输出 trie 或 DAWG 文件应该是什么样子。

• trie 应该是嵌套字典的对象吗？每个字母在哪里又分为to letter等等？
• 如果有 100k 或 500k 条目，在这样的字典上执行查找会很快吗？
• 如何实现由多个单词分隔的单词块-还是空间？
• 如何将单词的前缀或后缀链接到结构中的另一部分？ （对于 DAWG）

我想了解最好的输出结构以弄清楚如何创建和使用它。

我也很感激应该是什么DAWG 的输出随着trie.

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

Unwind https://stackoverflow.com/a/11015381/577088有许多不同的方法来实现 trie，这基本上是正确的；对于大型、可扩展的字典树来说，嵌套字典可能会变得很麻烦——或者至少是空间效率低下。但由于您才刚刚开始，我认为这是最简单的方法；你可以编写一个简单的代码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 https://docs.python.org/library/stdtypes.html#dict.setdefault，它只是在字典中查找一个键（这里，letter or _end）。如果键存在，则返回关联的值；如果没有，它会为该键分配一个默认值并返回该值（{} or _end）。 （这就像一个版本get https://docs.python.org/library/stdtypes.html#dict.get这也会更新字典。）

接下来是一个测试单词是否在 trie 中的函数：

>>> 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！你可能需要学习一些关于编辑 http://en.wikipedia.org/wiki/Levenshtein_distance distance https://stackoverflow.com/q/10638597/577088把它做好。