A implementação de um Patricia Trie para o uso como um dicionário

Question

Eu estou tentando implementar um Patricia Trie com o addWord() métodos, isWord() e isPrefix() como um meio para armazenar um grande dicionário de palavras para recuperação rápida (incluindo pesquisa de prefixo). Eu ler sobre os conceitos, mas eles simplesmente não estão esclarecendo em uma implementação. Eu quero saber (em código Java ou Python) como implementar o Trie, particularmente os nós (ou eu deveria implementá-lo de forma recursiva). Eu vi uma pessoa que implementou com uma variedade de nós de 26 crianças definido como nulo / Nenhum. Existe uma estratégia melhor (como tratar as letras como bits) e como você implementá-lo?

Answer 1

Alguém fez uma pergunta sobre Patricia tenta há um tempo atrás e eu pensei em fazer uma implementação de Python, em seguida, mas desta vez eu decidi realmente dar-lhe um tiro (Sim, esta é a maneira ao mar, mas parecia um pouco agradável projeto). O que eu fiz não é talvez uma implementação pura trie Patricia, mas eu como a minha maneira melhor. Outras tentativas Patricia (em outras línguas) usar apenas uma lista para as crianças e verificar cada criança para ver que há um jogo, mas eu pensei que esta era bastante ineficiente então eu uso dicionários. Aqui é basicamente como eu configurá-lo:

Vou começar no nó raiz. A raiz é apenas um dicionário. O dicionário tem chaves que são todos os caracteres individuais (as primeiras letras das palavras), levando às sucursais. Os valores correspondentes a cada tecla são listas em que o primeiro item é uma cadeia que dá o resto da string que corresponde com este ramo do trie, eo segundo item é um dicionário conduzindo a novos ramos deste nó. Este dicionário também tem teclas de caracteres individuais, que correspondem com a primeira letra do resto da palavra eo processo continua para baixo o trie.

Outra coisa que eu devo mencionar é que, se um determinado nó tem filiais, mas também é uma palavra na própria trie, em seguida, que é denotada por ter uma chave '' no dicionário que leva a um nó com a lista ['',{}].

Aqui está um pequeno exemplo que mostra como as palavras são armazenados (o nó raiz é a _d variável):

>>> 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', {}]}]}

Observe que no último caso, a '' chave foi adicionada ao dicionário para denotar que 'abc' é uma palavra em um além de 'abcdef' e 'abcabc'.

Código Fonte

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

Você deve ter notado que no final eu definir __getitem__ ao método isWord. Isto significa que

x['abc']

retornará se 'abc' no trie ou não.

Eu acho que talvez eu deveria fazer um módulo de fora deste e apresentá-lo PyPI, mas precisa de mais testes e pelo menos um método removeWord. Se você encontrar quaisquer erros deixe-me saber, mas parece estar funcionando muito bem. Além disso, se você ver qualquer grandes melhorias na eficiência Eu também gostaria de ouvir sobre eles. Eu considerei fazer algo sobre ter dicionários vazios na parte inferior de cada ramo, mas eu vou deixar isso por agora. Esses dicionários vazios podem ser substituídos com dados ligados à palavra para expandir os usos da implementação, por exemplo.

De qualquer forma, se você não gosta do jeito que eu implementado, pelo menos talvez isso vai lhe dar algumas idéias sobre como você gostaria de implementar sua própria versão.

Answer 2

Aqui está uma implementação recursiva usando métodos mais Python:

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