Cómo crear una TRIE en Python

Soy nuevo en Python y estoy tratando de aprender y avanzar. Estoy interesado en TRIEs y DAWGs y he estado leyendo mucho al respecto, pero no entiendo cómo debería ser el archivo de salida TRIE o DAWG.

  • ¿Debe una TRIE ser un objeto de diccionarios nesteds? ¿Dónde se divide cada letra en letras y así sucesivamente?
  • ¿Una búsqueda realizada en dicho diccionario sería rápida si hay entradas de 100k o 500k?
  • ¿Cómo implementar bloques de palabras que consistan en más de una palabra separada con – o espacio?
  • ¿Cómo vincular el prefijo o el sufijo de una palabra a otra parte en la estructura? [para DAWG]

Quiero entender la mejor estructura de salida para descubrir cómo crear y usar una.

También apreciaría lo que debería ser la salida de un DAWG junto con TRIE .

No quiero ver representaciones gráficas con burbujas vinculadas entre sí, las vi mucho mientras leía.

Me gustaría saber el objeto de salida una vez que un conjunto de palabras se convierta en TRIE o DAWG.

    Gracias.

    Desenrollar es esencialmente correcto que hay muchas maneras diferentes de implementar un trie; y para una lista grande y escalable, los diccionarios nesteds pueden volverse incómodos, o al menos ineficientes en cuanto al espacio. Pero como recién estás empezando, creo que ese es el enfoque más fácil; Usted podría codificar un trie simple en unas pocas líneas. Primero, una función para construir el trie:

     >>> _end = '_end_' >>> >>> def make_trie(*words): ... root = dict() ... for word in words: ... current_dict = root ... for letter in word: ... current_dict = current_dict.setdefault(letter, {}) ... current_dict[_end] = _end ... return root ... >>> make_trie('foo', 'bar', 'baz', 'barz') {'b': {'a': {'r': {'_end_': '_end_', 'z': {'_end_': '_end_'}}, 'z': {'_end_': '_end_'}}}, 'f': {'o': {'o': {'_end_': '_end_'}}}} 

    Si no está familiarizado con setdefault , simplemente busca una clave en el diccionario (aquí, letter o _end ). Si la clave está presente, devuelve el valor asociado; si no, asigna un valor predeterminado a esa clave y devuelve el valor ( {} o _end ). (Es como una versión de get que también actualiza el diccionario).

    A continuación, una función para probar si la palabra está en el trie. Esto podría ser más conciso, pero lo dejo detallado para que la lógica sea clara:

     >>> def in_trie(trie, word): ... current_dict = trie ... for letter in word: ... if letter in current_dict: ... current_dict = current_dict[letter] ... else: ... return False ... else: ... if _end in current_dict: ... return True ... else: ... return False ... >>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'baz') True >>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'barz') True >>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'barzz') False >>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'bart') False >>> in_trie(make_trie('foo', 'bar', 'baz', 'barz'), 'ba') False 

    Te dejo la inserción y el retiro como ejercicio.

    Por supuesto, la sugerencia de Unwind no sería mucho más difícil. Puede haber una pequeña desventaja de velocidad en el sentido de que encontrar el subnodo correcto requeriría una búsqueda lineal. Pero la búsqueda se limitaría al número de caracteres posibles: 27 si incluimos _end . Además, no hay nada que ganar al crear una lista masiva de nodos y acceder a ellos por índice como sugiere; También podrías anidar las listas.

    Finalmente, agregaré que crear un DAWG sería un poco más complejo, porque tiene que detectar situaciones en las que su palabra actual comparte un sufijo con otra palabra en la estructura. De hecho, esto puede ser bastante complejo, ¡dependiendo de cómo quiera estructurar el DAWG! Es posible que tenga que aprender algunas cosas sobre la distancia Levenshtein para hacerlo bien.

    Echa un vistazo a esto:

    https://github.com/kmike/marisa-trie

    Estructuras Trie de memoria estática y eficiente para Python (2.xy 3.x).

    Los datos de cadena en un MARISA-trie pueden tomar hasta 50x-100x menos memoria que en un dict de Python estándar; la velocidad de búsqueda en bruto es comparable; Trie también proporciona métodos avanzados rápidos como búsqueda de prefijo.

    Basado en la biblioteca marisa-trie C ++.

    Aquí hay una publicación de blog de una empresa que usa marisa trie con éxito:
    https://www.repustate.com/blog/sharing-large-data-structure-across-processes-python/

    En Repustate, muchos de nuestros modelos de datos que utilizamos en nuestro análisis de texto se pueden representar como simples pares clave-valor, o diccionarios en la jerga de Python. En nuestro caso particular, nuestros diccionarios son masivos, unos pocos cientos de MB cada uno, y necesitan ser accedidos constantemente. De hecho, para una solicitud HTTP dada, se puede acceder a 4 o 5 modelos, cada uno de los cuales realiza entre 20 y 30 búsquedas. Entonces, el problema al que nos enfrentamos es cómo mantener las cosas rápidas para el cliente y lo más ligeras posible para el servidor.

    Encontré este paquete, que intenta marisa, que es un envoltorio de Python alrededor de una implementación en C ++ de un trío de marisa. “Marisa” es un acrónimo de algoritmo de coincidencia con StorAge implementado recursivamente. Lo bueno de los bashs de marisa es que el mecanismo de almacenamiento realmente reduce la cantidad de memoria que necesita. El autor del complemento de Python afirmó una reducción de tamaño de 50-100X; nuestra experiencia es similar.

    Lo bueno del paquete marisa trie es que la estructura trie subyacente se puede escribir en el disco y luego leer a través de un objeto asignado en la memoria. Con una memoria asignada a Marisa Trie, ahora se cumplen todos nuestros requisitos. El uso de la memoria de nuestro servidor se redujo drásticamente, en aproximadamente un 40%, y nuestro rendimiento no varió cuando usamos la implementación del diccionario de Python.

    También hay un par de implementaciones de python puro, aunque, a menos que estés en una plataforma restringida, querrás usar la implementación respaldada por C ++ que se muestra arriba para obtener el mejor rendimiento:

    Aquí hay una lista de paquetes de python que implementan Trie:

    • marisa-trie – una implementación basada en C ++.
    • python-trie – una implementación simple de python pura.
    • PyTrie – una implementación de python pura más avanzada.
    • pygtrie – una implementación pura de python por Google.
    • datrie – una implementación de trie de doble matriz basada en libdatrie .

    No hay “debería”; tu decides. Varias implementaciones tendrán diferentes características de rendimiento, tomarán varias cantidades de tiempo para implementar, comprender y hacer las cosas bien. Esto es típico de todo el desarrollo de software, en mi opinión.

    Probablemente, primero intentaría tener una lista global de todos los nodos trie creados hasta ahora y representar los punteros secundarios en cada nodo como una lista de índices en la lista global. Tener un diccionario solo para representar la vinculación del niño es demasiado pesado para mí.

    Modificado desde el senderle del senderle (arriba). Descubrí que el valor defaultdict de Python es ideal para crear un árbol de trie o prefijo.

     from collections import defaultdict class Trie: """ Implement a trie with insert, search, and startsWith methods. """ def __init__(self): self.root = defaultdict() # @param {string} word # @return {void} # Inserts a word into the trie. def insert(self, word): current = self.root for letter in word: current = current.setdefault(letter, {}) current.setdefault("_end") # @param {string} word # @return {boolean} # Returns if the word is in the trie. def search(self, word): current = self.root for letter in word: if letter not in current: return False current = current[letter] if "_end" in current: return True return False # @param {string} prefix # @return {boolean} # Returns if there is any word in the trie # that starts with the given prefix. def startsWith(self, prefix): current = self.root for letter in prefix: if letter not in current: return False current = current[letter] return True # Now test the class test = Trie() test.insert('helloworld') test.insert('ilikeapple') test.insert('helloz') print test.search('hello') print test.startsWith('hello') print test.search('ilikeapple') 

    Si quieres una TRIE implementada como una clase de Python, aquí hay algo que escribí después de leer sobre ellos:

     class Trie: def __init__(self): self.__final = False self.__nodes = {} def __repr__(self): return 'Trie'.format(len(self), self.__final) def __getstate__(self): return self.__final, self.__nodes def __setstate__(self, state): self.__final, self.__nodes = state def __len__(self): return len(self.__nodes) def __bool__(self): return self.__final def __contains__(self, array): try: return self[array] except KeyError: return False def __iter__(self): yield self for node in self.__nodes.values(): yield from node def __getitem__(self, array): return self.__get(array, False) def create(self, array): self.__get(array, True).__final = True def read(self): yield from self.__read([]) def update(self, array): self[array].__final = True def delete(self, array): self[array].__final = False def prune(self): for key, value in tuple(self.__nodes.items()): if not value.prune(): del self.__nodes[key] if not len(self): self.delete([]) return self def __get(self, array, create): if array: head, *tail = array if create and head not in self.__nodes: self.__nodes[head] = Trie() return self.__nodes[head].__get(tail, create) return self def __read(self, name): if self.__final: yield name for key, value in self.__nodes.items(): yield from value.__read(name + [key]) 

    Esta versión está utilizando recursión.

     import pprint from collections import deque pp = pprint.PrettyPrinter(indent=4) inp = raw_input("Enter a sentence to show as trie\n") words = inp.split(" ") trie = {} def trie_recursion(trie_ds, word): try: letter = word.popleft() out = trie_recursion(trie_ds.get(letter, {}), word) except IndexError: # End of the word return {} # Dont update if letter already present if not trie_ds.has_key(letter): trie_ds[letter] = out return trie_ds for word in words: # Go through each word trie = trie_recursion(trie, deque(word)) pprint.pprint(trie) 

    Salida:

     Coool👾 🚸 python trie.py Enter a sentence to show as trie foo bar baz fun { 'b': { 'a': { 'r': {}, 'z': {} } }, 'f': { 'o': { 'o': {} }, 'u': { 'n': {} } } } 
     from collections import defaultdict 

    Definir Trie:

     _trie = lambda: defaultdict(_trie) 

    Crear Trie:

     trie = _trie() for s in ["cat", "bat", "rat", "cam"]: curr = trie for c in s: curr = curr[c] curr.setdefault("_end") 

    Buscar:

     def word_exist(trie, word): curr = trie for w in word: if w not in curr: return False curr = curr[w] return '_end' in curr 

    Prueba:

     print(word_exist(trie, 'cam'))