Estructura de Datos : Arboles Trie

Definiciones

Los Trie son arboles de busqueda, donde las claves de busqueda son interpretadas partidas en porciones de claves. Estas porciones son utilizadas para armar la estructura de datos de busqueda.

     <--------- clave ---------->

     +--------------------------+
     |  |  |  |  |  |  |  |  |  |
     +--------------------------+

      <> <> <> <> <> <> <> <> <>           <> = Porción

     Clave = aef789g, Porción 1 = ae, Porción 2 = f7, Porción 3 = 89, Porción 4 = g , Porción 5 =   , Porción 6 =   , Porción 7 =   , Porción 8 =   , Porción 9 =   .

     +--------------------------+
     |ae|f7|89|g |  |  |  |  |  |
     +--------------------------+

Ejemplos de claves partidas :

Claves alfabeticas
- Claves alfabeticas ( Idioma Ingles - Alfabeto 26 letras )
  Cantidad de caracteres distintos = 26 letras + 1 blanco = 27 caracteres
  Cantidad de caracteres en cada porción = 1 caracter
  Cantidad de entradas por nodo = 27 ** 1 = 27 entradas
  Diseño del nodo :
```
           a b c d  ........  x y z
        +--------------------------+
        | | | | | | ........ | | | |
        +--------------------------+
        
```
- Claves alfabeticas ( Idioma Castellano - Alfabeto 28 letras )
  Cantidad de caracteres distintos = 28 letras + 1 blanco = 29 caracteres
  Cantidad de caracteres en cada porción = 2 caracter
  Cantidad de entradas por nodo = 29 x 29 = 29 ** 2 = 841 entradas
  Diseño del nodo :
```
             a  b  c  d  ..........  ñn ññ ñm  ..........  zx zy zz
        +----------------------------------------------------------+
        |  |  |  |  |  | .......... |  |  |  | .......... |  |  |  |
        +----------------------------------------------------------+
        
```
Claves alfanuméricas
- Claves alfanumericas ( Idioma Castellano - Alfabeto 28 letras )
  Cantidad de caracteres distintos = 29 letras + 1 blanco + 10 numeros = 39 caracteres
  Cantidad de caracteres en cada porción = 1 caracter
  Cantidad de entradas por nodo = 39 ** 1 = 39 entradas
  Diseño del nodo :
```
           a b c d  ...  ñ  ...  x y z 1 2  ...  9 0
        +-------------------------------------------+
        | | | | | | ... | | ... | | | | | | ... | | |
        +-------------------------------------------+
        
```
- Claves alfanumericas con caracteres especiales ( Idioma Castellano - Alfabeto 28 letras )
  Cantidad de caracteres distintos = 28 letras + 1 blanco + 10 numeros + 7 caracteres especiales = 46 caracteres
  Cantidad de caracteres en cada porción = 1 caracter
  Cantidad de entradas por nodo = 46 ** 1 = 46 entradas
  Diseño del nodo :
```
           a b c d  ...  ñ  ...  x y z 1 2  ...  9 0 = < > % # & @
        +---------------------------------------------------------+
        | | | | | | ... | | ... | | | | | | ... | | | | | | | | | |
        +---------------------------------------------------------+
        
```

Número de la porción en la clave partida en n porciones

        +-------------------------------------------------------------------+
        |   |   |   |   |   | ................ |   | .......... |   |   |   |
        +-------------------------------------------------------------------+
          1   2   3   4   5   ................   i  ...........  n-2 n-1  n     ----> Número de la porción

Un Trie es un árbol de grado m >= 2 en el cual la ramificación a cualquier nivel es determinado no por el valor completo de la clave, sinó por una proción de ella.

T es la variable que apunta al nodo raíz del Trie. La raiz es necesariamente un nodo Rama.

Los Tries tienen dos tipos de nodos :

Nodos Ramas ( Branch Nodes )

Contienen un número fijo de entradas.

Cada entrada esta compuesta por un indicador de tipo de nodo y el enlace a dicho nodo. A continuación puede verse la variedad de entradas que pueden existir en un nodo rama :

   ............---------------------..............
                 | Tipo | Enlace |
   ............---------------------..............
                 <--- Entrada --->
				 
				 
   ............---------------------..............
                 |  B   |   *....|......................> Apunta a un Nodo Rama
   ............---------------------..............
                 <--- Entrada --->
				 
   ............---------------------..............
                 |  L   |   *....|......................> Apunta a un Nodo Hoja
   ............---------------------..............
                 <--- Entrada --->
				 
   ............---------------------..............
                 |  0   |   0    |                        Entrada Vacia
   ............---------------------..............
                 <--- Entrada --->

