实现Patricia Trie用作字典
我正在尝试使用addWord() ， isWord()和isPrefix()方法实现Patricia Trie，以便存储大型单词词典以便快速检索（包括前缀搜索）。 我已经阅读了这些概念，但他们只是没有澄清实现。 我想知道（在Java或Python代码中）如何实现Trie，特别是节点（或者我应该递归地实现它）。 我看到一个人使用26个子节点的数组设置为null / None来实现它。 是否有更好的策略（例如将字母视为位）以及如何实现它？
有人问了一段关于帕特里夏尝试的问题，然后我考虑制作一个Python实现，但这次我决定实际给它一个机会（是的，这是过分的，但它似乎是一个不错的小项目）。 我所做的可能不是纯粹的Patricia trie实现，但我更喜欢我的方式。 其他Patricia尝试（在其他语言中）只为孩子使用一个列表并检查每个孩子是否有匹配，但我认为这是相当低效的，所以我使用词典。 这基本上就是我如何设置的：
我将从根节点开始。 根只是一本字典。 字典的键是所有单个字符（单词的第一个字母），通向分支。 与每个键对应的值是列表，其中第一项是字符串，其给出与trie的该分支匹配的字符串的其余部分，第二项是从该节点引出进一步分支的字典。 这个字典也有单个字符键，与单词其余部分的第一个字母相对应，然后进程沿着trie继续。
我应该提到的另一件事是，如果一个给定的节点有分支，但也是trie本身的一个单词，那么通过在字典中有一个''键来表示一个带有列表['',{}]的节点['',{}] 。
这是一个小例子，显示了如何存储单词（根节点是变量_d ）：
>>> x = patricia() >>> x.addWord('abcabc') >>> x._d {'a': ['bcabc', {}]} >>> x.addWord('abcdef') >>> x._d {'a': ['bc', {'a': ['bc', {}], 'd': ['ef', {}]}]} >>> x.addWord('abc') {'a': ['bc', {'a': ['bc', {}], '': ['', {}], 'd': ['ef', {}]}]}
请注意，在最后一种情况下，在字典中添加了一个”键，表示’abc’是除’abcdef’和’abcabc’之外的单词。
源代码
class patricia(): def __init__(self): self._data = {} def addWord(self, word): data = self._data i = 0 while 1: try: node = data[word[i:i+1]] except KeyError: if data: data[word[i:i+1]] = [word[i+1:],{}] else: if word[i:i+1] == '': return else: if i != 0: data[''] = ['',{}] data[word[i:i+1]] = [word[i+1:],{}] return i += 1 if word.startswith(node[0],i): if len(word[i:]) == len(node[0]): if node[1]: try: node[1][''] except KeyError: data = node[1] data[''] = ['',{}] return else: i += len(node[0]) data = node[1] else: ii = i j = 0 while ii != len(word) and j != len(node[0]) and \ word[ii:ii+1] == node[0][j:j+1]: ii += 1 j += 1 tmpdata = {} tmpdata[node[0][j:j+1]] = [node[0][j+1:],node[1]] tmpdata[word[ii:ii+1]] = [word[ii+1:],{}] data[word[i-1:i]] = [node[0][:j],tmpdata] return def isWord(self,word): data = self._data i = 0 while 1: try: node = data[word[i:i+1]] except KeyError: return False i += 1 if word.startswith(node[0],i): if len(word[i:]) == len(node[0]): if node[1]: try: node[1][''] except KeyError: return False return True else: i += len(node[0]) data = node[1] else: return False def isPrefix(self,word): data = self._data i = 0 wordlen = len(word) while 1: try: node = data[word[i:i+1]] except KeyError: return False i += 1 if word.startswith(node[0][:wordlen-i],i): if wordlen - i > len(node[0]): i += len(node[0]) data = node[1] else: return True else: return False def removeWord(self,word): data = self._data i = 0 while 1: try: node = data[word[i:i+1]] except KeyError: print "Word is not in trie." return i += 1 if word.startswith(node[0],i): if len(word[i:]) == len(node[0]): if node[1]: try: node[1][''] node[1].pop('') except KeyError: print "Word is not in trie." return data.pop(word[i-1:i]) return else: i += len(node[0]) data = node[1] else: print "Word is not in trie." return __getitem__ = isWord
您可能已经注意到，最后我将__getitem__设置为isWord方法。 这意味着
x['abc']
将返回trie中是否为’abc’。
我想也许我应该创建一个模块并将其提交给PyPI，但它需要更多的测试，至少需要一个removeWord方法。 如果您发现任何错误让我知道，但它似乎工作得很好。 此外，如果你看到效率有任何重大改进，我也想听听它们。 我考虑过在每个分支的底部都有空字典，但我现在就离开了。 这些空字典可以用链接到该单词的数据替换，以扩展实现的用途。
无论如何，如果你不喜欢我实现它的方式，至少可能会给你一些关于如何实现自己版本的想法。
这是使用更多pythonic方法的递归实现：
def matching_prefix_index(word1, word2): max_len = min(len(word1),len(word2)) for i in range(max_len): if word2[i] != word1[i]: return i return max_len class PatriciaTrie(object): def __init__(self): self._storage = {} self._complete_prefix_flag = False def _find_storage_key(self, word): for key in self._storage: prefix_index = matching_prefix_index(key, word) if prefix_index > 0: return (key, prefix_index) return (None, None) def add(self, word): if word == '': self._complete_prefix_flag = True return True key, prefix_index = self._find_storage_key(word) if key is not None: if prefix_index == len(key): return self._storage[key].add(word[len(key):]) else: new_tree = PatriciaTrie() new_tree._storage[key[prefix_index:]] = self._storage.pop(key) self._storage[key[0:prefix_index]] = new_tree return new_tree.add(word[prefix_index:]) else: self._storage[word] = PatriciaTrie() self._storage[word].add('') return True def remove(self, word): if word == '': self._complete_prefix_flag = False return True key, prefix_index = self._find_storage_key(word) if key is None or prefix_index != len(key): return False subword = word[prefix_index:] subtrie = self._storage[key] if subtrie.remove(subword): if (not subtrie._complete_prefix_flag) and len(subtrie._storage) == 0: self._storage.pop(key) return True else: return False def __contains__(self, word): if word == '': return self._complete_prefix_flag key, prefix_index = self._find_storage_key(word) if key is None or prefix_index != len(key): return False else: return (word[prefix_index:] in self._storage[key]) def has_prefix(self, word): if word == '': return True key, prefix_index = self._find_storage_key(word) if key is None: return False elif len(key) > len(word): return (prefix_index == len(word)) elif len(key) != prefix_index: return False else: return self._storage[key].has_prefix(word[prefix_index:])