Implementación de la estructura de datos de Trie

Introducción

La palabra trie es un inflix de la palabra "re trie val", porque el trie puede encontrar una sola palabra en un diccionario con sólo un prefijo de la palabra.

Trie es una estructura de datos de recuperación de datos eficiente. Con trie, las complejidades de la búsqueda se pueden llevar a un límite óptimo, es decir, la longitud de la cadena.

Es una estructura de árbol de múltiples vías útil para almacenar cadenas sobre un alfabeto, cuando las estamos almacenando. Se ha utilizado para almacenar grandes diccionarios de inglés, digamos, palabras en programas de revisión ortográfica. Sin embargo, la penalización en los intentos son los requisitos de almacenamiento.

¿Qué es un trie?

Un trie es una estructura de datos en forma de árbol que almacena cadenas y le ayuda a encontrar los datos asociados con esa cadena utilizando el prefijo de la cadena.

Por ejemplo, supongamos que planea crear un diccionario para almacenar cadenas junto con sus significados. Debes preguntarte por qué no puedo simplemente usar una tabla hash para obtener la información.

Sí, puede obtener información usando una tabla hash, pero las tablas hash solo pueden encontrar datos donde la cadena coincide exactamente con la que hemos agregado. Pero el trie nos dará la capacidad de encontrar cadenas con prefijos comunes, un carácter faltante, etc. en menos tiempo, en comparación con una tabla hash.

Un trie normalmente se parece a esto,

Trie

Ésta es una imagen de un Trie, que almacena las palabras {assoc, algo, all, also, tree, trie}.

Cómo implementar un trie

Implementemos un trie en python, para almacenar palabras con sus significados de un diccionario de inglés.

ALPHABET_SIZE = 26 # For English class TrieNode: def __init__(self): self.edges = [None]*(ALPHABET_SIZE) # Each index respective to each character. self.meaning = None # Meaning of the word. self.ends_here = False # Tells us if the word ends here.

Como puede ver, los bordes tienen una longitud de 26, cada índice se refiere a cada carácter del alfabeto. 'A' corresponde a 0, 'B' a 1, 'C' a 2… 'Z' al índice 25. Si el carácter que está buscando está apuntando None, eso implica que la palabra no está en el trie.

Un Trie típico debería implementar al menos estas dos funciones:

  • add_word(word,meaning)
  • search_word(word)
  • delete_word(word)

Además, también se puede agregar algo como

  • get_all_words()
  • get_all_words_with_prefix(prefix)

Añadiendo Word al proceso

 def add_word(self,word,meaning): if len(word)==0: self.ends_here = True # Because we have reached the end of the word self.meaning = meaning # Adding the meaning to that node return ch = word[0] # First character # ASCII value of the first character (minus) the ASCII value of 'a'-> the first character of our ALPHABET gives us the index of the edge we have to look up. index = ord(ch) - ord('a') if self.edges[index] == None: # This implies that there's no prefix with this character yet. new_node = TrieNode() self.edges[index] = new_node self.edges[index].add(word[1:],meaning) #Adding the remaining word

Recuperando datos

 def search_word(self,word): if len(word)==0: if self.ends_here: return True else: return "Word doesn't exist in the Trie" ch = word[0] index = ord(ch)-ord('a') if self.edge[index]== None: return False else: return self.edge[index].search_word(word[1:])

La search_wordfunción nos dirá si la palabra existe en el Trie o no. Dado que el nuestro es un diccionario, también necesitamos buscar el significado, ahora declaremos una función para hacer eso.

 def get_meaning(self,word): if len(word)==0 : if self.ends_here: return self.meaning else: return "Word doesn't exist in the Trie" ch = word[0] index = ord(ch) - ord('a') if self.edges[index] == None: return "Word doesn't exist in the Trie" else: return self.edges[index].get_meaning(word[1:])

Borrando datos

Al eliminar datos, solo necesita cambiar la variable ends_herea False. Hacer eso no altera los prefijos, pero elimina el significado y la existencia de la palabra del trie.

 def delete_word(self,word): if len(word)==0: if self.ends_here: self.ends_here = False self.meaning = None return "Deleted" else: return "Word doesn't exist in the Trie" ch = word[0] index = ord(ch) - ord('a') if self.edges[index] == None: return "Word doesn't exist in the Trie" else: return self.edges[index].delete_word(word[1:])
:cohete:

Ejecutar código