Si el tipo es B el enlace apunta a un nodo rama, si el tipo es L el enlace apunta a un nodo hoja y si el tipo es 0 es una entrada vacia, no apunta a ningún nodo y el árbol termina en esa entrada.

El enlace hacia un nodo rama apunta a un subtrie que contiene todos los valores de las claves cuya porción tienen el mismo valor.
El nivel j de la ramificación es determinado por la porción de numero j.

Nodos Hojas ( Leaves Nodes )
- Cuando un subtrie contiene solamente una valor de clave, este apunta a un Nodo Leaf.
- El Nodo Leaf contiene el valor de la clave y toda información relevante de ese valor de clave, como ser, la dirección del registro correspondiente.
- Veamos una representación de un nodo hoja :
```
        +--------------------------------------+
        |    clave    | direccion del registro |
        +--------------------------------------+
```

Las porciones de una clave están numeradas de isquierda a derecha, de 1 a n. El órden de uso de estas porciones pueden diferir del número de la porción. Se entiende por órden de uso de las porciones el órden en que las porciones son llamadas para navegar el árbol. Veamos ejemplos :

            +-------------------------------------------------------------------+
            |   |   |   |   |   | ................................. |   |   |   |
            +-------------------------------------------------------------------+
              1   2   3   4   5   .................................  n-2 n-1  n     ----> Número de la porción
              1   2   3   4   5   .................................  n-2 n-1  n     ----> Orden Ejemplo A
              n  n-1 n-2 n-3 n-4  .................................   3   2   1     ----> Orden Ejemplo B
              1   3   5   7   9                                       6   4   2     ----> Orden Ejemplo C

Buscar en un Trie el valor de la clave X significa desmembrar a X en sus porciones constituyentes y seguir la ramificación del Trie según los valores de las porciones.

Los Tries ( Tries ) es una estructura de datos útil para volores de claves de ancho variable.

Dada una clave a buscar, debo contar con una funcion a la que le pase como parametros la clave mencionada ( X ) y un entero ( o ), indicatriz del órden de la porción dentro de dicha clave. A esta función la llamare Funcion Muestreo ( Sampling Function ). La función devuelve el tipo de entrada hallado ( t ) y el enlace correspondiente ( e ). Veamos algunos ejemplos :

SAMPLE( X, o ) ===> ( t, e ) donde o = i.
SAMPLE( X, o ) ===> ( t, e ) donde o = n-i+1.
SAMPLE( X, o ) ===> ( t, e ) donde o = randomización de ( X, i ).
SAMPLE( X, o ) ===> ( t, e ) donde o = i/2 si i es par y n-(i-1)/2 si i es impar.

Ejemplos de Tries

Veamos las particularidades generales de todos los ejemplos :

Las claves son alfabéticas y se usa el idioma inglés.

Las porciones de la clave son de 1 caracter.

Los Branch Nodes tienen 27 entradas, por el uso del alfabeto ingles.

Todos los caracteres de los valores de las claves se asumen ser una de las 26 letras del alfabeto inglés, más el blanco.

El primer y último caracter de la clave no son blancos.

En el nivel 1 del Trie todos los valores de las claves son particionadas en 27 clases disjuntas dependiendo de la porcion de primer órden.

En el nivel 1 del Trie todos los valores de las claves son particionadas en 27 clases disjuntas dependiendo de la porcion de segundo órden.

En el nivel 1 del Trie todos los valores de las claves son particionadas en 27 clases disjuntas dependiendo de la porcion de tercer órden.

..........

En el nivel 1 del Trie todos los valores de las claves son particionadas en 27 clases disjuntas dependiendo de la porcion de enésimo órden.

Los Branch Nodes se dibujan con rectángulos de guiones.

Los Information Nodes se dibujan con rectángulos de asteriscos.

El juego de valores de claves es : bluebird, bunting, cardinal, chickadee, godwit, goshawk, gull, oriole, thrasher, thrush y wren.

Primer ejemplo

