Codificación de Huffman

UNIVERSIDAD DE CUENCAdesde 1867

Miguel MacíasEdisson SiguaChristian Salinas

Algoritmo de compresión de HuffmanProgramación 3 Estructura de Archivos

Generalidades• Se utiliza para la comprensión o encriptación de datos.• Se basa en asignar códigos de distinta longitud de bits a cada uno de

los caracteres de un archivo.• Si se asignan códigos mas cortos a los caracteres que aparecen mas a

menudo se consigue una comprensión del archivo.• La compresión es mayor cuando la variedad de caracteres diferentes

que aparecen es menor.• Para recuperar el archivo original es necesario el código asignado a

cada carácter, así como su longitud en bits

Mecanismo del Algoritmo• Contar cuantas veces aparece cada carácter en el fichero a

comprimir y crear una lista enlazada con la información de caracteres y frecuencias

• Ordenar la lista de menor a mayor en función de la frecuencia

• Convertir cada elemento de la lista en un árbol

Mecanismo del Algoritmo• Fusionar todos estos arboles en uno único, de la siguiente manera:

• Con los dos primero arboles formar un nuevo árbol, cada uno de los arboles originales en una rama.

• Sumar las frecuencias de cada rama en le nuevo árbol.• Insertar el nuevo árbol en el lugar adecuado de la lista según la suma de

frecuencias obtenidas• Para asignar el nuevo código binario de cada carácter solo hay que

seguir el camino adecuado a través del árbol. Si se toma una rama cero, se añade un cero al código, de la misma manera con cualquier rama uno.

• Se recodifica el fichero según los nuevos códigos

EjemploSe toma una texto corto, como por ejemplo:

‘‘ata la jaca en la estaca’’Ahora se cuenta las veces que se repite cada carácter en el texto:

Ahora se ordena por frecuencia de menor a mayor:

‘ ’ a c e j l s t5 9 2 1 1 2 1 2

e j s c l t ‘ ’ a 1 1 1 2 2 2 5 9

EjemploAhora se considera a cada elemento como un nodo raíz un árbol.

e j s c l t ‘ ’ a (1) (1) (1) (2) (2) (2) (5) (9)


Ahora se unen los dos primero nodos (arboles), en un nuevo árbol, se suman sus frecuencias y se las coloca en el lugar correspondiente según el orden.

e j s c l t ‘ ’ a (1) (1) (1) (2) (2) (2) (5) (9)

e j (1) (1)


Ahora de unen los dos primero nodos (arboles), en un nuevo árbol, se suman sus frecuencias y se las coloca en el lugar correspondiente según el orden.

e j s c l t ‘ ’ a (1) (1) (1) (2) (2) (2) (5) (9)

s c l t ‘ ’ a(1) (2) (2) (2) (2) (5) (9)

e j (1) (1)

EjemploY se sigue el mismo proceso sucesivamente:

Los nuevos nodos (arboles) a unir serian s(1) y (2)

s c l t ‘ ’ a(1) (2) (2) (2) (2) (5) (9)

e j (1) (1)

Ejemplo

Nuevos nodos a unirse s (1) (2)

Ejemplo

Recordamos que (2) se divide en e(1) y j (1)

e j (1) (1)

s (1) (2)

Ejemplo

(3)

e j (1) (1)

s (1) (2)


Ahora se suman las frecuencias de s(1) (2)

Ejemplo

c l t ‘ ’ a (2) (2) (2) (3) (5) (9)

e j (1) (1)

s (1) (2)



Y agregamos según el orden que corresponda

Ejemplo

c l t ‘ ’ a (2) (2) (2) (3) (5) (9)

e j (1) (1)

s (1) (2)




Siguientes a unir

Ejemplo

c l(2) (2)

Nuevos nodos a unirse

Ejemplo

(4)

c l(2) (2)

Nuevos nodos a unirseAhora se suman las frecuencias de c(1) l(2)

Ejemplo

t ‘ ’ a (2) (3) (4) (5) (9)

e j(1) (1)

s (1) (2)

c l(2) (2)



Ejemplo

t ‘ ’ a (2) (3) (4) (5) (9)

e j(1) (1)

s (1) (2)

c l(2) (2)



Siguientes a unir

Ejemplo

t (2)

(3)Nuevos nodos a unirse

Ejemplo

t (2)

(3)

s (1) (2)

Recordamos que (3) se divide en s(1) y (2)


Ejemplo

t (2)

(3)

e j(1) (1)

s (1) (2)


Recordamos que (3) se divide en s(1) y (2)Recordamos que (2) se divide en e(1) y j(1)

Ejemplo

t (2)

(3)

e j(1) (1)

s (1) (2)

(5)



Ahora se suman las frecuencias de t(2) y (3)

Ejemplo

c l(2) (2)

t (2)

(3)

e j(1) (1)

s (1) (2)

‘ ’ a (4) (5) (5) (9)




Ahora se suman las frecuencias de t(2) y (3)

Ejemplo

c l(2) (2)

t (2)

(3)

e j(1) (1)

