La estructura de datos de Trie (árbol de prefijos)

A Trie, (también conocido como árbol de prefijos) es un tipo especial de árbol que se utiliza para almacenar estructuras de datos asociativas

Un trie (que se pronuncia try) recibe su nombre de re trie val: su estructura lo convierte en un algoritmo de coincidencia estelar.

Contexto

Write your own shuffle method to randomly shuffle characters in a string. 
Use the words text file, located at /usr/share/dict/words, and your shuffle method to create an anagram generator that only produces real words.
Given a string as a command line argument, print one of its anagrams. 

Se me presentó este desafío esta semana en la Academia de productos de Make School.

Las palabras del archivo de texto están separadas por nuevas líneas. Su formato hace que sea mucho más fácil poner las palabras en una estructura de datos. Por ahora, los estoy almacenando en una lista, cada elemento es una sola palabra del archivo.

Un enfoque para este desafío es:

  • baraja aleatoriamente los caracteres de la cadena
  • luego, compruébelo con todas las palabras que estaban en / usr / share / dict / words para verificar que es una palabra real.

Sin embargo, este enfoque requiere que verifique que los caracteres mezclados aleatoriamente en la nueva cadena coincidan con una de las 235,887 palabras en ese archivo, lo que significa 235,887 operaciones para cada cadena que quiero verificar como una palabra real.

Esta fue una solución inaceptable para mí. Primero busqué bibliotecas que ya se habían implementado para verificar si existen palabras en un idioma y encontré pyenchant. Primero completé el desafío usando la biblioteca, en unas pocas líneas de código.

def generateAnagram(string, language="en_US"): languageDict = enchant.Dict(language) numOfPossibleCombinationsForString = math.factorial(len(string)) for i in range(0, numOfPossibleCombinationsForString): wordWithShuffledCharacters = shuffleCharactersOf(string)
 if languageDict.check(wordWithShuffledCharacters): return wordWithShuffledCharacters return "There is no anagram in %s for %s." % (language, string)

Usar un par de funciones de biblioteca en mi código fue una solución rápida y fácil. Sin embargo, no aprendí mucho al encontrar una biblioteca que me resolviera el problema.

Estaba seguro de que la biblioteca no estaba usando el enfoque que mencioné anteriormente. Tenía curiosidad y busqué en el código fuente: encontré un truco.

Trie

Un trie almacena datos en "pasos". Cada paso es un nodo en el trie.

El almacenamiento de palabras es un caso de uso perfecto para este tipo de árbol, ya que hay una cantidad finita de letras que se pueden juntar para formar una cadena.

Cada paso, o nodo, en un idioma representará una letra de una palabra. Los pasos comienzan a ramificarse cuando el orden de las letras difiere del resto de palabras del trie, o cuando termina una palabra.

Creé un trie de directorios en mi escritorio para visualizar el paso a través de los nodos. Este es un trie que contiene dos palabras: manzana y aplicación.

Tenga en cuenta que el final de una palabra se indica con un '$'. Estoy usando '$' porque es un carácter único que no estará presente en ninguna palabra en ningún idioma.

Si tuviera que agregar la palabra 'apertura' a este trie, haría un bucle sobre las letras de la palabra 'apertura' mientras simultáneamente bajaba los nodos en el trie. Si la letra existe como hija del nodo actual, desciende a ella. Si la letra no existe como hija del nodo actual, créala y luego descienda a ella. Para visualizar estos pasos usando mis directorios:

Al bajar del trie, las dos primeras letras de 'apertura' ya están presentes en el trie, así que bajo en esos nodos.

La tercera letra, 'e', ​​sin embargo, no es hija del nodo 'p'. Se crea un nuevo nodo para representar la letra 'e', ​​que se bifurca de las otras palabras en el trie. También se crean nuevos nodos para las letras que siguen.

Para generar un trie a partir de un archivo de palabras, este proceso ocurrirá para cada palabra, hasta que se almacenen todas las combinaciones de cada palabra.

Quizás esté pensando: “Espera, ¿no tomará mucho tiempo generar el trie a partir de ese archivo de texto con 235,887 palabras? ¿Cuál es el punto de recorrer cada carácter en cada palabra? "

Sí, iterar sobre cada carácter de cada palabra para generar un trie lleva algo de tiempo. Sin embargo, el tiempo necesario para crear el ensayo vale la pena , porque para comprobar si existe una palabra en el archivo de texto, se necesitan como máximo tantas operaciones como la longitud de la palabra misma . Mucho mejor que las 235.887 operaciones que iba a realizar antes.

Escribí la versión más simple de un ensayo, usando diccionarios anidados. Esta no es la forma más eficiente de implementar uno, pero es un buen ejercicio para comprender la lógica detrás de un trie.

endOfWord = "$"
def generateTrieFromWordsArray(words): root = {} for word in words: currentDict = root for letter in word: currentDict = currentDict.setdefault(letter, {}) currentDict[endOfWord] = endOfWord return root
def isWordPresentInTrie(trie, word): currentDict = trie for letter in word: if letter in currentDict: currentDict = currentDict[letter] else: return False return endOfWord in currentDict

Puedes ver mi solución para el generador de anagramas en mi Github. Desde que exploré este algoritmo, he decidido hacer de esta publicación de blog una de muchas: cada publicación cubre un algoritmo o estructura de datos. El código está disponible en mi repositorio de Algoritmos y Estructuras de Datos - ¡Ábralo para mantenerse actualizado!

Próximos pasos

Sugiero consultar el repositorio trie de Ray Wenderlich. Aunque está escrito en Swift, es una fuente valiosa de explicaciones de varios algoritmos.

Similar al trie (pero más eficiente en memoria) es un árbol de sufijos o base. En resumen, en lugar de almacenar caracteres individuales en cada nodo, el final de una palabra, su sufijo, se almacena y las rutas se crean relativamente.

Sin embargo, un radix es más complicado de implementar que un trie. Sugiero echar un vistazo al repositorio de radix de Ray Wenderlich si está interesado.

Esta es la primera publicación de mi serie de algoritmos y estructuras de datos. En cada publicación, presentaré un problema que puede resolverse mejor con un algoritmo o estructura de datos para ilustrar el algoritmo / estructura de datos en sí.

¡Destaca mi repositorio de algoritmos en Github y sígueme en Twitter si quieres seguirme!

¿Obtuvo valor al leer este artículo? ¡Haz clic aquí para compartirlo en Twitter! Si deseas ver contenido como este con más frecuencia, sígueme en Medium y suscríbete a mi boletín mensual a continuación. No dudes en invitarme a un café también.