实现Patricia Trie用作字典

Question

我试图实现一个帕特里夏特里结构的方法addWord(),isWord()以及isPrefix()作为一种手段来存储大量的字典进行快速检索(包括前缀搜索)的话.我已经阅读了这些概念,但他们只是没有澄清实现.我想知道(在Java或Python代码中)如何实现Trie,特别是节点(或者我应该递归地实现它).我看到一个人用26个子节点数组设置为null/None来实现它.是否有更好的策略(例如将字母视为位)以及如何实现它？

Answer 1

其他人问了一段关于帕特里夏尝试的问题,然后我考虑制作一个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方法.如果你发现任何错误让我知道,但它似乎工作得很好.此外,如果你看到效率有任何重大改进,我也想听听他们.我考虑过在每个分支的底部都有空字典,但我现在就离开了.这些空字典可以用链接到该单词的数据替换,以扩展实现的用途.

无论如何,如果你不喜欢我实现它的方式,至少可能会给你一些关于如何实现自己版本的想法.