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

Некоторое время назад кто-то еще задал вопрос о попытках Патрисии, и тогда я подумал о создании реализации Python, но на этот раз я решил попробовать (Да, это слишком много, но это казалось приятным маленьким проект). То, что я сделал, возможно, не является чистой реализацией Patricia 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']

вернет "abc" в дереве или нет.

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

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