Diccionarios y tries. - ALIPSO.COM: Monografías, resúmenes, biografias y tesis gratis.
Aprende sobre marketing online, desarrollo de sitios web gratis en Youtube
Suscribite para recibir notificaciones de nuevos videos:
Jueves 28 de Marzo de 2024 |
 

Diccionarios y tries.

Imprimir Recomendar a un amigo Recordarme el recurso

Diccionarios y tries, tipos de implementacioens para diccionarios y de estructuras para tries.

Agregado: 29 de AGOSTO de 2000 (Por ) | Palabras: 635 | Votar | Sin Votos | Sin comentarios | Agregar Comentario
Categoría: Apuntes y Monografías > Computación > Varios >
Material educativo de Alipso relacionado con Diccionarios tries
  • Diccionarios y tries.: Diccionarios y tries, tipos de implementacioens para diccionarios y de estructuras para tries.

  • Enlaces externos relacionados con Diccionarios tries

    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.


    Votar

    Ingresar una calificación para del 1 al 10, siendo 10 el máximo puntaje.

    Para que la votación no tenga fraude, solo se podrá votar una vez este recurso.

    Comentarios de los usuarios


    Agregar un comentario:


    Nombre y apellido:

    E-Mail:

    Asunto:

    Opinión:



    Aún no hay comentarios para este recurso.
     
    Sobre ALIPSO.COM

    Monografias, Exámenes, Universidades, Terciarios, Carreras, Cursos, Donde Estudiar, Que Estudiar y más: Desde 1999 brindamos a los estudiantes y docentes un lugar para publicar contenido educativo y nutrirse del conocimiento.

    Contacto »
    Contacto

    Teléfono: +54 (011) 3535-7242
    Email:

    Formulario de Contacto Online »