CODIGOS DE HUFFMAN
Definición : La codificación de
Huffman es una técnica para la compresión
de datos, ampliamente usada y muy efectiva.
Fichero con 100.000 caracteres. Se sabe que aparecen
6 caracteres diferentes y la frecuencia de aparición de cada uno de ellos es :
¿Cómo codificar los caracteres para
comprimir el espacio ocupado utilizando
un código binario?
Solución 1: Código de longitud fija
Para 6 caracteres se necesitan 3 bits (300000 bits)
( 224000 bits )
Esta técnica de codificación se denomina código prefijo.
Codificación : Basta con concatenar el código
de cada uno de los caracteres.
Ejemplo :
aabacd º 0×0×101×0×100×111º 001010100111
Descodificación : Fácil porque ningún código
es prefijo de otro código Þ NO hay
ambigüedad.
Ejemplo :
101011101111011100 º badadcf
¡ Es la única posibilidad !
Un árbol binario es una forma de representar el código prefijo
que simplifica el proceso de descodificación :
- Las hojas son los caracteres.
- El camino de la raíz a la hojas con la interpretación 0 a la izquierda y 1 a la derecha nos da el código de cada hoja.
Y éste el de la
codificación de longitud variable :
Dado T
el árbol binario que corresponde a una codificación prefijo, es fácil
averiguar el número de bits necesarios para codificar el fichero :
Para cada carácter c diferente del alfabeto C
que aparece en el fichero,
- Sea f(c) la frecuencia de c en la entrada.
- Sea dT(c)la profundidad de la hoja c en el árbol T, entonces el número de bits requeridos es :
B(T) = å f(c)× dT(c)
cÎ C
B(T) nos da el coste de T.
Algoritmo Greedy
Huffman inventó un algoritmo voraz que construye una codificación prefijo óptima.
Construye un árbol binario de
códigos de longitud variable de manera ascendente de modo que [MIN] B(T).
Ejemplo de funcionamiento
Fase 2. y posteriores :
Fusionar hasta obtener un sólo árbol manteniendo la ordenación creciente
