实现 Patricia Trie 用作字典
我正在尝试使用 addWord()
、isWord()
和 isPrefix()
方法来实现 Patricia Trie 作为存储方式用于快速检索的大型单词词典(包括前缀搜索)。我已经阅读了这些概念,但它们只是没有澄清实现。我想知道(在Java或Python代码中)如何实现Trie,特别是节点(或者我应该递归地实现它)。我看到一个人用一组 26 个子节点设置为 null/None 来实现它。是否有更好的策略(例如将字母视为位)以及您将如何实施它?
I'm attempting to implement a Patricia Trie with the methods addWord()
, isWord()
, and isPrefix()
as a means to store a large dictionary of words for quick retrieval (including prefix search). I've read up on the concepts but they just aren't clarifying into an implementation. I want to know (in Java or Python code) how to implement the Trie, particularly the nodes (or should I implement it recursively). I saw one person who implemented it with an array of 26 child nodes set to null/None. Is there a better strategy (such as treating the letters as bits) and how would you implement it?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
发布评论
评论(2)
不久前,有人问了一个关于 Patricia attempts 的问题,我当时就想过做一个 Python 实现,但这次我决定真正尝试一下(是的,这太过分了,但它似乎是一个不错的小项目)。我所做的也许不是纯粹的 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']
将返回“abc”是否在 trie 中。
我认为也许我应该用它制作一个模块并将其提交给 PyPI,但它需要更多测试,至少需要一个removeWord 方法。如果您发现任何错误请告诉我,但它似乎运行得很好。另外,如果您看到效率有任何重大改进,我也想听听。我曾考虑过在每个分支的底部放置空字典,但我现在暂时放弃它。例如,可以用链接到单词的数据来替换这些空字典,以扩展实现的用途。
不管怎样,如果你不喜欢我实现它的方式,至少这会给你一些关于如何实现你自己的版本的想法。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
这是使用更多 Python 方法的递归实现:
Here's a recursive implementation using more pythonic methods: