如何在Python中创build一个TRIE
我是Python的新手，试图学习和发展。 我对TRIE和DAWG感兴趣，我一直在阅读很多，但我不明白输出TRIE或DAWG文件应该是什么样子。
- TRIE是嵌套字典的对象吗？ 每个字母都被分成几个字母等等？
- 如果有100k或500k的条目，那么在这样的字典上执行查找会快吗？
- 如何实现由多个单词组成的由多个单词组成的单词块？
- 如何将一个单词的前缀或后缀链接到结构中的另一个部分？ [DAWG]
我想了解最好的输出结构 ，以便弄清楚如何创build和使用它。
我还要感谢DAWG和TRIE的输出 。
我不想看到气泡相互连接的graphics表示，我在阅读时看到它们很多。
一旦一组单词变成TRIE或DAWG，我想知道输出对象。
谢谢。
放松在本质上是正确的，有许多不同的方式来实现一个trie; 而对于一个大的，可扩展的字典，嵌套字典可能会变得麻烦 – 至less是空间效率低下。 但是既然你刚开始，我认为这是最简单的方法。 你可以在几行代码中编写一个简单的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的版本，也更新字典。）
接下来，testing一个函数是否在单词中。 这可能更简洁，但是我将其放在冗长的位置，以便逻辑清晰：
>>> def in_trie(trie, word): ... current_dict = trie ... for letter in word: ... if letter in current_dict: ... current_dict = current_dict[letter] ... else: ... return False ... else: ... if _end in current_dict: ... return True ... else: ... return False ... >>> 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的build议不会更难。 可能存在轻微的速度劣势，因为find正确的子节点将需要线性search。 但search将限于可能的字符数 – 如果包含_end则为27。 另外，如他所build议的那样，通过创build大量的节点并通过索引来访问它们是没有任何好处的。 你也可以把这些列表嵌套起来。
最后，我会补充一点，创build一个DAWG会更复杂一些，因为你必须检测当前单词与结构中的另一个单词共享后缀的情况。 事实上，这可能会变得相当复杂，取决于你想如何构buildDAWG！ 你可能不得不学习一些关于Levenshtein 距离的东西来得到它的正确。
看看这个：
https://github.com/kmike/marisa-trie
Python的静态内存效率Trie结构（2.x和3.x）。
MARISA-trie中的string数据可能比标准Python字典中的内存less50至100倍; 原始的查询速度是可比较的; trie还提供了像前缀search这样的快速高级方法。
基于marisa-trie C ++库。
这是一个使用marisa trie成功的公司的博客文章：
http://blog.repustate.com/sharing-large-data-structure-across-processes-python/
在Repustate中，我们在文本分析中使用的大部分数据模型都可以用简单的键值对来表示，或者用Python的术语来表示。 在我们的具体情况下，我们的字典是巨大的，每个数百MB，需要不断地访问。 实际上，对于给定的HTTP请求，可以访问4或5个模型，每个模型都可以进行20-30次查找。 所以我们面临的问题是如何保持客户端的速度以及服务器的可用性。
…
我发现这个软件包，marisa尝试，这是一个围绕一个marisa trie的C ++实现的Python包装。 “Marisa”是recursion实现StorAge的匹配algorithm的缩写。 存储机制真正缩小了你需要的内存量，这对于marisa来说真是太棒了。 Python插件的作者声称缩小了50-100倍 – 我们的经验是相似的。
marisa trie软件包的优点在于底层的trie结构可以写入磁盘，然后通过内存映射对象读入。 通过内存映射marisa trie，现在我们所有的要求都满足了。 我们的服务器的内存使用率大幅下降了大约40％，而且我们的性能与我们使用Python的字典实现时没有变化。
还有一些纯python实现，除非你是在一个受限制的平台上，否则你想使用上面C ++支持的实现来获得最佳性能：
这是一个实现Trie的Python包列表：
- marisa-trie – 一个基于C ++的实现。
- python-trie – 一个简单的纯python实现。
- PyTrie – 更高级的纯Python实现。
从senderle的方法（上面）修改。 我发现Python的defaultdict是创build一个trie或前缀树的理想select。
from collections import defaultdict class Trie: """ Implement a trie with insert, search, and startsWith methods. """ def __init__(self): self.root = defaultdict() # @param {string} word # @return {void} # Inserts a word into the trie. def insert(self, word): current = self.root for letter in word: current = current.setdefault(letter, {}) current.setdefault("_end") # @param {string} word # @return {boolean} # Returns if the word is in the trie. def search(self, word): current = self.root for letter in word: if letter not in current: return False current = current[letter] if "_end" in current: return True return False # @param {string} prefix # @return {boolean} # Returns if there is any word in the trie # that starts with the given prefix. def startsWith(self, prefix): current = self.root for letter in prefix: if letter not in current: return False current = current[letter] return True # Now test the class test = Trie() test.insert('helloworld') test.insert('ilikeapple') test.insert('helloz') print test.search('hello') print test.startsWith('hello') print test.search('ilikeapple')
没有“应该”; 随你便。 各种实现将具有不同的性能特点，需要花费不同的时间来实现，理解和获得正确的。 在我看来，这是整个软件开发的典型代表。
我可能会首先尝试创build迄今为止创build的所有trie节点的全局列表，并将每个节点中的子指针表示为全局列表中的索引列表。 有一本字典只是为了代表孩子的联系，对我来说太重了。
如果你想把一个TRIE作为一个Python类来实现，下面是我在阅读后写的：
class Trie: def __init__(self): self.__final = False self.__nodes = {} def __repr__(self): return 'Trie<len={}, final={}>'.format(len(self), self.__final) def __getstate__(self): return self.__final, self.__nodes def __setstate__(self, state): self.__final, self.__nodes = state def __len__(self): return len(self.__nodes) def __bool__(self): return self.__final def __contains__(self, array): try: return self[array] except KeyError: return False def __iter__(self): yield self for node in self.__nodes.values(): yield from node def __getitem__(self, array): return self.__get(array, False) def create(self, array): self.__get(array, True).__final = True def read(self): yield from self.__read([]) def update(self, array): self[array].__final = True def delete(self, array): self[array].__final = False def prune(self): for key, value in tuple(self.__nodes.items()): if not value.prune(): del self.__nodes[key] if not len(self): self.delete([]) return self def __get(self, array, create): if array: head, *tail = array if create and head not in self.__nodes: self.__nodes[head] = Trie() return self.__nodes[head].__get(tail, create) return self def __read(self, name): if self.__final: yield name for key, value in self.__nodes.items(): yield from value.__read(name + [key])
这个版本使用recursion
import pprint from collections import deque pp = pprint.PrettyPrinter(indent=4) inp = raw_input("Enter a sentence to show as trie\n") words = inp.split(" ") trie = {} def trie_recursion(trie_ds, word): try: letter = word.popleft() out = trie_recursion(trie_ds.get(letter, {}), word) except IndexError: # End of the word return {} # Dont update if letter already present if not trie_ds.has_key(letter): trie_ds[letter] = out return trie_ds for word in words: # Go through each word trie = trie_recursion(trie, deque(word)) pprint.pprint(trie)
输出：
Coool👾 <algos>🚸 python trie.py Enter a sentence to show as trie foo bar baz fun { 'b': { 'a': { 'r': {}, 'z': {} } }, 'f': { 'o': { 'o': {} }, 'u': { 'n': {} } } }