El Trie tiene el órden de las porciones iguales a los números de las porciones :

                                A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
                             +-----------------------------------------------------+
                             |0|0| | |0|0|0| |0|0|0|0|0|0|0| |0|0|0|0| |0|0| |0|0|0|                                   --------- Nivel 1
                             +-----------------------------------------------------+
                                  | |       |               |         |     |
                                  | |       |               |         |     +---------------------------------+
                                  | |       |               |         +-------------------------+             |
            +---------------------+ +---+   |               +---------------------+             |             |
            |                           |   +-----------------------+             |             |             |
            |                           |                           |             |             |             |
       +---------+                 +---------+                 +---------+   ***********   +---------+   ***********
       |..l....u.|                 |a...h....|                 |.....o..u|   * oriole  *   |....h....|   *  wren   *   --------- Nivel 2
       +---------+                 +---------+                 +---------+   ***********   +---------+   ***********
          |   |                       |   |                       |   |                         |
     +----+   +----+             +----+   +----+             +----+   +----+                    |
     |             |             |             |             |             |                    |
***********   ***********   ***********   ***********   +---------+   ***********          +---------+
*bluebird *   * bunting *   *cardinal *   *chickadee*   |..d...s..|   *  gull   *          |......r..|                 --------- Nivel 3
***********   ***********   ***********   ***********   +---------+   ***********          +---------+
                                                           |   |                                |
                                                      +----+   +----+                           |
                                                      |             |                           |
                                                 ***********   ***********                 +---------+
                                                 * godwit  *   * goshawk *                 |a.......u|                 --------- Nivel 4
                                                 ***********   ***********                 +---------+
                                                                                              |   |
                                                                                         +----+   +----+
                                                                                         |             |
                                                                                    ***********   ***********
                                                                                    *thrasher *   * thrush  *          --------- Nivel 5
                                                                                    ***********   ***********

Segundo ejemplo

Veamos ahora el ejemplo visto anteriormente pero creando el Trie usando porciones que van desde la derecha hacia la isquierda :


                                A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
                             +-----------------------------------------------------+
                             |0|0|0|0| | |0| | |0|0| | |0| |0|0|0| |0| |0|0|0|0|0|0|                                         --------- Nivel 1
                             +-----------------------------------------------------+
                                      | |   | |     | |   |       |   |
                                      | |   | |     | |   |       |   +----------------------------------------------+
                                      | |   | |     | |   |       +------------------------------------+             |
     +--------------------------------+ |   | |     | |   +------------------------------+             |             |
     |             +--------------------+   | |     | +--------------------+             |             |             |
     |             |             +----------+ ++    +--------+             |             |             |             |
     |             |             |             |             |             |             |             |             |
***********   +---------+   ***********   ***********   ***********   +---------+   ***********   ***********   ***********
*bluebird *   |         |   * bunting *   * thrush  *   * goshawk *   |         |   *  wren   *   *thrasher *   * godwit  *  --------- Nivel 2
***********   +---------+   ***********   ***********   ***********   +---------+   ***********   ***********   ***********
                 |   |                                                   |   |
            +----+   +----+                                         +----+   +----+
            |             |                                         |             |
       ***********   ***********                               ***********   ***********
       *chickadee*   * oriole  *                               *cardinal *   *  gull   *                                     --------- Nivel 3
       ***********   ***********                               ***********   ***********

Tercer ejemplo

Veamos ahora el ejemplo visto anteriormente pero creando el Trie usando el cuarto caracter de los valores de la clave en primer órden :


                                A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
                             +-----------------------------------------------------+
                             |0| |0| | | |0|0| |0|0|0| |0| | |0|0|0|0| | |0| |0|0|0|                                                                    --------- Nivel 1
                             +-----------------------------------------------------+
                                |   | | |     |       |   | |         | |   |
                                |   | | |     |       |   | |         | |   +--------------------------------------------------------------------+
                                |   | | |     |       |   | |         | +----------------------------------------------------------+             |
                                |   | | |     |       |   | |         +----------------------------------------------+             |             |
                                |   | | |     |       |   | +------------------------------------------+             |             |             |
                                |   | | |     |       |   +------------------------------+             |             |             |             |
     +--------------------------+   | | |     |       +--------------------+             |             |             |             |             |
     |             +----------------+ | |     +--------------+             |             |             |             |             |             |
     |             |             +----+ +------+             |             |             |             |             |             |             |
     |             |             |             |             |             |             |             |             |             |             |
