python - 如何在 Python 中创建一个 trie

Question

我对 Trie 和 DAWG(直接无环词图)很感兴趣，我已经阅读了很多关于它们的内容，但我不明白输出 trie 或 DAWG 文件应该是什么样子。

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

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

我也很欣赏 DAWG 的输出 以及 trie。

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

Answer 1

Unwind本质上是正确的，有许多不同的方式来实现 trie；对于大型、可扩展的 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 ，它只是在字典中查找一个键(此处为 letter 或 _end)。如果键存在，则返回关联的值；如果不是，它会为该键分配一个默认值并返回该值({} 或 _end)。 (就像 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 的建议不会难很多。找到正确的子节点可能需要线性搜索，这可能会带来轻微的速度劣势。但是搜索将被限制在可能的字符数——如果我们包含 _end 则为 27 个。此外，正如他所建议的那样，通过创建大量节点列表并按索引访问它们并没有什么好处；你也可以只嵌套列表。

最后，我要补充一点，创建有向无环词图 (DAWG) 会稍微复杂一些，因为您必须检测当前词与结构中的另一个词共享后缀的情况。事实上，这可能会变得相当复杂，具体取决于您希望如何构建 DAWG!你可能需要学习一些关于 Levenshtein 的知识。 distance做对了。