Huffman
Páginas: 7 (1703 palabras)
Publicado: 25 de noviembre de 2014
ANÁLISIS DE ALGORITMOS
ANÁLISIS DEL ALGORITMO DE HUFFMAN
POR
ALONSO RIVERA EDUARDO
DÍAZ CRUZ DULCE MARÍA CLARET
RODRÍGUEZ PALACIO REYNALDO
ALGORITMO DE COMPRESIÓN DE HUFFMAN
Generalidades:
Se trata de un algoritmo que puede ser usado para compresión o encriptación de datos.
Este algoritmo se basa en asignar códigos de distinta longitud de bits a cada uno de loscaracteres de un fichero. Si se asignan códigos más cortos a los caracteres que aparecen más a
menudo se consigue una compresión del fichero.
Esta compresión es mayor cuando la variedad de caracteres diferentes que aparecen es menor. Por ejemplo: si el texto se compone únicamente de números o mayúsculas, se conseguirá una compresión mayor.
Para recuperar el fichero original esnecesario conocer el código asignado a cada carácter,
así como su longitud en bits, si ésta información se omite, y el receptor del fichero la conoce, podrá recuperar la información original. De este modo es posible utilizar el algoritmo
para encriptar ficheros.
Ejemplo: Se tiene un archivo con 100,000 caracteres. Se sabe que aparecen 6 caracteres diferentes y la frecuencia de aparición de cada unode ellos es:
Caracter (c)
Frecuencia
(en miles)
a
b
c
d
e
f
45
13
12
16
9
5
La pregunta que surge 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, lo que implica que por todo el archivo serían 300000 bits.
Fija
000
001010
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. El archivo ocuparía 224000 bits con la siguiente codificación.
Variable
0
101
100
111
1101
1100
Esta técnica de codificación se denomina código prefijo.
Para la codificación: Basta con concatenar elcódigo de cada uno de los caracteres.
Ejemplo :
aabacd 001010100111 001010100111
Decodificación: Es 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
decodificació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:
100
0
1
86
14
1
0
58
0
a : 45
0
28
1
b : 13
0
c : 12
14
1
d : 16
0
e:9
1
f:5
Y éste el de la codificación de longitud variable:
100
1
0
a : 45
55
10
25
30
1
0
c : 12
1
0
14
b : 13
d : 16
1
0
f:5
e:9
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.
f:5
e:9
c : 12b : 13
d : 16
a : 45
Fase 2 (y posteriores): Fusionar hasta obtener un sólo árbol manteniendo la ordenación creciente.
c : 12
b : 13
d : 16
14
0
f:5
1
e:9
a : 45
d : 16
14
f:5
c : 12
e:9
25
c : 12
b : 13
a : 45
30
1
0
1
0
1
0
a : 45
25
1
0
14
b : 13
d : 16
1
0
f:5
e:9
a : 45
55
10
25
0
c : 12
30
1
1
0
14
b : 13
0
f:5
d : 16
1
e:9
100
1
0
a : 45
55
1
0
25
30
1
0
c : 12
1
0
14
b : 13
d : 16
1
0
f:5
e:9
ANÁLISIS DEL PROBLEMA
Entrada:
Una lista ligada en la cual cada nodo tiene 2 campos, uno es el caracter y otro es la frecuencia.
Esta lista debe estar ordenada ascendentemente de...
ANÁLISIS DEL ALGORITMO DE HUFFMAN
POR
ALONSO RIVERA EDUARDO
DÍAZ CRUZ DULCE MARÍA CLARET
RODRÍGUEZ PALACIO REYNALDO
ALGORITMO DE COMPRESIÓN DE HUFFMAN
Generalidades:
Se trata de un algoritmo que puede ser usado para compresión o encriptación de datos.
Este algoritmo se basa en asignar códigos de distinta longitud de bits a cada uno de loscaracteres de un fichero. Si se asignan códigos más cortos a los caracteres que aparecen más a
menudo se consigue una compresión del fichero.
Esta compresión es mayor cuando la variedad de caracteres diferentes que aparecen es menor. Por ejemplo: si el texto se compone únicamente de números o mayúsculas, se conseguirá una compresión mayor.
Para recuperar el fichero original esnecesario conocer el código asignado a cada carácter,
así como su longitud en bits, si ésta información se omite, y el receptor del fichero la conoce, podrá recuperar la información original. De este modo es posible utilizar el algoritmo
para encriptar ficheros.
Ejemplo: Se tiene un archivo con 100,000 caracteres. Se sabe que aparecen 6 caracteres diferentes y la frecuencia de aparición de cada unode ellos es:
Caracter (c)
Frecuencia
(en miles)
a
b
c
d
e
f
45
13
12
16
9
5
La pregunta que surge 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, lo que implica que por todo el archivo serían 300000 bits.
Fija
000
001010
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. El archivo ocuparía 224000 bits con la siguiente codificación.
Variable
0
101
100
111
1101
1100
Esta técnica de codificación se denomina código prefijo.
Para la codificación: Basta con concatenar elcódigo de cada uno de los caracteres.
Ejemplo :
aabacd 001010100111 001010100111
Decodificación: Es 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
decodificació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:
100
0
1
86
14
1
0
58
0
a : 45
0
28
1
b : 13
0
c : 12
14
1
d : 16
0
e:9
1
f:5
Y éste el de la codificación de longitud variable:
100
1
0
a : 45
55
10
25
30
1
0
c : 12
1
0
14
b : 13
d : 16
1
0
f:5
e:9
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.
f:5
e:9
c : 12b : 13
d : 16
a : 45
Fase 2 (y posteriores): Fusionar hasta obtener un sólo árbol manteniendo la ordenación creciente.
c : 12
b : 13
d : 16
14
0
f:5
1
e:9
a : 45
d : 16
14
f:5
c : 12
e:9
25
c : 12
b : 13
a : 45
30
1
0
1
0
1
0
a : 45
25
1
0
14
b : 13
d : 16
1
0
f:5
e:9
a : 45
55
10
25
0
c : 12
30
1
1
0
14
b : 13
0
f:5
d : 16
1
e:9
100
1
0
a : 45
55
1
0
25
30
1
0
c : 12
1
0
14
b : 13
d : 16
1
0
f:5
e:9
ANÁLISIS DEL PROBLEMA
Entrada:
Una lista ligada en la cual cada nodo tiene 2 campos, uno es el caracter y otro es la frecuencia.
Esta lista debe estar ordenada ascendentemente de...
Leer documento completo
Regístrate para leer el documento completo.