Algoritmos y Estructuras de Datos (VJ1215)
Curso 2023/2024
Algoritmos y Estructuras de Datos (VJ1215)
Curso 2023/2024
Aplicando el algoritmo de Huffman podemos llegar a esta codificación:
| carácter | frecuencia | codificación | bits |
|---|---|---|---|
| A | 0.4 | 0 | 1 |
| C | 0.1 | 110 | 3 |
| G | 0.1 | 111 | 3 |
| T | 0.4 | 10 | 2 |
En una secuencia de longitud n con esas frecuencias hay 0.4 · n Adenina, 0.1 · n Citosina, 0.1 · n Guanina y 0.4 · n Timina. Por tanto, con esa codificación la ocupación de la secuencia sería:
0.4 · n · 1 + 0.1 · n · 3 + 0.1 · n · 3 + 0.4 · n · 2 = 1.8 · n bits
Eso supone un ahorro del 10 % respecto de los 2 · n bits que ocuparía utilizando 2 bits por carácter.
El problema se resuelve empleando el algoritmo de Huffman, que construye un árbol binario para obtener la codificación óptima, el denominado árbol de Huffman. Cada hoja de ese árbol lleva asociado un carácter. Asignando 0 y 1, respectivamente, a descender al hijo izquierdo y a descender al hijo derecho, y recorriendo el camino desde la raíz hasta una hoja, se obtiene la codificación del carácter correspondiente.
El algoritmo de Huffman emplea internamente una cola de prioridad durante la construcción del árbol de Huffman, utilizando las frecuencias como prioridades para conseguir que los caracteres menos frecuentes acaben a mayor profundidad en el árbol y sean por tanto esos los que requieran más bits.
El algoritmo de Huffman es un ejemplo clásico de aplicación de la estrategia voraz.