我正在尝试使用 , 和 方法实现 Patricia Trie addWord()，isWord()并将isPrefix()其作为一种存储大型单词字典以便快速检索（包括前缀搜索）的方法。我已经阅读了这些概念，但它们只是没有阐明实现。我想知道（在 Java 或 Python 代码中）如何实现 Trie，尤其是节点（或者我应该递归地实现它）。我看到一个人用一组 26 个子节点设置为 null/None 来实现它。是否有更好的策略（例如将字母视为位）以及您将如何实施？
问问题
7887 次
2 回答
13
前段时间有人问了一个关于 Patricia 尝试的问题，我当时想制作一个 Python 实现，但这次我决定试一试（是的，这太过分了，但它似乎是一个不错的小项目）。我所做的可能不是纯粹的 Patricia trie 实现，但我更喜欢我的方式。其他 Patricia 尝试（在其他语言中）仅使用孩子的列表并检查每个孩子以查看是否有匹配项，但我认为这相当低效，所以我使用字典。这基本上是我的设置方式：
我将从根节点开始。根只是一个字典。字典的键都是通向分支的单个字符（单词的第一个字母）。与每个键对应的值是列表，其中第一项是一个字符串，它给出与 trie 的该分支匹配的字符串的其余部分，第二项是一个字典，该字典导致该节点的进一步分支。该词典还具有与单词其余部分的第一个字母相对应的单字符键，并且该过程继续沿着 trie 进行。
我应该提到的另一件事是，如果给定的节点有分支，但也是 trie 本身中的一个词，那么这表示为''在字典中有一个键，该键通向一个带有 list 的节点['',{}]。
这是一个小例子，展示了单词是如何存储的（根节点是变量_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 方法。如果您发现任何错误，请告诉我，但它似乎运行良好。此外，如果您看到效率方面的任何重大改进，我也想听听它们。我考虑过在每个分支的底部放置空字典，但我现在要离开它。例如，这些空字典可以用链接到单词的数据来替换，以扩展实现的用途。
无论如何，如果您不喜欢我实现它的方式，至少也许这会给您一些关于您希望如何实现自己的版本的想法。
于 2010-03-09T20:51:45.317 回答
3
这是使用更多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:])
于 2013-04-16T21:33:27.640 回答