java - 实现 Patricia Trie 用作字典

Question

我正在尝试使用 addWord()、isWord() 和 isPrefix() 方法实现帕特里夏树作为意思是存储一个大的单词词典，以便快速检索(包括前缀搜索)。我已经阅读了这些概念，但它们只是没有阐明实现。我想知道(在 Java 或 Python 代码中)如何实现 Trie，特别是节点(或者我应该递归地实现它)。我看到一个人用一个包含 26 个子节点的数组设置为 null/None 来实现它。是否有更好的策略(例如将字母视为位)以及您将如何实现它？

Answer 1

不久前有人问了一个关于 Patricia 尝试的问题，当时我想做一个 Python 实现，但这次我决定真正尝试一下(是的，这太过分了，但它看起来不错项目)。我所做的可能不是纯粹的 Patricia trie 实现，但我更喜欢我的方式。其他 Patricia 尝试(用其他语言)只为 child 使用一个列表并检查每个 child 是否匹配，但我认为这是相当低效的，所以我使用字典。这基本上是我的设置方式:

我将从根节点开始。根只是一本字典。字典的键都是通向分支的单个字符(单词的第一个字母)。与每个键对应的值是列表，其中第一项是一个字符串，它给出与 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 方法。如果您发现任何错误，请告诉我，但它似乎工作得很好。此外，如果您发现效率有任何重大改进，我也很想听听。我考虑过在每个分支的底部做一​​些空字典的事情，但我现在要离开它。例如，这些空词典可能会被链接到单词的数据替换，以扩展实现的用途。

无论如何，如果您不喜欢我实现它的方式，至少也许这会给您一些关于如何实现您自己的版本的想法。