如何在Python中创建特里

Z时代
2024-01-10
分类：问答

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

特里应该是嵌套词典的对象吗？每个字母分为几个字母，依此类推？

如果存在100k或500k条目，对这样的词典执行的查找会很快吗？

如何实现由多个单词组成的单词块，用-空格或空格分隔？

如何将单词的前缀或后缀链接到结构的另一部分？（对于DAWG）

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

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

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

回答：

展开实际上是正确的，因为有许多不同的方法可以实现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