有人问了一个关于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方法。如果您发现任何错误，请告诉我，但它似乎运作良好。另外，如果您发现效率有任何大的提高，我也希望听到有关它们的信息。我已经考虑过要在每个分支的底部都使用空字典，但是我现在暂时不做。这些空字典可以用链接到单词的数据代替，以扩展实现的用途。
无论如何，如果您不喜欢我的实现方式，至少这可能会给您一些有关您希望如何实现自己的版本的想法。
