Implementando una Patricia Trie para usar como diccionario

Question

Estoy intentando implementar una Patricia Trie con los métodos addWord(), isWord() y isPrefix() como un medio para almacenar un gran diccionario de palabras para la recuperación rápida (incluida la búsqueda de prefijos). He leído sobre los conceptos, pero simplemente no están aclarando en una implementación. Quiero saber (en código Java o Python) cómo implementar el Trie, particularmente los nodos (o debo implementarlo recursivamente). Vi a una persona que lo implementó con una matriz de 26 nodos secundarios configurados como nulos/Ninguno. ¿Hay una mejor estrategia (como tratar las letras como bits) y cómo implementarla?

Answer 1

Alguien más hizo una pregunta sobre Patricia hace un tiempo y pensé en hacer una implementación de Python entonces, pero esta vez decidí intentarlo (Sí, esto es demasiado por la borda, pero parecía un buen pequeño proyecto). Lo que he hecho quizás no sea una implementación pura de Patricia, pero me gusta mucho mejor. Otros intentos de Patricia (en otros idiomas) usan solo una lista para los niños y verifican que coincida, pero pensé que esto era bastante ineficiente, así que uso diccionarios. Aquí está básicamente cómo lo configuré:

Comenzaré en el nodo raíz. La raíz es solo un diccionario. El diccionario tiene claves que son todos los caracteres individuales (las primeras letras de las palabras) que llevan a las ramas. Los valores correspondientes a cada clave son listas donde el primer elemento es una cadena que proporciona el resto de la cadena que coincide con esta rama del trie, y el segundo elemento es un diccionario que conduce a otras ramas de este nodo. Este diccionario también tiene teclas de un solo carácter que se corresponden con la primera letra del resto de la palabra y el proceso continúa hacia abajo del trie.

Otra cosa que debo mencionar es que si un nodo dado tiene ramas, pero también es una palabra en el trie mismo, eso se denota teniendo 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 la variable _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', {}]}]} 

en cuenta que en el último caso, se añadió una llave '' al diccionario para denotar que 'abc' es una palabra en 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 necesita más pruebas y al menos un método removeWord. Si encuentras algún error, avísame, pero parece funcionar bastante bien. Además, si observa grandes mejoras en la eficiencia, también me gustaría saber sobre ellos. He considerado hacer algo para tener diccionarios vacíos en la parte inferior de cada rama, pero lo dejo por ahora. Estos diccionarios vacíos pueden reemplazarse con datos vinculados a la palabra para expandir los usos de la implementación, por ejemplo.

De todos modos, si no le gusta la forma en que lo implementé, al menos tal vez le dará algunas ideas sobre cómo le gustaría implementar su propia versión.

Answer 2

He aquí 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:])