data-structures
Trie (árbol de prefijo / árbol de radix)

Introducción a Trie

¿Te has preguntado alguna vez cómo funcionan los motores de búsqueda? ¿Cómo alinea Google millones de resultados frente a usted en tan solo unos pocos milisegundos? ¿Cómo una enorme base de datos situada a miles de kilómetros de usted encuentra la información que está buscando y se la envía? La razón detrás de esto no es posible solo mediante el uso más rápido de Internet y superordenadores. Algunos algoritmos de búsqueda fascinantes y estructuras de datos funcionan detrás de esto. Una de ellas es Trie .

Trie , también llamado árbol digital y, a veces, árbol de prefijos o de radix (ya que pueden buscarse por prefijos), es un tipo de árbol de búsqueda: una estructura de datos de árbol ordenada que se utiliza para almacenar un conjunto dinámico o una matriz asociativa donde están las claves. por lo general cuerdas. Es una de esas estructuras de datos que se pueden implementar fácilmente. Digamos que tienes una enorme base de datos de millones de palabras. Puede usar trie para almacenar esta información y la complejidad de la búsqueda de estas palabras depende solo de la longitud de la palabra que estamos buscando. Eso significa que no depende de qué tan grande es nuestra base de datos. ¿No es eso asombroso?

Supongamos que tenemos un diccionario con estas palabras:

algo
algea
also
tom
to

Queremos almacenar este diccionario en la memoria de tal manera que podamos encontrar fácilmente la palabra que estamos buscando. Uno de los métodos consistiría en clasificar las palabras lexicográficamente: cómo los diccionarios de la vida real almacenan palabras. Entonces podemos encontrar la palabra haciendo una búsqueda binaria . Otra forma es usar Prefix Tree o Trie , en resumen. La palabra 'Trie' viene de la palabra Re trie val. Aquí, prefijo denota el prefijo de cadena que puede definirse así: Todas las subcadenas que pueden crearse desde el principio de una cadena se llaman prefijo. Por ejemplo: 'c', 'ca', 'cat' son todos el prefijo de la cadena 'cat'.

Ahora volvamos a Trie . Como su nombre lo sugiere, crearemos un árbol. Al principio, tenemos un árbol vacío con solo la raíz:

Insertaremos la palabra 'algo' . Crearemos un nuevo nodo y nombraremos el borde entre estos dos nodos 'a' . Desde el nuevo nodo crearemos otra ventaja llamada 'l' y la conectaremos con otro nodo. De esta manera, crearemos dos nuevos bordes para 'g' y 'o' . Tenga en cuenta que no estamos almacenando ninguna información en los nodos. Por ahora, solo consideraremos crear nuevos bordes desde estos nodos. A partir de ahora, vamos a llamar a un borde llamado 'x' - edge-x

Ahora queremos añadir la palabra 'algea' . Necesitamos un edge-a desde la raíz, que ya tenemos. Así que no necesitamos agregar nuevas ventajas. De manera similar, tenemos un borde de 'a' a 'l' y 'l' a 'g' . Eso significa que 'alg' ya está en el trie . Solo agregaremos edge-e y edge-a con él.

Añadiremos la palabra 'también' . Tenemos el prefijo 'al' de root. Sólo añadiremos 'así' con él.

Vamos a añadir 'tom' . Esta vez, creamos un nuevo borde desde la raíz ya que no tenemos ningún prefijo de tom creado anteriormente.

Ahora, ¿cómo debemos agregar 'a' ? 'to' es completamente un prefijo de 'tom' , por lo que no necesitamos agregar ninguna ventaja. Lo que podemos hacer es poner marcas finales en algunos nodos. Pondremos marcas finales en aquellos nodos donde se complete al menos una palabra. El círculo verde denota la marca final. El trie se verá como:

Puedes entender fácilmente por qué agregamos las marcas finales. Podemos determinar las palabras almacenadas en trie. Los caracteres estarán en los bordes y los nodos contendrán las marcas finales.

Ahora puedes preguntar, ¿cuál es el propósito de almacenar palabras como esta? Digamos, se le pide que encuentre la palabra 'alice' en el diccionario. Vas a atravesar el trie. Comprobarás si hay un edge-a desde la raíz. A continuación, compruebe desde 'a' , si hay un borde-l . Después de eso, no encontrará ninguna edge-i , por lo que puede llegar a la conclusión de que la palabra alice no existe en el diccionario.

