# TAD Trie _© F.J. Madrid Cuevas (fjmadrid@uco.es) Estructuras de Datos. Grado de Ingeniería Informática. Universidad de Córdoba. España_ ## Objetivos - Aprender a implementar el TAD Trie. - Aprender a compactar un Trie. - Aprender a usar el tipo std::map - Aprender a usar el tipo std::pair - Aprender a usar el tipo std::stack ## Descripción Un Trie [1] es un árbol multicamino especializado en recuperar las claves almacenadas basándose en prefijos. En un Trie todo nodo (salvo la raíz) representa un prefijo de clave formado por el camino desde la raíz a dicho nodo y el subárbol que tiene a dicho nodo como raíz almacena todas las clave que tienen como prefijo el definido por el nodo raíz. Ver Fig 1a. Aplicando el algoritmo canónico para crear un Trie insertando claves que hemos visto en clase, existirán subárboles compuestos por una sóla rama. Esto supone un desperdicio de memoria. La alternativa que vamos a implementar es compactar un Trie, ya creado de forma canónica, añadiendo una operación `Trie::compact()`. Esta operación realiza un recorrido post-fijo del Trie de forma que las cadenas de nodos que no son clave y tengan un solo hijo se compactan en un único nodo representando el string que se forma al contatenar los símbolos representados por la cadena de nodos compactada. Ver Fig 1b.
>
Trie no compactado Trie compactado
(a)
(b)
Figura 1. (a) Ejemplo de Trie tras insertar las claves "123", "123456", "123457", "123567", "123568", "2346", "2347" usando el algoritmo canónico. Los nodos oscuros indican que el prefijo de ese subárbol es una clave. (b) Versión compactada del Trie.
## Detalles de implementación ### Uso de un mapa para asociar un símbolo con un nodo Para representar el diccionario que asocia símbolo con nodo hijo vamos a utilizar el tipo std::map [2]. Vamos a asumir que se usa codificación utf-8 para los símbolos que forman las claves, esto significa que usaremos el tipo `std::string` ya que en utf-8 un símbolo puede ocupar entre 1 y 4 bytes (ver más adelante la codificación utf-8). ### Codificación UTF-8 de caracteres Nosotros utilizamos codificación UTF-8 de caracteres. Originalmente, el estándar ASCII utilizaba solo 7 bits (luego extendido a 8 bits en varios "Code Pages"). Con 8 bits, solo puedes representar 256 caracteres diferentes. Esto es suficiente para el alfabeto inglés, números y algunos símbolos. Sin embargo, es totalmente insuficiente para cubrir los alfabetos cirílico, griego, árabe, hebreo, y mucho menos los miles de ideogramas de los idiomas asiáticos (CJK: Chino, Japonés, Coreano) o los emojis modernos. El dilema está entonces en el balance eficiencia vs. la capacidad: si quisiéramos representar todos los caracteres del mundo con un tamaño fijo, tendríamos que usar UTF-32 (4 bytes por cada carácter). Problema: Un texto que solo contiene inglés ocuparía 4 veces más espacio del necesario. Solución Multibyte: Las codificaciones multibyte (como UTF-8) permiten que los caracteres comunes (ASCII) sigan ocupando 1 byte, mientras que los caracteres más complejos ocupan 2, 3 o hasta 4 bytes solo cuando es necesario. #### ¿Cómo funciona UTF-8?: auto sincronización" UTF-8 utiliza un diseño ingenioso donde los bits iniciales de cada byte te dicen qué está pasando: - Si un byte empieza por 0, es un carácter de 1 byte (ASCII). - Si empieza por 110, es el inicio de una secuencia de 2 bytes. - Si empieza por 1110, es de 3 bytes. - Si empieza por 11110, es de 4 bytes. - Los bytes de continuación siempre empiezan por 10. Esto permite que, si empiezas a leer un archivo por la mitad, el software pueda identificar rápidamente dónde empieza el siguiente carácter real, algo que no ocurría con codificaciones antiguas. #### ¿Cómo trabajos con secuencias UTF-8 en C++? Usando C++11, podemos usar el tipo `std::string` para representar cadenas codificadas con UTF-8, pero sabiendo que, por ejemplo, el carácter "🌎" tiene una longitud de 4 bytes. Con la llegada de C++20 y `std::u8string`, el lenguaje empieza a tratar estas secuencias con mayor semántica: - Iteradores especializados: Se busca que el programador no salte accidentalmente al medio de un carácter multibyte (lo que corrompería los datos). - Seguridad de Tipos: Al usar `char8_t`, el compilador te impide pasar por error una cadena UTF-8 a una función que espera ASCII puro. ## Referencias - [1] Trie: http://en.wikipedia.org/wiki/Trie - [2] std::map: http://www.cplusplus.com/reference/map/map/ - [3] std::pair: https://www.cplusplus.com/reference/utility/pair/pair/ - [4] std::stack: http://www.cplusplus.com/reference/stack/stack/ - [5] Manipuladores de flujo: https://www.cplusplus.com/reference/library/manipulators/ - [6] Tipos estándar para enteros: https://www.cplusplus.com/reference/cstdint/