Реализация Patricia Trie для использования в качестве словаря

Question

Я пытаюсь реализовать Патрицию Три с помощью методов addWord(), isWord(), и isPrefix() как средство хранения большого словаря слов для быстрого поиска (включая поиск по префиксам).Я прочитал концепции, но они просто не проясняют реализацию.Я хочу знать (в коде Java или Python), как реализовать Trie, особенно узлы (или мне следует реализовать его рекурсивно).Я видел одного человека, который реализовал это с массивом из 26 дочерних узлов со значением null/None.Есть ли лучшая стратегия (например, рассматривать буквы как биты) и как бы вы ее реализовали?

Answer 1

Некоторое время назад кто-то еще задал вопрос о попытках Патриции, и тогда я подумал о создании реализации Python, но на этот раз я решил действительно попробовать (да, это слишком запредельно, но мне показалось, что это хороший маленький проект).То, что я сделал, возможно, не является чистой реализацией дерева Patricia, но мой способ мне нравится больше.Другая Патрисия пытается (на других языках) использовать только список дочерних элементов и проверять каждого дочернего элемента на наличие совпадений, но мне показалось, что это довольно неэффективно, поэтому я использую словари.Вот в основном, как я это настроил:

Я начну с корневого узла.Корень - это просто словарь.В словаре есть ключи, состоящие из одиночных символов (первых букв слов), ведущих к ветвям.Значения, соответствующие каждому ключу, представляют собой списки, где первый элемент представляет собой строку, которая дает остальную часть строки, соответствующую этой ветке дерева, а второй элемент представляет собой словарь, ведущий к дальнейшим ветвям от этого узла.В этом словаре также есть односимвольные клавиши, которые соответствуют первой букве остальной части слова, и процесс продолжается вниз по дереву.

Еще я должен упомянуть, что если данный узел имеет ветви, но также является словом в самом дереве, то это обозначается наличием '' ключ в словаре, ведущий к узлу со списком ['',{}].

Вот небольшой пример, показывающий, как хранятся слова (корневым узлом является переменная _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» в дереве или нет.

Я думаю, что, возможно, мне следует сделать из этого модуль и отправить его в PyPI, но для этого требуется дополнительное тестирование и хотя бы метод удаленияWord.Если вы обнаружите какие-либо ошибки, дайте мне знать, но, похоже, все работает очень хорошо.Кроме того, если вы увидите какие-либо значительные улучшения в эффективности, я также хотел бы услышать о них.Я подумывал о том, чтобы оставить пустые словари внизу каждой ветки, но пока оставляю это.Эти пустые словари могут быть заменены данными, связанными со словом, например, для расширения использования реализации.

В любом случае, если вам не нравится то, как я это реализовал, по крайней мере, возможно, это даст вам некоторые идеи о том, как вы хотели бы реализовать свою собственную версию.

Answer 2

Вот рекурсивная реализация с использованием большего количества питонических методов:

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:])