如何在Python中创建trie

Question

我对tries和DAWGs（直接无环字图）很感兴趣，我已经读了很多关于它们的东西，但我不明白输出trie或DAWG文件应该是什么样子。

null

我也会很感激一个DAWG和Trie的输出。

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

Answer 1

放松本质上是正确的，有许多不同的方法来实现一个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距离的东西才能正确。