实现Patricia Trie用作字典
我试图实现一个帕特里夏特里结构的方法addWord()
,isWord()
以及isPrefix()
作为一种手段来存储大字典中的字进行快速检索(包括前缀搜索)的。我已经阅读了这些概念,但是并没有明确说明它们的实现。我想知道(用Java或Python代码)如何实现Trie,特别是节点(或者我应该递归实现)。我看到一个人用将26个子节点设置为null
/ None来实现它。有没有更好的策略(例如将字母当作位),您将如何实现呢?
回答:
有人问了一个关于Patricia的问题,我想过要制作一个Python实现,但是这次我决定实际尝试一下(是的,这太过分了,但这似乎是一个不错的小项目)。我所做的可能不是纯粹的Patricia
trie实现,但我更喜欢自己的方式。其他帕特里夏(Patricia)尝试(使用其他语言)仅使用了一个孩子列表,并检查每个孩子是否有匹配项,但是我认为这样做效率不高,因此我使用词典。我基本上是这样设置的:
我将从根节点开始。根只是字典。字典中的键都是通向分支的单个字符(单词的首字母)。与每个键对应的值是列表,其中第一项是一个字符串,给出与该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方法。如果您发现任何错误,请告诉我,但它似乎运作良好。另外,如果您发现效率有任何大的提高,我也希望听到有关它们的信息。我已经考虑过要在每个分支的底部都使用空字典,但是我现在暂时不做。这些空字典可以用链接到单词的数据代替,以扩展实现的用途。
无论如何,如果您不喜欢我的实现方式,至少这可能会给您一些有关您希望如何实现自己的版本的想法。
以上是 实现Patricia Trie用作字典 的全部内容, 来源链接: utcz.com/qa/400214.html