DICCIONARIOS Y TRIES

CARLOS H. HINCAPIE

SERGIO A. HERRERA

Materia: Análisis de Algoritmos

Profesor: Alberto Restrepo

Fecha: Abril 13 de 1999

MEDELLIN

DEPARTAMENTO DE INFORMATICA

UNIVERSIDAD EAFIT

INTRODUCCION

Este trabajo será realizado como un resumen de la exposición que presentaremos el día 13 de abril en la clase de análisis de algoritmos.

En este trabajo trataremos de presentar los conceptos de DICCIONARIOS y TRIES lo mas claramente posible.

DICCIONARIOS

A menudo cuando diseñamos una estructura para la implementación de un algoritmo, no son necesarias operaciones poderosas y a su vez complicadas como la unión e intersección. Por lo general lo único que necesitamos es mantener un conjunto de objetos <<Actuales>>, para lo cual necesitamos operaciones como inserciones y supresiones periódicas en el conjunto. Con cierta frecuencia también necesitamos operaciones como saber si un elemento particular esta en el conjunto. A este tipo estructura la hemos llamado diccionario. Y definimos unas operaciones INSERTAR, SUPRIME y MIEMBRO se incluirá también ANULA para inicializar un diccionario.

Tipos de implementaciones de un diccionario:

1.      Un diccionario puede implementarse mediante una lista enlazada.

2.       Otra forma es mediante un vector.

3. Y una posible tercer forma seria implementarlo como un arreglo de longitud fija con un apuntador a la ultima entrada del arreglo en uso. Esta solución es factible si se puede suponer que los conjuntos nunca serán mas grandes que la longitud del arreglo. Tiene la ventaja de la sencillez de la representación con listas enlazadas, mientras sus desventajas son: 1) los conjuntos no pueden crecer arbitrariamente, 2) la supresión es mas lenta, 3) el tamaño no se utiliza de forma eficiente si los conjuntos son de tamaño variable.

TRIES

Es una estructura para representar conjuntos de cadenas de caracteres. El mismo método funciona para la representación de tipos de datos que son cadenas de objetos de cualquier tipo, como las cadenas de enteros.

Ejemplo:

En este trie, cada camino de la raíz a una hoja corresponde a una palabra del conjunto representado. De esta forma los nodos del trie corresponden a los prefijos de las palabras del conjunto. Para evitar confusión entre palabras como ello y ellos, se añade un símbolo especial ($) al final de todas las palabras.

Dicho trie representa el conjunto de las palabras {THE, THEN, THIN, THIS, TIN, SIN, SING}.

Observaciones:

ü      Cada nodo tiene hasta 27 hijos, uno para cada letra y $.

ü      La mayor parte de los nodos tiene mucho menos de 27 hijos.

ü      Una hoja que sigue a una arista etiquetada con $ no puede tener hijos e incluso podría no existir.

NODOS DE UN TRIE COMO TDA:

Un nodo de trie puede considerarse como una correspondencia cuyo dominio es {A, B, ....., Z, $} (o cualquier alfabeto que se escoja) y cuyo  conjunto de valores es de tipo <<apuntador a nodo de trie>>. Más aún, el trie puede identificarse con su propia raíz, por lo que los TDA TRIE y NODO_TRIE tienen el mismo tipo de datos , aunque sus operaciones son un poco diferentes. En un NODO_TRIE se necesitan las siguientes

Operaciones:

1)     ASIGNA (nodo, c, p) que asigna el valor p (un apuntador a un nodo) al carácter c de nodo.

2)     VALOR_DE (nodo, c) que produce el valor asociado con el carácter c de nodo.

3)     TOMA_NUEVO (nodo, c) para hacer que el valor de nodo para el carácter c apunte a un nodo nuevo.

BIBLIOGRAFIA

ü      Estructura de datos y algoritmos, de Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, Editorial Addison-Wesley Iberoamericana, Pg 118-122, 165-171.

ü      Datos encontrados en Internet.