s (1) (2)

‘ ’ a (4) (5) (5) (9) Siguientes a unir

Ejemplo

(4) (5)


Ejemplo

c l(2) (2)

t (2)

(3)

e j(1) (1)

s (1) (2)

(4) (5)


(4) y (5) tiene subárboles binarios generados anteriormente

Ejemplo

c l(2) (2)

t (2)

(3)

e j(1) (1)

s (1) (2)

‘ ’ a (5) (9) (9) (4)

(5)Ahora se suman las frecuencias de (4) y (5), y se colocan en el orden especifico



Ejemplo

c l(2) (2)

t (2)

(3)

e j(1) (1)

s (1) (2)

‘ ’ a (5) (9) (9) (4)

(5)Siguientes a unir

Ejemplo

‘ ’ (5) (9) Nuevos nodos a unirse

Ejemplo

c l(2) (2)

t (2)

(3)

e j(1) (1)

s (1) (2)

‘ ’ (5) (9)

(4) (5)(5) y (9) tiene subárboles binarios generados anteriormente


Ejemplo

c l(2) (2)

t (2)

(3)

e j(1) (1)

s (1) (2)

‘ ’ (5) (9)

(4) (5)

a (9) (14)

Se suman las frecuencias de (5) y (9), y se colocan en el orden especifico



Ejemplo

c l(2) (2)

t (2)

(3)

e j(1) (1)

s (1) (2)

‘ ’ (5) (9)

(4) (5)

a (9) (14)Al tener finalmente dos arboles que unir, a(9) y (14), se suman sus frecuencias y se tiene creado el árbol para obtener las claves

c l(2) (2)

t (2)

(3)

e j(1) (1)

s (1) (2)

‘ ’ (5) (9)

(4) (5)

a (9) (14)

(23)

Resultado Final de la estructura del arbol

Se asigna las claves, las ramas a la izquierda son cero y a la derecha unos

Ejemplo

c l(2) (2)

t (2)

(3)

e j(1) (1)

s (1) (2)

‘ ’ (5) (9)

(4) (5)

a (9) (14)

(23)

Resultado Final de la estructura del arbol

Se asigna las claves, las ramas a la izquierda son cero y a la derecha unos

0

0

0

0 0

0

0

1

1

1

1 1

1

1

Ejemplo

c l(2) (2)

t (2)

(3)

e j(1) (1)

s (1) (2)

‘ ’ (5) (9)

(4) (5)

a (9) (14)

(23)0

0

0

0 0

0

0

1

1

1

1 1

1

1

EjemploCarácter - Clave

a 0 ' ' 10c 1100l 1101t 1110s 11110e 111110j 111111

Mas se repite ‘‘a’’ , menos se repite ‘‘e,s,j’’

El texto ‘‘ata la jaca a la estaca’’, transformado a binario mediante código ASCII, es igual a :01100001 01110100 01100001 00100000 01101100 01100001 00100000 01101010 01100001 01100011 01100001 00100000 01100001 00100000 01101100 01100001 00100000 01100101 01110011 01110100 01100001 01100011 01100001 Esta representado por 184 bits, es decir 23 bytes.

Ejemplo

Ejemploa 0

' ' 10c 1100l 1101t 1110s 11110

e 111110

j 111111

Se puede traducir ahora el texto mediante las claves generadas con Huffman.

a t a ' ' l a ' ' j a c a ' ' a ' ' l a ' ' e s t a c a

0 1110 0 10 1101 0 10 111111 0 1100 0 10 0 10 1101 0 10 111110 11110 1110 0 1100 0

Ejemploa t a ' ' l a ' ' j a c a ' ' a ' ' l a ' ' e s t a c a

0 1110 0 10 1101 0 10 111111 0 1100 0 10 0 10 1101 0 10 111110 11110 1110 0 1100 0

Finalmente se debe empaquetar los bits en grupos de 8, es decir bytes.

01110010 11010101 11111011 00010010 11010101 11110111 10111001 10000000

En total 8 bytes, mientras que el archivo original tenia 23

Conclusiones

• Huffman es una manera de lograr comprensión de la información sin perdidas de manera que la información enviada pueda llegar completa.

• Se tiene que conocer inicialmente las frecuencias de cada carácter en el archivo y ordenarlas para poder generar el árbol binario que nos ayuda a generar las claves de cada carácter

Conclusiones• La asignación de claves para cada carácter depende de la cantidad de

veces que se repita cada carácter en el texto.• Mientras se repita mas veces el carácter, tendrá una clave mas pequeña• Mientras menos se repita el carácter tendrá una clave mas grande.

• Independientemente del archivo a comprimir, lo que determina que tan compacto sea el archivo resultante, será el numero de veces que se repita los caracteres y símbolos que estén en el mismo:• El caso mas optimo para la codificación de Huffman es cuando la mayoría de caracteres se

repiten• El pero caso es cuando existe muy pocos o no se repiten ninguna carácter dentro del

archivo a comprimir

Codificación de Huffman

Software

Transcript of Codificación de Huffman