Codigos de Нuffman

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

Ejemplo : Fichero con 100.000 caracteres. Se sabe que aparecen 6 caracteres diferentes y la frecuencia de aparición de cada uno de ellos es :

a b c d e f

Frecuencia

( en miles ) 45 13 12 16 9 5

¿ 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)

Fija 000 001 010 011 100 101

Solución 2 : Código de longitud variable en el que los más frecuentes tienen el código más corto. Restricción : ningún código es prefijo de otro.

( 224000 bits )

Variable 0 101 100 111 1101 1100

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.

Este sería el árbol binario de la codificación de longitud fija:

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 1. : Caracteres colocados en orden creciente de frecuencia.

Fase 2. y posteriores : Fusionar hasta obtener un sólo árbol manteniendo la ordenación creciente.

Implementación del algoritmo

Se usa una cola de prioridad, Q, con clave la frecuencia lo que permite seleccionar los dos objetos de la cola con la frecuencia más baja.

El resultado de fusionar dos objetos es un nuevo objeto cuya frecuencia es la suma de frecuencias de los dos objetos fusionados.

función COD_HUF ( C es conj_<car,frec> )

{ Pre : C está bien construido y no es vacio }

n := C;

CO:= ordenar_crec_por_frec(C) ;

/* se ordena crecientemente por frecuencia el conjunto de caracteres de la entrada */

Q := Insertar_todos (CO);

/* la cola contiene todos los elementos */

Para i=1 hasta n-1 hacer

z:= crear_objeto();

/* elección de los candidatos */

x := izq(z) := primero(Q); Q:= avanzar(Q);

y:= der(z) := primero(Q); Q:= avanzar(Q);

frec[z] := frec[x] + frec[y];

/* actualizar solución */

Q:= insertar_ordenado ( Q, z);

fpara

{ Post : Q contiene un único elemento que es un árbol de codificación de prefijo óptimo }

dev ( primero(Q))

ffunción

Demostración de optimalidad del criterio

• Sea T un árbol binario de codificación óptimo.

• Sean b y c dos hojas hermanas en T que se encuentran a profundidad máxima.

• Sean x e y dos hojas de T tales que son los 2 caracteres del alfabeto C con la frecuencia más baja.

árbol T

Vamos a ver que T, que es un árbol óptimo, se puede transformar en otro árbol T’’, también óptimo, en el que los 2 caracteres, x e y, con la frecuencia más baja serán hojas hermanas que estarán a la máxima profundidad  El árbol que genera el algoritmo voraz cumple exactamente esa condición.

Podemos suponer que f[b]  f[c] y que f[x]  f[y]. Además, se puede deducir que f[x]  f[b] y f[y]  f[c].

Se puede construir un nuevo árbol, T’, en el que se intercambia la posición que ocupan en T las hojas b y x.

árbol T’

B(T) – B(T’) = f[c].dT(c) – f[c].dT’(c) =

cC cC

= f[x].dT(x) + f[b].dT(b) –

f[x].dT’(x) – f[b].dT’(b) =

= f[x].dT(x) + f[b].dT(b) –

f[x].dT (b) –f[b].dT (x) =

= ( f[b] – f[x] ) . ( dT(b) – dT (x) )  0

De forma similar, se construye el árbol T’’ intercambiando c e y.

árbol T’’

Con este intercambio tampoco se incrementa el coste y B(T’)  B(T’’)  0.

Por tanto, B(T’’)  B(T) y como T es óptimo,

...