Trie

Trie
Diseño y Análisis de Algoritmos
Boris Castillo Pizarro 24 de mayo de 2011

Índice:

Introducción…………………………………….……………………………...………………………… Pag. 2 Definición Trie.…………………………………………………………..……………………………… Pag. 3 Inserción Trie (árbol). …………………………………………………….…………………………… Pag. 4 Borrado Trie (árbol). ………………………………………………...………………………………… Pag. 5 Problema común..……………….…………………………………….………………………………… Pag.6 Conclusión……………………………………………………………………..………………………… Pag. 7 Referencias y Bibliografía..…………………………………………………..……………………… Pag. 8

Diseño y Análisis de Algoritmos – Universidad de La Serena

1

Introducción:

Cada vez que se requiere estructurar grandes conjuntos de datos siempre se busca la estructura de datos más adecuada para organizarlos y que a la vez facilite realizar operaciones sobreel conjunto con los menos costos y complejidad posibles. Una de estas estructuras es el Trie, una estructura de datos arbórea, que tiene la propiedad de ser sufijos (o prefijos), que permite encontrar una cadena dentro del conjunto en tiempo proporcional al largo de la cadena, versátil en aplicaciones de procesamiento de cadenas. A menudo se tiene que encontrar todas las apariciones de un patrón enun documento, se requiere corregir su ortografía, compresión de textos, problemas relacionados a la igualdad de cadenas “Algorithms String Matching”. Entre sus otras muchas aplicaciones está la de búsqueda de cadenas de coincidencia de patrones particulares en las secuencias de ADN, tema fundamental de la Bioinformática. Los motores de búsqueda en Internet, también las utilizan para encontrarpáginas Web relevantes para las consultas. Los tries son una de las estructuras de datos de propósito general más importantes en informática.

Diseño y Análisis de Algoritmos – Universidad de La Serena

2

Definición Trie:

Un trie sobre un conjunto S de strings distintos es un árbol etiquetado donde cada nodo representa un prefijo del conjunto y el nodo raíz representa el prefijo ε. Un nodo υque representa el prefijo Y es hijo de un nodo µ que representa el prefijo X sii Y = Xc para algún símbolo c que etiqueta la rama entre µ y υ. Se asume que todos los strings terminan con el símbolo especial $, no perteneciente en el alfabeto. Esto asegura que ningún string es prefijo de otro string en el conjunto, lo que garantiza que el árbol tiene exactamente |S| hojas. Un trie para el conjunto S ={S1,.., Sn} se puede construir en tiempo О(|S1| + ...+ |Sn|) mediante inserciones sucesivas de cada string en el árbol. Para buscar un patrón Ƥ, se parte de la raíz y se van siguiendo las ramas etiquetadas con los caracteres de Ƥ, lo que toma tiempo О(|Ƥ|).

Fig. Un nodo-vector trie de búsqueda para una lista de palabras.

Fig. Un nodo-árbol trie de búsqueda para una lista de palabras.Fig. Un nodo-lista trie de búsqueda para una lista de palabras.

Diseño y Análisis de Algoritmos – Universidad de La Serena

3

Inserción Trie (árbol): La inserción en un árbol trie se realiza con la entrada de un string donde cada letra da forma a un nodo. Mientras se va agregando un string, “CATCA” Fig, este se descompone de forma que la primera letra del string da forma al prefijo padre delstring, marcado el fin de la palabra con un signo $. Mientras haya una palabra entrante con prefijo existente en la estructura, el árbol va generando nuevas ramas con el substring faltante, letra a letra.

Fig. Presentación de los pasos en la construcción de un trie sufijo para la secuencia CATCA. “Bioinformática”

Diseño y Análisis de Algoritmos – Universidad de La Serena

4

BorradoTrie (árbol): El borrado se realiza mientras la palabra a eliminar exista, conservando los prefijos en común que existan.

La inserción y el borrado en los tries de listas y arrays se realizan de la misma forma, variando en los costos de memoria y complejidad.

Diseño y Análisis de Algoritmos – Universidad de La Serena

5

Problema común: String Matching (búsqueda en texto): El objetivo...