Si se le pide que busque la palabra 'alg' en el diccionario, atravesará root-> a , a-> l , l-> g , pero no encontrará un nodo verde al final. Así que la palabra no existe en el diccionario. Si busca 'tom' , terminará en un nodo verde, lo que significa que la palabra existe en el diccionario.

Complejidad:

La cantidad máxima de pasos necesarios para buscar una palabra en un trío es la longitud de la palabra que estamos buscando. La complejidad es O (longitud) . La complejidad para la inserción es la misma. La cantidad de memoria necesaria para implementar trie depende de la implementación. Veremos una implementación en otro ejemplo donde podemos almacenar 10 ⁶ caracteres (no palabras, letras) en un trie .

Uso de Trie:

• Para insertar, eliminar y buscar una palabra en el diccionario.
• Para averiguar si una cadena es un prefijo de otra cadena.
• Para saber cuántas cadenas tiene un prefijo común.
• Sugerencia de nombres de contacto en nuestros teléfonos dependiendo del prefijo que ingresamos.
• Averiguar 'Substring Común más largo' de dos cadenas.
• Averiguar la longitud del 'Prefijo común' para dos palabras usando 'El ancestro común más largo'

Implementación de Trie

Antes de leer este ejemplo, es muy recomendable que lea Introducción a Trie primero.

Una de las maneras más fáciles de implementar Trie es usar la lista enlazada.

Nodo:

Los nodos constarán de:

1. Variable para la marca final.
2. Pointer Array al siguiente nodo.

La variable marca de final simplemente indicará si es un punto final o no. La matriz de punteros indicará todos los bordes posibles que se pueden crear. Para los alfabetos en inglés, el tamaño de la matriz será de 26, ya que se pueden crear un máximo de 26 bordes desde un solo nodo. Al principio, cada valor de la matriz de punteros será NULL y la variable de marca final será falsa.

Node:
Boolean Endmark
Node *next[26]
Node()
    endmark = false
    for i from 0 to 25
        next[i] := NULL
    endfor
endNode

Cada elemento en la siguiente [] matriz apunta a otro nodo. el siguiente [0] apunta al nodo que comparte el borde-a , el siguiente [1] apunta al nodo que comparte el borde-b y así sucesivamente. Hemos definido el constructor de Nodo para inicializar Endmark como falso y poner NULL en todos los valores de la siguiente matriz de punteros [] .

Para crear Trie , primero necesitaremos crear una instancia de root . Luego, desde la raíz , crearemos otros nodos para almacenar información.

Inserción:

Procedure Insert(S, root):    // s is the string that needs to be inserted in our dictionary
curr := root
for i from 1 to S.length
    id := S[i] - 'a'
    if curr -> next[id] == NULL
        curr -> next[id] = Node()
    curr := curr -> next[id]
endfor
curr -> endmark = true

Aquí estamos trabajando con az . Entonces, para convertir sus valores ASCII a 0-25 , restamos el valor ASCII de 'a' de ellos. Comprobaremos si el nodo actual (curr) tiene un borde para el personaje en cuestión. Si lo hace, nos movemos al siguiente nodo usando ese borde, si no creamos un nuevo nodo. Al final, cambiamos la marca final a verdadero.

Buscando:

Procedure Search(S, root)      // S is the string we are searching
curr := root
for i from 1 to S.length
    id := S[i] - 'a'
    if curr -> next[id] == NULL
        Return false
    curr := curr -> id
Return curr -> endmark

El proceso es similar a insertar. Al final, devolvemos la marca final . De modo que si la marca final es verdadera, eso significa que la palabra existe en el diccionario. Si es falso, entonces la palabra no existe en el diccionario.

Esta fue nuestra principal implementación. Ahora podemos insertar cualquier palabra en trie y buscarla.

Supresión:

A veces necesitaremos borrar las palabras que ya no se utilizarán para ahorrar memoria. Para este propósito, necesitamos eliminar las palabras no utilizadas:

Procedure Delete(curr):       //curr represents the current node to be deleted
for i from 0 to 25
    if curr -> next[i] is not equal to NULL
        delete(curr -> next[i])
    delete(curr)               //free the memory the pointer is pointing to

Esta función va a todos los nodos secundarios de curr , los elimina y luego se elimina curr para liberar la memoria. Si llamamos delete (root) , eliminará todo Trie .

Trie puede implementarse usando Arrays también.