***********   ***********   ***********   ***********   ***********   ***********   ***********   ***********   ***********   ***********   ***********
*thrasher *   *chickadee*   *cardinal *   *bluebird *   * goshawk *   *  gull   *   *  wren   *   * oriole  *   * bunting *   * thrush  *   *  godwit * --------- Nivel 2
***********   ***********   ***********   ***********   ***********   ***********   ***********   ***********   ***********   ***********   ***********

Si el juego de valores es conocido de antemano es posible realizar el estudio precedente, pero carece de sentido si el juego de valores es dinámico. En el caso de juego de valores dinámico, quizas la mejor Función Muestreo sea la segunda.

Cuarto ejemplo

Es tambien posible restringuir el número de niveles del Trie a un determinado número, por ejemplo, h. En este caso todos los sinónimos del nivel h-1 se ubican en mismo Nodo Hoja. El siguiente ejemplo crea un Trie con h = 3, usando porciones según el número de las porciones, desde la isquierda hacia la derecha, un caracter a la vez.


                                A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
                             +-----------------------------------------------------+
                             |0|0| | |0|0|0| |0|0|0|0|0|0|0| |0|0|0|0| |0|0| |0|0|0|                                   --------- Nivel 1
                             +-----------------------------------------------------+
                                  | |       |               |         |     |
                                  | |       |               |         |     +---------------------------------+
                                  | |       |               |         +-------------------------+             |
            +---------------------+ +---+   |               +---------------------+             |             |
            |                           |   +-----------------------+             |             |             |
            |                           |                           |             |             |             |
       +---------+                 +---------+                 +---------+   ***********   +---------+   ***********
       |         |                 |         |                 |         |   * oriole  *   |         |   *  wren   *   --------- Nivel 2
       +---------+                 +---------+                 +---------+   ***********   +---------+   ***********
          |   |                       |   |                       |   |                         |
     +----+   +----+             +----+   +----+             +----+   +----+                    |
     |             |             |             |             |             |                    |
***********   ***********   ***********   ***********   ***********   ***********          ***********
*bluebird *   * bunting *   *cardinal *   *chickadee*   * godwit  *   *  gull   *          *thrasher *                 --------- Nivel 3
***********   ***********   ***********   ***********   * goshawk *   ***********          * thrush  *
                                                        ***********                        ***********

Función Muestreo ( Sampling Function )

Es importante tomar conciencia de que los Tries pueden residir en disco, y por lo tanto, cuantos menos niveles tenga será mejor. Este objetivo de la estructura de datos nos lleva a la Función Muestreo que se use en cada caso en particular. La tarea a realizar es analizar distintas Funciones Muestreo y los Tries producidos por ellas, para determinar la más conveniente o la que produce el Trie con menos niveles, que nos lleva la Trie más eficiente, principalmente cuando el Trie reside en disco.
Para el ejemplo primero visto, la Función Muestreo produce un Trie de 5 niveles.
Para el ejemplo segundo visto, la Función Muestreo produce un Trie de 3 niveles.
Para el ejemplo tercero visto, la Función Muestreo produce un Trie de 2 niveles.
Para el ejemplo cuarto visto, la Función Muestreo produce un Trie de 3 niveles.

Algoritmo de Búsqueda


        boolean buscarValor( Trie arbol, String clave )
        {
                clave = clave.trim();                           // Limpio la clave adelante y atrás
                Trie proximoNodo = arbol;                       // Inicializo el proximo nodo con el raiz
                String tipoEntrada = "B";                       // Inicializo el tipo de entrada a B, ya que el raiz debe ser B
                int enlace = 0;                                 // Inicializo el enlace
                
                while( true )                                   // Salgo del loop por return o break
                {
                        if ( tipoEntrada.equals("B") )
                        {
                               recuperarSiguienteNodo();        // Navego el árbol
                        }
                        else if ( tipoEntrada.equals("L") )
                        {
                               break;                           // Arribo a nodo hoja	
                        }
                        else if ( tipoEntrada.equals("0") )
                        {
                               return false                    // La clave no existe en el árbol 
                        }
                        else
						{
						}
                }

                if( claveNodoHoja.equals(clave) )              // Análisis del Nodo Hoja
                {
                        return true;                           // La clave existe en el índice
                }
                else
                {
                        return false;                          // La clave no existe en el índice
                }
        }