我对the和DAWGs (直接非循环单词图)很感兴趣,我读了很多关于它们的文章,但我不明白输出trie或DAWG文件应该是什么样子。
-
或空格分隔的多个单词组成的词块?我想了解最好的输出结构,以便弄清楚如何创建和使用它。
我也希望能得到DAWG和trie的输出。
我不想看到带有相互链接的气泡的图形表示,我想知道一组单词转换为tries或DAWGs后的输出对象。
发布于 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的知识才能正确使用它。
发布于 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++支持的实现来获得最佳性能:
发布于 2014-01-23 16:36:12
以下是实现Trie的python包的列表:
的双数组C++实现
https://stackoverflow.com/questions/11015320
复制相似问题