La implementación de un Patricia Trie para su uso como un diccionario

Question

Estoy tratando de implementar una Patricia Trie con el addWord() métodos, isWord() y isPrefix() como un medio para almacenar una gran diccionario de palabras para la recuperación rápida (incluyendo búsqueda de prefijo). He leído en los conceptos, sino que simplemente no está aclarando en una aplicación. Quiero saber (en Java o Python código) cómo implementar el trie, en particular los nodos (o debería aplicar de forma recursiva). Vi a una persona que puso en práctica con una serie de 26 nodos secundarios fijados a null / Ninguno. ¿Hay una mejor estrategia (por ejemplo, el tratamiento de las letras como bits) y cómo habría que ponerlo en práctica?

Answer 1

Otra persona hizo una pregunta sobre Patricia intenta hace un tiempo y pensé en hacer una implementación de Python a continuación, pero esta vez decidí realmente le dan un tiro (Sí, ésta es la manera por la borda, pero parecía un poco agradable proyecto). Lo que he hecho no es tal vez una aplicación pura trie Patricia, pero me gusta mi mejor manera. Otro Patricia intenta (en otros idiomas) utilizar sólo una lista para los niños y comprobar cada niño a ver que hay una coincidencia, pero yo pensaba que esto era bastante ineficiente, así que uso los diccionarios. Aquí es básicamente cómo me he instalado:

Voy a empezar en el nodo raíz. La raíz es sólo un diccionario. El diccionario tiene teclas que son todos los caracteres individuales (las primeras letras de las palabras) que conducen a las sucursales. Los valores correspondientes a cada tecla están listas en las que el primer elemento es una cadena que da el resto de la cadena que coincide con esta rama del trie, y el segundo elemento es un diccionario que lleva a nuevas ramas de este nodo. Este diccionario también tiene teclas de caracteres individuales que se corresponden con la primera letra del resto de la palabra y el proceso continúa hasta el trie.

Otra cosa que debo mencionar es que si un nodo dado tiene ramas, sino que también es una palabra en el propio trie, a continuación, que se denota por tener una clave '' en el diccionario que conduce a un nodo con la lista ['',{}].

Aquí hay un pequeño ejemplo que muestra cómo se almacenan las palabras (el nodo raíz es el _d variable):

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

Tenga en cuenta que en el último caso, 'se añadió clave para el diccionario para denotar que' a 'abc' es una palabra en una adición a 'abcdef' y 'abcabc'.

Código fuente

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

Usted puede haber notado que al final me puse __getitem__ al método isWord. Esto significa que

x['abc']

devolverá si 'abc' en el trie o no.

Creo que tal vez debería hacer un módulo de esto y enviarlo a PyPI, pero se necesita más pruebas y al menos un método removeWord. Si encuentra algún error, que me haga saber, pero parece estar funcionando bastante bien. Además, si hay grandes mejoras en la eficiencia También me gustaría oír hablar de ellos. He pensado en hacer algo acerca de tener diccionarios vacíos en la parte inferior de cada rama, pero estoy dejando todo por ahora. Estos diccionarios vacíos pueden ser reemplazados con datos vinculados a la palabra de ampliar los usos de la aplicación, por ejemplo.

De todos modos, si no te gusta la forma en que he implementado, por lo menos tal vez esto le dará algunas ideas sobre cómo le gustaría a poner en práctica su propia versión.

Answer 2

Esta es una implementación recursiva utilizando métodos más 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:])