Post on 12-Jan-2017
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)
EjemploAhora se considera a cada elemento como un nodo raíz un árbol.
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)
EjemploAhora se considera a cada elemento como un nodo raíz un árbol.
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)
Recordamos que (2) se divide en e(1) y j (1)
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)
Recordamos que (2) se divide en e(1) y j (1)
Ahora se suman las frecuencias de 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)
Recordamos que (2) se divide en e(1) y j (1)
Ahora se suman las frecuencias de s(1) (2)
Y agregamos según el orden que corresponda
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)
Nuevos nodos a unirseAhora se suman las frecuencias de c(1) l(2)
Y agregamos según el orden que corresponda
Ejemplo
t ‘ ’ a (2) (3) (4) (5) (9)
e j(1) (1)
s (1) (2)
c l(2) (2)
Nuevos nodos a unirseAhora se suman las frecuencias de c(1) l(2)
Y agregamos según el orden que corresponda
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)
Nuevos nodos a unirse
Ejemplo
t (2)
(3)
e j(1) (1)
s (1) (2)
Nuevos nodos a unirse
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)
Nuevos nodos a unirse
Recordamos que (3) se divide en s(1) y (2)Recordamos que (2) se divide en e(1) y j(1)
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)
Y agregamos según el orden que corresponda
Nuevos nodos a unirse
Recordamos que (3) se divide en s(1) y (2)Recordamos que (2) se divide en e(1) y j(1)
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)
Nuevos nodos a unirse
Ejemplo
c l(2) (2)
t (2)
(3)
e j(1) (1)
s (1) (2)
(4) (5)
Nuevos nodos a unirse
(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
Nuevos nodos a unirse
(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)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
Nuevos nodos a unirse
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
(5) y (9) tiene subárboles binarios generados anteriormente
Nuevos nodos a unirse
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