实现Patricia Trie用作字典-Java 学习之路

我正在尝试使用方法 addWord() ， isWord() 和 isPrefix() 来实现Patricia Trie，作为存储大型单词词典以便快速检索（包括前缀搜索）的方法 . 我澄清了一个实现 . 我想知道（在Java或Python代码中）如何实现Trie，特别是节点（或者我应该递归地实现它） . 我看到一个人使用26个子节点的数组设置为null / None来实现它 . 是否有更好的策略（例如将字母视为位）以及如何实现它？

2 回答

有人问了一段关于帕特里夏尝试的问题，然后我考虑制作一个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'之外的单词 .

Source Code

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

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

回复于 2024-04-29T10:59:13+08:00

这是使用更多pythonic方法的递归实现：

def matching_prefix_index(word1, word2):
    max_len = min(len(word1),len(word2))
    for i in range(max_len):
        if word2[i] != word1[i]:
            return i
    return max_len

class PatriciaTrie(object):
    def __init__(self):
        self._storage = {}
        self._complete_prefix_flag = False

    def _find_storage_key(self, word):
        for key in self._storage:
            prefix_index = matching_prefix_index(key, word)
            if prefix_index > 0:
                return (key, prefix_index)
        return (None, None)

    def add(self, word):
        if word == '':
            self._complete_prefix_flag = True
            return True

        key, prefix_index = self._find_storage_key(word)
        if key is not None:
            if prefix_index == len(key):
                return self._storage[key].add(word[len(key):])
            else:
                new_tree = PatriciaTrie()
                new_tree._storage[key[prefix_index:]] = self._storage.pop(key)
                self._storage[key[0:prefix_index]] = new_tree
                return new_tree.add(word[prefix_index:])
        else:
            self._storage[word] = PatriciaTrie()
            self._storage[word].add('')
            return True

    def remove(self, word):
        if word == '':
            self._complete_prefix_flag = False
            return True

        key, prefix_index = self._find_storage_key(word)
        if key is None or prefix_index != len(key):
            return False

        subword = word[prefix_index:]
        subtrie = self._storage[key]
        if subtrie.remove(subword):
            if (not subtrie._complete_prefix_flag) and len(subtrie._storage) == 0:
                self._storage.pop(key)
            return True
        else:
            return False

    def __contains__(self, word):
        if word == '':
            return self._complete_prefix_flag

        key, prefix_index = self._find_storage_key(word)
        if key is None or prefix_index != len(key):
            return False
        else:
            return (word[prefix_index:] in self._storage[key])

    def has_prefix(self, word):
        if word == '':
            return True

        key, prefix_index = self._find_storage_key(word)
        if key is None:
            return False
        elif len(key) > len(word):
            return (prefix_index == len(word))
        elif len(key) != prefix_index:
            return False
        else:
            return self._storage[key].has_prefix(word[prefix_index:])

回复于 2024-04-29T10:59:13+08:00

实现Patricia Trie用作字典

2 回答

相关问题