Trei y Tabla Hash (una respeusta)

Jimmy hizo una entrada sobre el tema de trei y hash table, pero pedió una explicación más clara. Entonces, decidí investigar el tema. Aquí es mi entendemiento.

Imagine que se necesita un sistema para almacenar cadenas, donde cada cadena está asociada con un valor. La cadena, entonces, puede sirvir como una clave para encontrar el valor asociado. Sabiendo la clave se puede encontrar el valor asociado. Los dos pueden ser guardados como un par (clave,valor) dentro de una matriz. En cada indice de la matriz se encuentra un par. El primero elemento del par es la clave y el segundo elemento es su valor. El problema con este arbordaje es ¿en cual indice guardar cual par?, pues sin saber el indice ni se puede encontrar la clave ni su valor.

Una función hash resuelva el problema, pero en una manera problemática, mientras un trie evite el problema.

Una tabla hash usa una función hash que mapea cada clave a un número que sirve para ser un indice a la matriz. Un problema es que la misma función es, a veces, capaz de mapear dos cadenas al mismo número. En este caso se tiene que guardar un par en un otro lugar de la matriz o asociar el lugar dentro de la matriz con una otra lista, agregando a esta lista todos los pares cuya función hash mapeó al mismo indice de la matriz. Esto implica que para encontrar el par se tiene que primero usar la función hash para llegar en el indice cierto de la matriz y despues pasar por cada par en la lista guardada alla hasta encontrar el par querido, lo que hace mucho mas lenta la buscada.

Usar un trie evita el problema porque en vez de guardar pares de (cadena,valor) en una matriz, se crea un arbol que implicitimente representa las cadenas, en sus nodos terminales, pues se puede usar cualquiera cadena para seguir una trayectoria hasta llegar en el nodo que representa (implicitamente) la cadena. Alla, se puede encontrar el valor de la cadena.

El nombre “trie” (o arbol de prefix) viene de un juego de palabras en inglés. “Trie” viene de “retrieval”, que quiere decir buscada y recuperación de información. Pero “trie” suena como “tree”, lo que es inglés para “arbol”. La idea es que se puede tomar el conjunto de cadenas para cuales se quiere guardar sus valores y formar en una manera sistematica un arbol que contiene nodos para cada cadena y cada prefijo de cada cadena. El nodo de encima es una cadena vacía. Despues viene una capa con nodos que representan (por su posición en la capa) el primero carácter de cada cadena, listado en orden del lado izquierdo al lado derecho (o vice-versa), seguido por una capa abajo con nodos que representan los primeros dos carácteres de cada cadena, etc, pues entre un nodo de la primera capa y un nodo de la segunda capa se va agregando (implicitamente, por su orden en la capa) el segundo carácter de la cadena. Esta continua hasta que se llega en nodos terminales, que representan las cadenas completas. Si más de una cadena comparte el mismo primero carácter, el nodo va conectar con más que un nodo de la capa abajo, y igual. para las otras capas. (Vé [http://en.wikipedia.org/wiki/Image:Trie_example.svg] por un gráfico de esto).

Asi guardado, es fácil, entonces, encontrar el nodo que representa cualquiera cadena, y asi encontrar el valor asociado con la cadena, guardado en el nodo. Se empieza en el nodo encima del arbol y se busca para el nodo abajo que debe representar el primero carácter. Por ejemplo, se todos las cadenas empiezan con “a” o “b” se sabe que el nodo que representa “a” es el primero nodo y el nodo que representa “b” es el segundo nodo. Si todas las cadenas que comienzan con “b” también comienzan con “ba”, “be” o “bo” se sabe que se encuentra el nodo para “be” en el segundo nodo por abajo del nodo para “b”, etc.

Como Jimi dice:

Un trie es un caso especial de autómata finito determinista (S, Σ, T, s, A), que sirve para almacenar un conjunto de cadenas E en el que:
Σ es el alfabeto sobre el que están definidas las cadenas;
S, el conjunto de estados, cada uno de los cuales representa un prefijo de E;
la función de transición: ; está definida como sigue: T(x,σ)...

Σ es un conjunto de todos los caracteres (o sea, letras) de todas las cadenas (o sea, palabras) que queremos guardar.

Se puede notar que un arbol parece a un tipo de automáta finito determinista para procesar las cadenas representadas (por los nodos terminales) por dentro de si mismo. Piense en la representación gráfica de tal automáta. Su estado inicial, s, es la cadena vacía, el nodo encima del trie. Cada nodo representa un prefijo de cada cadena, siendo uno (o cero si se toma en cuenta el estado incial) o más caracteres de la cadena. Asi, se puede representar también un estado del autómata (elemento de S). Los nodos terminales, los que representan las cadenas completas, son estados de aceptación (elementos de A). Asi , la función de transición T(x,σ) sirve para crear las lineas conectando los nodos de una capa con los nodos de la capa abajo. T toma el prefijo representado por el nodo arriba y el proximo carácter de la cadena y mapea esto a un nodo abajo. (Por ejemplo, la función de transición mapea (“tr”,'i') al estado que representa “tri” y luego toma (“tri”,'e') y lo mapea al estado de aceptación que representa “trie”.)