首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >如何在Python中创建trie

如何在Python中创建trie
EN

Stack Overflow用户
提问于 2012-06-13 20:56:14
回答 15查看 126.6K关注 0票数 141

我对the和DAWGs (直接非循环单词图)很感兴趣,我读了很多关于它们的文章,但我不明白输出trie或DAWG文件应该是什么样子。

  • 应该是嵌套字典的对象吗?其中每个字母被分成字母,依此类推?
  • 如果有100k或500k条目,在这样的字典上执行查找是否会很快?
  • 如何实现由-或空格分隔的多个单词组成的词块?
  • 如何将一个单词的前缀或后缀链接到结构中的另一个部分?(针对DAWG)

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

我也希望能得到DAWG和trie输出。

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

EN

回答 15

Stack Overflow用户

回答已采纳

发布于 2012-06-13 21:56:08

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的知识才能正确使用它。

票数 187
EN

Stack Overflow用户

发布于 2012-10-16 19:22:37

看看这个:

https://github.com/kmike/marisa-trie

Python2.x和3.x的

静态内存高效Trie结构。

与标准Python字典相比,MARISA-trie中的字符串数据占用的内存最多可以减少50倍-100倍;原始查找速度相当;trie还提供了快速的高级方法,如前缀搜索。

基于marisa-trie C++库。

以下是一家公司成功使用marisa trie的博客文章:

https://www.repustate.com/blog/sharing-large-data-structure-across-processes-python/

在Repustate中,我们在文本分析中使用的许多数据模型都可以表示为简单的键值对,或者Python行话中的字典。在我们的特殊情况下,我们的字典很大,每个字典有几百MB,并且需要不断地访问它们。事实上,对于给定的HTTP请求,可能会访问4到5个模型,每个模型进行20-30次查找。因此,我们面临的问题是,我们如何让客户端的事情变得更快,同时让服务器端的事情变得尽可能轻。

..。

我找到了这个包,marisa trie,它是围绕marisa trie的C++实现的Python包装器。“Marisa”是用递归实现的StorAge匹配算法的首字母缩写。关于marisa尝试的伟大之处在于,存储机制确实缩小了您所需的内存量。Python插件的作者声称尺寸减少了50-100倍-我们的经验是相似的。

marisa trie包的伟大之处在于,底层trie结构可以写入磁盘,然后通过内存映射对象读取。有了内存映射的marisa trie,我们所有的需求现在都得到了满足。我们的服务器内存使用量急剧下降,大约下降了40%,性能与使用Python的字典实现时没有变化。

还有一些纯python实现,除非你在受限的平台上,否则你会想要使用上面的C++支持的实现来获得最佳性能:

票数 29
EN

Stack Overflow用户

发布于 2014-01-23 16:36:12

以下是实现Trie的python包的列表:

的双数组C++实现

票数 27
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/11015320

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档