当前位置: 首页 > 知识库问答 >
问题:

如何在Python中创建trie

钱振
2023-03-14

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

    null

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

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

共有1个答案

夔学智
2023-03-14

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

 类似资料:
  • 问题内容: 我对尝试和DAWG(直接非循环字图)感兴趣,并且已经阅读了很多有关它们的信息,但我不知道输出trie或DAWG文件应该是什么样。 特里应该是嵌套词典的对象吗?每个字母分为几个字母,依此类推? 如果存在100k或500k条目,对这样的词典执行的查找会很快吗? 如何实现由多个单词组成的单词块,用-空格或空格分隔? 如何将单词的前缀或后缀链接到结构的另一部分?(对于DAWG) 我想了解最佳的

  • 问题内容: 如何在独立于平台的Python中创建GUID?我听说有一种在Windows上使用ActivePython的方法,但这仅是Windows,因为它使用COM。有没有使用普通Python的方法? 问题答案: Python 2.5及更高版本中的uuid模块提供了符合RFC的UUID生成。有关详细信息,请参见模块文档和RFC。 文件: Python 2:http://docs.python.or

  • 问题内容: 有没有办法在Python中声明常量?在Java中,我们可以按以下方式创建常量值: Python中上述Java常量声明的等效项是什么? 问题答案: 不,那里没有。你无法在Python中将变量或值声明为常量。只是不要更改它。 如果你正在上课,则等价于: 如果不是,那只是 但是你可能想看看Alex Martelli 编写的Python代码片段中的Constants。 从Python 3.8开

  • 问题内容: 我如何声明一个非常大的位数组,例如600万位? 问题答案: 您可以在http://pypi.python.org/pypi/bitarray/中查看有关此模块的更多信息。

  • 问题内容: 我有引用文件路径的此函数: 其中FILE_PATH是文件路径的字符串,即 我想在python脚本中使用字符串内容创建文件FILE_NAME.ext: 怎么办呢?Python脚本将放置在Linux盒子中。 问题答案: 有一个用于python的模块,但是创建一个简单的文件也可以解决这个问题: 现在,您可以使用以下方法对其进行写入: 使用模块,它可能看起来像这样: 使用完后,您有责任删除文件

  • 问题内容: 例如,Python中的函数使用该模块返回文件中最常见单词的计数。 我已经跟踪了该文件,但是在理解如何相对于假设的单词创建/更新堆方面遇到了一些麻烦。 因此,我认为对我来说最好的理解方法是弄清楚如何从头开始创建堆。 有人可以提供伪代码来创建表示字数的堆吗? 问题答案: 这是在这里找到的代码的略微修改版本:http : //code.activestate.com/recipes/5770