03 Codigo de Huffman
03 Codigo de Huffman
03 Codigo de Huffman
Objetivos del tema El algoritmo del cdigo de Huffman Cdigos de Huffman de mnima varianza Cdigos de Huffman Adaptativos Procedimiento de codificacin Procedimiento de decodificacin Procedimiento de actualizacin (*) Cdigos de Golomb (*)Cdigo Tunstall Aplicaciones del cdigo de Huffman Resumen Bibliografa
Contenidos
Apndice: Longitud del cdigo de Huffman y cdigo de Huffman extendido (*) Estas secciones son ilustrativas, no entran en el examen
Rafael Molina Tema 3: Codificacin Huffman
Rafael Molina
El cdigo de Huffman est basado en dos propiedades de los cdigos prefijo ptimos: 1. En un cdigo prefijo ptimo, los smbolos ms frecuentes los que tienen mayor probabilidad- tienen palabras del cdigo ms cortas que las palabras menos frecuentes. 2. En un cdigo prefijo ptimo, los dos smbolos que ocurren con menos frecuencia tendrn la misma longitud.
Para probar la segunda condicin usaremos reduccin al absurdo. Supongamos que existe un cdigo prefijo ptimo, C, en el que los dos smbolos menos probables no tienen la misma longitud. Sean P1 y P2 las correspondientes palabras del cdigo y supongamos que long(P1)=k y long(P2)=n con k<n. Al ser un cdigo prefijo, P1 no puede ser prefijo de P2. Por tanto podemos suprimir los n-k ltimos dgitos de P2 y tener an dos cdigos distintos. Sea C el nuevo cdigo, sigue siendo prefijo?
Rafael Molina Tema 3: Codificacin Huffman 6
Como estos smbolos son los menos probables ninguna otra palabra puede ser ms larga que estas dos y por tanto no hay peligro de que al hacer ms corta esta palabra del cdigo (la de P2) se convierta en prefijo de ninguna otra. Por tanto, C sigue siendo prefijo. Hemos creado un nuevo cdigo, C, que hace que C no sea ptimo, lo que contradice la hiptesis inicial sobre C. Para construir el cdigo de Huffman le aadimos la siguiente condicin a las dos propiedades vistas de los cdigos prefijo ptimos: Si u y v son los dos smbolos menos probables en el alfabeto, si la codificacin de u es m*0, la de v ser m*1. Donde m es una hilera de ceros y unos y * denota concatenacin.
Rafael Molina Tema 3: Codificacin Huffman 7
probabilidades
1.0 1
Probabilidades acumuladas
Smbolo
Smbolo
Cdigo
0 10
Rafael Molina
110 E 111
probabilidades 0
Otro ejemplo
A B C D
1.0 1
0.4
B 01
C 10
D 11
Rafael Molina
10
probabilidades
Otro ejemplo
B A C D E
B A C D E
Para decodificar una secuencia de palabras slo tenemos que recorrer el rbol del cdigo prefijo correspondiente al cdigo Huffman como vimos en el captulo anterior.
Rafael Molina Tema 3: Codificacin Huffman 11
Para disminuir la varianza colocamos, en caso de empate en las probabilidades de los nodos, los nodos ya utilizados lo ms alto posible procurando utilizarlos lo ms tarde posible. Retomemos el ejemplo de la seccin anterior.
probabilidades
B A C D E
0 0 0.6 1 1.0
0.4
1 1 0.2
Tema 3: Codificacin Huffman
B A C D E
00 10 11 010 011
13
Rafael Molina
Consideremos un rbol binario correspondiente a un alfabeto de tamao n en el que los smbolos del alfabeto son las hojas. Entonces, el nmero de nodos del rbol es 2n-1 (prubalo por induccin). A cada nodo del rbol binario le vamos a asignar dos campos: Nmero del nodo y peso del nodo. El nmero de nodo es un nmero nico asignado a cada nodo del rbol entre 1 y 2n-1. Los nmeros los notaremos y1,,y2n-1. El peso de un nodo hoja es simplemente el nmero de veces que aparece el smbolo correspondiente y el de uno interno la suma de los pesos de sus dos hijos. Los pesos los notaremos x1,,x2n-1.
Rafael Molina Tema 3: Codificacin Huffman 15
Puede probarse que: Si al asignar nmeros a los nodos comenzando por el uno y recorriendo el rbol por niveles (asignamos, de izquierda a derecha en cada nivel y de las hojas (abajo) a la raz (arriba) los pesos de los nodos quedan ordenados en un orden no decreciente
El rbol obtenido es un rbol binario correspondiente a un cdigo de Huffman para dichos smbolos con las probabilidades de cada nodo hoja igual a su peso dividido por la suma de los pesos. La propiedad anterior recibe el nombre de sibling property o node number invariant.
Rafael Molina Tema 3: Codificacin Huffman 16
En el ejemplo de la derecha: Entre parntesis los pesos de cada nodo. Dentro de los cuadrados el nmero asignado a cada nodo. Por tanto, este rbol es el correspondiente al cdigo de Huffman para estos smbolos con las probabilidades que se obtienen a partir del nmero de veces que ha aparecido cada smbolo dividido por el nmero de smbolo ledos.
Rafael Molina
9 7 5
(7)
(16)
8 6
(4)
(9)
(3)
(1)
(2)
(2)
(2)
17
En el cdigo Huffman adaptativo ni el transmisor ni el receptor conocen al principio las probabilidades de los smbolos. Por eso: 1. Codificador y decodificar comienzan con un rbol con un nodo nico que corresponde a todos los smbolos no transmitidos (NYT) y que tiene peso cero. 2. Mientras progresa la transmisin se aadirn nodos al rbol correspondientes a smbolos que aparezcan por primera vez, se modificarn los pesos (tanto si el smbolo es nuevo como si es ya existente) y se actualizar el rbol para que siga cumpliendo the sibling property (siga siendo de Huffman).
Rafael Molina Tema 3: Codificacin Huffman 18
El algoritmo de Huffman adaptativo consta de los siguientes elementos: 1. Inicializacin (la decodificador). misma para el codificador y
2 Algoritmo de codificacin. 3. Algoritmo de decodificacin. 4. Proceso de actualizacin del rbol para que mantenga the sibling property. Antes de describir estas partes comentaremos brevemente sobre la codificacin de los smbolos:
Rafael Molina Tema 3: Codificacin Huffman 19
Codificacin de un smbolo que aparece por primera vez: Salvo que sea el primero de todos lo smbolos de la secuencia, la codificacin de un smbolo que aparece por primera vez consta de la codificacin que proporciona el rbol del nodo NYT seguido de un cdigo fijo para el smbolo que deben conocer codificador y decodificador En el caso en que sea el primer smbolo que aparece en la secuencia no necesitamos transmitir el cdigo de NYT. Si el smbolo ya ha aparecido Utilizamos la codificacin que proporciona el rbol que vamos construyendo.
Rafael Molina Tema 3: Codificacin Huffman 20
1. Nuestro rbol ha de codificar n+1 smbolos incluyendo el correspondiente a NYT, 2. Necesitamos por tanto 2(n+1)-1=2n+1 nmeros para los nodos, 3. El rbol de Huffman inicial tiene un nodo nico:
peso
0
NYT
Rafael Molina
2n+1
el
23
Rafael Molina
24
Ejemplo
Consideremos el alfabeto A={a,b,c,d} y realicemos la codificacin de la secuencia aabcdad Primero vemos el nmero de nodos que necesitaremos Nodos=2*4+1=9
000
001
010
011
25
Inicializacin
0
NYT
aabcdad en A={a,b,c,d}
1
7
0
a
26
0 0 0
NYT 7
1 1
a 8
1 0 0
NYT
Tema 3: Codificacin Huffman
1
7
1
a
Rafael Molina
27
aabcdad Tenemos 0 0
NYT 7
1 1
a 8
salida=000
1
7
1
a
28
1 0 0
NYT 7
1 2
a 8
2 0 0
NYT
Tema 3: Codificacin Huffman
1
7
2
a
Rafael Molina
29
aabcdad Tenemos 0 0
NYT 7
1 2
a 8 Cdigo de NYT
salida=0001
9
salida=00010001 1 2
8 a Cdigo de b
1
5
0
b
6
30
2 0 0 0 0
NYT 5 7
2 1 2
8 a
0 1 0 0
5 7
1 2 1 1
b 6 a 8
1 1
b 6
3 0 1
7
NYT
1 2 1
a 6 8
0 0
NYT
Rafael Molina
1
b
Cdigo de NYT
salida=0001000100010 3 0 1 2
8 9
1
7
c 8
1 0 0 0 0
NYT 3 5
2 1 1
6 a
0 0
NYT
Rafael Molina
1
5
a 6
1
b
1 0
c
b 4
32
0 1 0 0
NYT
3
7
1 2
a
0
8
3
7
1 2
8 a
0 0
3
1 1
c
1 1
b 4
1 0 1 0 0
3 5
1 1 1 1
c b 4
0 2 0 1
3 5
3
7
NYT
1 2
a
0 2
5
4
7
1 2
a
1 1 1 1
c b 4
0 0
NYT
0 0
NYT
0 1
3
1 1
c
1 1
b 4
Rafael Molina
aabcdad Tenemos
salida=0001000100010000011 0 2
8
salida=0001000100010 4
7 9
4
7
d 1 2
a 8
0 2 0 1
3 5
1 2
a
0 0
NYT
1 1
c
1 1
b 4
0 0 0 0
NYT
0 1
3
1 1
c
1 1
b 4
1 0
d
2
34
Rafael Molina
0 2 0 1
3 5
4
7
1 2
a
0 2 0 1
3 5
4
7
1 2
a
0 0 0 0
NYT
1 1
c
1 1
b 4
0 1 0 0
NYT
1 1
c
1 1
b 4
1 1
d
1 1
d
Rafael Molina
0 2 0 1
3 5
4
7
1 2
a
0 1 0 0
NYT
1 1
c
1 1
b 4
0 2 0 1
b 5
4
7
1 2
a
0 1
1 1
3
1 1
c 4
1 1
d
0 0
NYT
1 1
d
CAMBIO DE ORDEN
Rafael Molina Tema 3: Codificacin Huffman
0 2 0 1
b 5
4
7
1 2
a
0 2 0 1
b 5
4
7
1 2
a
0 1
1 2
3
1 1
c 4
0 1
1 2
3
1 1
c 4
0 0
NYT
1 1
d
0 0
NYT
1 1
d
Rafael Molina
0 2
a
4
7
1 2
5
0 2
6 a
4
7
1 3
5
0 1
b
0 1
1 2
3
1 1
c 4
0 1
b
0 1
1 2
3
1 1
c 4
0 0
NYT
1 1
d
0 0
NYT
1 1
d
CAMBIO DE ORDEN
Rafael Molina Tema 3: Codificacin Huffman
0 2
a
5
7
1 3
5
0 1
b
0 1
1 2
3
1 1
c 4
0 0
NYT
1 1
d
Rafael Molina
aabcdad
5
7
1 3
5
0 2
6 a
5
7
1 3
5
0 1
b
0 1
1 2
3
1 1
c 4
0 1
b
0 1
1 2
3
1 1
c 4
0 0
Rafael Molina
1 1
d
2
Tema 3: Codificacin Huffman
0 0
NYT
1 1
d
2
40
NYT
0 3
a
5
7
1 3
5
0 3
6 a
6
7
1 3
5
0 1
b
0 1
1 2
3
1 1
c 4
0 1
b
0 1
1 2
3
1 1
c 4
0 0
NYT
1 1
d
0 0
NYT
1 1
d
Rafael Molina
41
aabcdad Tenemos
salida= 00010001000100000110 0 3
a
6
7
1 3
5
6
7
1 3
5
0 1
b
0 1
1 2
3
1 1
c 4
0 1
b
0 1
1 2
3
1 1
c 4
0 0
Rafael Molina
1 1
d
2
Tema 3: Codificacin Huffman
0 0
NYT
1 1
d
2
42
NYT
0 3
a
6
7
1 3
5
0 3
6 a
6
7
1 3
5
0 1
b
0 1
1 2
3
1 1
c 4
0 1
d
0 1
1 2
3
1 1
c 4
0 0
NYT
1 1
d
0 0
NYT
1 1
b
Observar cambio
Rafael Molina Tema 3: Codificacin Huffman 43
0 3
a
6
7
1 3
5
0 3
6 a
6
7
1 3
5
0 2
d
0 1
1 2
3
1 1
c 4
0 2
d
0 1
1 2
3
1 1
c 4
0 0
NYT
1 1
b
0 0
NYT
1 1
b
Rafael Molina
44
0 3
a
6
7
1 4
5
0 3
6 a
7
7
1 4
5
0 2
d
0 1
1 2
3
1 1
c 4
0 2
d
0 1
1 2
3
1 1
c 4
0 0
NYT
1 1
b
0 0
NYT
1 1
b
Rafael Molina
45
Ejercicio: Usando el cdigo fijo a=000, b=001, c=010, d=011 Decodificar la secuencia 00110000 usando el cdigo de Huffman adaptativo. Aunque el cdigo de Huffman es uno de los mtodos de codificacin de longitud de palabra variable ms conocidos, existen otros mtodos algo menos conocidos pero tambin muy tiles. En particular los mtodos de Golomb-Rice y Tunstall que veremos a continuacin.
Rafael Molina Tema 3: Codificacin Huffman 46
Rafael Molina
47
Ejemplos de estos modelos son: 1. A es que salga cara al lanzar una moneda y Ac es obviamente que salga cruz. 2. En el problema del agente 00111 de Golomb (ver material adicional) el suceso Ac es que salga el cero en la ruleta y A es que no salga (la ruleta tiene los nmeros del 0 al 36). 3. Puntos en blanco y negro como podra ser el contenido de una hoja.
Rafael Molina
48
1. Observa que para la ruleta P(A)=36/37 y P(Ac)=1/37. 2. En el caso de la moneda (si no est sesgada) P(A)=P(Ac)=1/2. 3. En el caso de hojas en blanco y negro se podra estimar p. Los fabricantes de impresoras suponen p=0.05 Lo que queremos codificar son las realizaciones de la variable aleatoria N definida por N= nmero de veces que aparece A antes de que aparezca Ac. Esta variable tiene la siguiente distribucin de probabilidad P(N=n)=pnq n=0,1,2,.
Rafael Molina Tema 3: Codificacin Huffman 49
Una posible codificacin sera: Cada vez que aparezca el suceso A lo codificamos con un uno y cuando se produzca el suceso Ac lo codificamos con un cero. De esta forma el valor n de la variable aleatoria N se codifica mediante n unos seguidos de un cero. Es decir, N cdigo 0 1 2 3 . . 0 10 110 1110 . . Este cdigo recibe el nombre de cdigo unario. Cul es el nmero medio de bits que este cdigo, C, usa para codificar la variable N?
Tema 3: Codificacin Huffman 50
Rafael Molina
C p ( N ) = (n + 1)qp = q p + q np
n n n =0 n =0 n =0
q q n 1 n = + qp np = + pq deriv p 1 p 1 p n =0 n =0
q 1 1 = + pq = 2 1 p (1 p ) 1 p
Recuerda que q=1-p
Observa que si p est muy prximo a uno Cp(N) es muy grande. Cunto vale la entropa de la variable aleatoria N en funcin de p?.
Rafael Molina Tema 3: Codificacin Huffman 51
( )
Observa que para p grande deberamos ser capaces de mejorar el cdigo unario. Sin embargo, para p=0.5, Cp(N) Hp(N)=0 y el cdigo unario es el mejor que podemos utlizar.
Rafael Molina Tema 3: Codificacin Huffman 53
Veamos la idea del cdigo de Golomb intuitivamente. Supongamos que tenemos una racha de apariciones de A de longitud n1 y otra racha de apariciones de A de longitud n2(>n1) cuya probabilidad es la mitad. Cmo estn relacionados n2 y n1?.
P( N = n2 ) = qp n2 = q 2 n2 log p
de donde o
Rafael Molina
n2 log p = 1 + n1 log p
1 n2 = n1 = n1 + log p 1 log p
Muy importante
54
Intutivamente, nos gustara que el cdigo de n2 fuese un bit ms largo que el de n1. Esto es lo que consigue el cdigo de Golomb. Antes un poco de notacin
x = entero ms prximo a x por abajo x = entero ms prximo a x por arriba 3.5 = 3 3.5 = 4
Continuemos con el cdigo de Golomb. Sea
Rafael Molina
1 w = log p
55
n Q= w
y R = n Qw
En otras palabras Q es el cociente y R es el resto de la divisin de n por w (Observa que si n=n+w entonces Q=Q+1) La codificacin de Golomb para n consiste en: 1. un prefijo unario (para el cociente, es decir para Q), 2. y un sufijo binario (para el resto, R) usando
* Este cdigo va a ser mejorado despus
Rafael Molina Tema 3: Codificacin Huffman 56
* log w bits
w = 4, log w = 2
N 0 1 2 3 4 5 6
Rafael Molina
Q 0 0 0 0 1 1 1
R 0 1 2 3 0 1 2
w = 5, log w = 3
N 0 1 2 3 4 5 6
Rafael Molina
Q 0 0 0 0 0 1 1
R 0 1 2 3 4 0 1
La parte sufijo del cdigo es mejorable cuando w no sea una potencia de 2, si usamos la siguiente representacin de longitud variable: Sea R {0,1,,w-1}
Rafael Molina
59
Ejemplos: w=2 0 0
Resto R 0 1
w=3 1 1
Representacin 0 1 Resto R 0 1 2 Los arcos determinan el cdigo Los nodos contienen el resto
0 0 0 1
Representacin 0 10 11
1 2
Rafael Molina
60
1 1 0 1 2
w=4
0 1 0 0
Resto R 0 1 2 3 4
1 1 1
w=5
0 2 0 3
1 1 4
Representacin 00 01 10 11
Rafael Molina
61
w = 5, log w = 3
C D I G O G O L L U B
Rafael Molina
N 0 1 2 3 4 5 6
Q 0 0 0 0 0 1 1
R 0 1 2 3 4 0 1
Cdigo de Tunstall
Supongamos que tenemos inicialmente m smbolos y queremos usar como salida representaciones de longitud fija con n bits, siendo 2n>m. Suponemos que las realizaciones de dichos smbolos son independientes. Construccin del rbol: Formar un rbol con una raz y m hijos con arcos etiquetados con los smbolos del alfabeto, Si el nmero de hojas del rbol, l, cumple l+(m-1)< 2n seguir, en caso contrario parar.* Encontrar la hoja con mayor probabilidad (la probabilidad es el producto de las probabilidades de los smbolos del camino de la raz a las hojas) y expandirla para que tenga m hijos. Volver al paso anterior,
Rafael Molina Tema 3: Codificacin Huffman 63
*Justificacin de la condicin de parada: Veamos cuantos hojas tiene el rbol, Si en un instante tiene l hojas, para expandir le quitamos una y de esa una salen m. Por tanto una vez realizada la expansin tenemos l-1+m que necesitaremos que sea menor que 2n ya que necesitamos dejarnos al menos un cdigo libre como ya veremos.
Una vez construido el rbol le asignamos un cdigo de longitud n a cada una de las hojas.
Rafael Molina Tema 3: Codificacin Huffman 64
Supongamos que P(A)=0.6, P(B)=0.3 y P(C)=0.1 y n=3. Por tanto, deseamos generar una representacin de longitud fija 3. Paso 1
A 0.6
B 0.3
C 0.1
Rafael Molina
65
B 0.3
C 0.1
0.36
Rafael Molina
0.18
0.06
66
Rafael Molina
67
B 101
C 110
B C 011
100
000
Rafael Molina
001
010
68
Qu ocurre si queremos codificar la secuencia AA?. AA no tiene representacin. Para codificar el AA enviamos el cdigo no utilizado (111) y un cdigo fijo para AA. Generalmente, si hay k nodos internos en el rbol necesitaremos k-1 cdigos fijos. En nuestro problema A y AA.
69
Otro ejemplo. Supongamos P(A)=0.9 y P(B)=0.1 y usamos n=2. El rbol que construiramos sera Entrada AA AB B Salida 00 01 10 A 00 Y dejaramos el 11 para enviar el cdigo de A
Rafael Molina Tema 3: Codificacin Huffman 70
B 10 01
Si ussemos las cuatro palabras tendramos Entrada AAA AAB AB B Salida 00 01 10 11 A 00 y no podramos enviar cdigo para A
Rafael Molina Tema 3: Codificacin Huffman 71
B 11 10
B 01
Problema: considera la tabla en la que el cdigo 111 es utilizado para anunciar que a continuacin viene el cdigo de A o AA. Entrada AAA AAB AAC AB AC B C
Rafael Molina
72
Texto: Usaremos diferentes tipos de texto y aplicaremos Huffman habiendo calculado antes las probabilidades de cada letra a partir del texto. Eliminar la correlacin aqu es ms complicado y veremos como hacerlo en captulos posteriores. Sonido: Cada canal estreo se muestrea a 44.1 kHz y utiliza una representacin de 16 bits. Aunque no vamos a construir el cdigo Huffman (tendra 216 entradas), calcularemos la entropa y por tanto una estimacin de la mejor compresin que podemos alcanzar. Podemos tambin eliminar (o disminuir) la correlacin entre los datos y volver a calcular la entropa y por tanto una estimacin de la compresin a alcanzar con este modelo.
Rafael Molina Tema 3: Codificacin Huffman 74
Rafael Molina
75
III.8 Bibliografa
K. Sayood, Introduction to Data Compression, Morgan and Kaufmann, 2000.
Material adicional de la asignatura
G. Langdon, Data Compression, Universidad de California, 1999. (langdon_RunLength_Encodings.pdf). Roque Marn,Compresores estadsticos, Universidad de Murcia, (00_compresores_estadsticos_univ.murcia.pdf). Notas sobre el cdigo de Golomb (Golomb_Notes.pdf). Otra presentacin sobre compresores estadsticos, (00_compresores_estadsticos_II.pdf). Temas 2, 3 y 4 del curso de compresin de datos impartido en Stony Brook University (NY, USA), (tema[2,3,4]_stony.pdf). Tema 3 del curso de compresin de datos impartido en Chalmers University of Technology (Suecia), curso 2003-2004. (tema3_chalmers.pdf). S. W. Golomb, Run-Length Encodings, IEEE Trans. On Information Theory, IT12: 399-401, 1966. D.A. Huffman, A method for the construction of minimum redundancy codes, Proceedings of the IRE, 40:1098-1101, 1951.
Rafael Molina Tema 3: Codificacin Huffman 76
La demostracin del teorema es la siguiente: Supongamos que codificamos bloques de q mensajes y seguimos suponiendo que son independientes, entonces tendremos (observa que la fuente es ahora Sq)
H ( S q ) nq H ( S q ) + 1
Basta con elegir un tamao de bloque q suficientemente grande para conseguir 1/q < para que se cumpla lo afirmado por el teorema.
Rafael Molina Tema 3: Codificacin Huffman 78