Post on 24-Nov-2015
Rafael Molina Tema 3: Codificacin Huffman 1
Tema 3: Codificacin Huffman
Rafael MolinaDepto. Ciencias de la Computacin
e Inteligencia ArtificialUniversidad de Granada
Rafael Molina Tema 3: Codificacin Huffman 2
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 Apndice: Longitud del cdigo de Huffman y cdigo de
Huffman extendido (*) Estas secciones son ilustrativas, no entran en el examen
Contenidos
Rafael Molina Tema 3: Codificacin Huffman 3
III.1 Objetivos del tema
En este tema vamos a describir un algoritmo de codificacinmuy conocido: el cdigo de Huffman. Primero supondremosque es conocida la distribucin de probabilidad de la fuentey luego construiremos el cdigo cuando dichasprobabilidades no son conocidas.
A continuacin veremos algunos esquemas de codificacin,en algn sentido, similares al cdigo de Huffman.
Finalmente veremos algunos ejemplos de aplicacin acompresin de imgenes, sonido y texto.
Rafael Molina Tema 3: Codificacin Huffman 4
III.2 El algoritmo del cdigo de Huffman.
La codificacin usando el mtodo de Huffman (cdigoHuffman) es un cdigo prefijo ptimo para un conjuntodado de probabilidades.
Puede alcanzar la entropa, aunque no lo hace siempre.
S es ptimo entre los cdigos prefijo.
Rafael Molina Tema 3: Codificacin Huffman 5
El cdigo de Huffman est basado en dos propiedades de loscdigos prefijo ptimos:
1. En un cdigo prefijo ptimo, los smbolos ms frecuenteslos que tienen mayor probabilidad- tienen palabras delcdigo ms cortas que las palabras menos frecuentes.
2. En un cdigo prefijo ptimo, los dos smbolos que ocurrencon menos frecuencia tendrn la misma longitud.
Demostracin de que estas condiciones las cumple un cdigoprefijo ptimo:
La primera condicin es obvia. El nmero medio de bits porsmbolo sera mayor si esta condicin no se cumpliese.
Rafael Molina Tema 3: Codificacin Huffman 6
Para probar la segunda condicin usaremos reduccin alabsurdo.
Supongamos que existe un cdigo prefijo ptimo, C, en elque los dos smbolos menos probables no tienen la mismalongitud.
Sean P1 y P2 las correspondientes palabras del cdigo ysupongamos que long(P1)=k y long(P2)=n con k
Rafael Molina Tema 3: Codificacin Huffman 7
Como estos smbolos son los menos probables ninguna otrapalabra puede ser ms larga que estas dos y por tanto nohay 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 seaptimo, lo que contradice la hiptesis inicial sobre C.
Para construir el cdigo de Huffman le aadimos la siguientecondicin a las dos propiedades vistas de los cdigos prefijoptimos: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 esuna hilera de ceros y unos y * denota concatenacin.
Rafael Molina Tema 3: Codificacin Huffman 8
Genera el cdigo de Huffmancorrespondiente a lassiguientes probabilidades
1. Ordena los smbolos de ms probable a menos probable,
2. Comienza a construir un rbol por las hojas combinando los dos smbolos menos probables,
3. Itera el procedimiento
Algoritmo del cdigo de Huffman
P( )=0.5P( )=0.4P( )=0.09P( E )=0.01
Rafael Molina Tema 3: Codificacin Huffman 9
E 0.01
0.09
0.4
0.5
1
0
0.1
0
10.5
0
11.0
Cul es la longitud media del cdigo?
Cul es la entropa de la fuente?
probabilidades
Probabilidades acumuladas
Nota: asignamos 1 a la rama menos probableE
0
10
110
111
CdigoSmbolo CdigoSmbolo
Rafael Molina Tema 3: Codificacin Huffman 10
D 0.1
0.3
0.3
0.3
1
0
0.4
0.61
0
1
0
1.0C
B
A
A 00 B 01 C 10 D 11
probabilidades Otro ejemplo
Rafael Molina Tema 3: Codificacin Huffman 11
E 0.1
0.1
0.2
0.2
1
0
0.2
0
10.4
probabilidades
D
C
A
B 0.4
0.6
0
1
0
11.0
B 1A 01C 000D 0010E 0011
Para decodificar una secuencia de palabras slo tenemos querecorrer el rbol del cdigo prefijo correspondiente al cdigoHuffman como vimos en el captulo anterior.
Otro ejemplo
Rafael Molina Tema 3: Codificacin Huffman 12
III.2.1 Cdigos de Huffman de mnima varianzaConsideremos el cdigo de Huffman del ejemplo anterior. Elnmero medio de bits por smbolo es
L=0.4x1+0.2x2+0.2x3+0.1x4+0.1x4=2.2 bits/smbolo
Supongamos que queremos transmitir 10000 smbolos/sg.Con una capacidad de transmisin de 22000 bits/sg el canalira en media bien. Sin embargo, si tenemos que transmitirmuchas veces seguidas los smbolos D o E podemos necesitarun buffer mucho mayor.
Lo mejor sera que, manteniendo la misma longitud media,pudisemos disear un cdigo de Huffman con menorvarianza en la longitud de la codificacin de cada smbolo.
Rafael Molina Tema 3: Codificacin Huffman 13E 0.1
0.1
0.2
0.2
1
0
0.2
0
1 0.4
probabilidades
D
C
A
B 0.4
B 00A 10C 11D 010E 011
0
1 1.0
Para disminuir la varianza colocamos, en caso de empate enlas probabilidades de los nodos, los nodos ya utilizados loms alto posible procurando utilizarlos lo ms tarde posible.Retomemos el ejemplo de la seccin anterior.
0.6
0
1
Rafael Molina Tema 3: Codificacin Huffman 14
III.3 Cdigo de Huffman adaptativo
El cdigo de Huffman necesita conocer la probabilidad deaparicin de cada smbolo.
Para la construccin del rbol adaptativamente, veamos acontinuacin qu propiedades caracterizan a un rbol binariopara que sea el correspondiente a un cdigo de Huffman.
1. Para tener estas probabilidades podemos leer los datospara obtenerlas y luego codificar los smbolos usando elcdigo de Huffman para dichas probabilidades,
2. o bien podemos ir construyndolo (adaptativamente)mientras vamos leyendo los smbolos. Esta es la base delcdigo Huffman adaptativo.
Rafael Molina Tema 3: Codificacin Huffman 15
Consideremos un rbol binario correspondiente a un alfabeto detamao n en el que los smbolos del alfabeto son las hojas.Entonces, el nmero de nodos del rbol es 2n-1 (prubalo porinduccin).
A cada nodo del rbol binario le vamos a asignar doscampos: Nmero del nodo y peso del nodo.
El nmero de nodo es un nmero nico asignado a cada nododel rbol entre 1 y 2n-1. Los nmeros los notaremos y1,,y2n-1.
El peso de un nodo hoja es simplemente el nmero de vecesque aparece el smbolo correspondiente y el de uno interno lasuma de los pesos de sus dos hijos. Los pesos los notaremosx1,,x2n-1.
Rafael Molina Tema 3: Codificacin Huffman 16
Puede probarse que:
Si al asignar nmeros a los nodos comenzando por el uno yrecorriendo el rbol por niveles (asignamos, de izquierda aderecha en cada nivel y de las hojas (abajo) a la raz(arriba) los pesos de los nodos quedan ordenados en unorden no decreciente
El rbol obtenido es un rbol binario correspondiente a uncdigo de Huffman para dichos smbolos con lasprobabilidades de cada nodo hoja igual a su peso divididopor la suma de los pesos.La propiedad anterior recibe el nombre de sibling property onode number invariant.
Rafael Molina Tema 3: Codificacin Huffman 17
En el ejemplo de la derecha:Entre parntesis los pesos decada nodo. (16)
(7) (9)
(3) (4)
(2)(2)(1) (2)1 2
7 8
5 6
9
3 4
Dentro de los cuadrados elnmero asignado a cadanodo.
Por tanto, este rbol es elcorrespondiente al cdigo deHuffman para estos smboloscon las probabilidades que seobtienen a partir del nmero deveces que ha aparecido cadasmbolo dividido por el nmerode smbolo ledos.
Rafael Molina Tema 3: Codificacin Huffman 18
En el cdigo Huffman adaptativo ni el transmisor ni elreceptor conocen al principio las probabilidades de lossmbolos. Por eso:
1. Codificador y decodificar comienzan con un rbol con unnodo nico que corresponde a todos los smbolos notransmitidos (NYT) y que tiene peso cero.
2. Mientras progresa la transmisin se aadirn nodos alrbol correspondientes a smbolos que aparezcan porprimera vez, se modificarn los pesos (tanto si elsmbolo es nuevo como si es ya existente) y seactualizar el rbol para que siga cumpliendo the siblingproperty (siga siendo de Huffman).
Rafael Molina Tema 3: Codificacin Huffman 19
El algoritmo de Huffman adaptativo consta de los siguienteselementos:
1. Inicializacin (la misma para el codificador ydecodificador).
Antes de describir estas partes comentaremos brevemente sobre la codificacin de los smbolos:
2 Algoritmo de codificacin.
3. Algoritmo de decodificacin.
4. Proceso de actualizacin del rbol para que mantengathe sibling property.
Rafael Molina Tema 3: Codificacin Huffman 20
Codificacin de un smbolo que aparece por primeravez:
Salvo que sea el primero de todos lo smbolos de lasecuencia, la codificacin de un smbolo que aparece porprimera vez consta de la codificacin que proporciona elrbol del nodo NYT seguido de un cdigo fijo para el smboloque deben conocer codificador y decodificador
En el caso en que sea el primer smbolo que aparece en lasecuencia 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 21
Inicializacin del cdigo de Huffman adaptativo (tanto para el codificador como para el decodificador
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:
0
NYT2n+1
Nmero del nodo
peso
Rafael Molina Tema 3: Codificacin Huffman 22
1. Si encontramos un smbolo nuevo (ver nota) entoncesgenerar el cdigo del nodo NYT seguido del cdigo fijo(ver nota) del smbolo. Aadir el nuevo smbolo alrbol,
2. Si el smbolo ya est presente, generar su cdigousando el rbol,
3. Actualizar el rbol para que siga conservando thesibling property.
Nota: Recordemos que para el primer smbolo no hace falta transmitir elcdigo de NYT. El cdigo fijo es conocido al principio por codificador ydecodificador.
Algoritmo de codificacin para el cdigo Huffman adaptativo
Rafael Molina Tema 3: Codificacin Huffman 23
1. Decodificar el smbolo usando el rbol actual,
2. Si encontramos el nodo NYT, usar el cdigo fijo paradecodificar el smbolo que viene a continuacin. Aadirel nuevo smbolo al rbol,
3. Actualizar el rbol para que siga conservando thesibling property.
Nota: recordar, de nuevo, que el primer smbolo no va precedido por elcdigo de NYT
Algoritmo de decodificacin para el cdigo Huffman adaptativo
Rafael Molina Tema 3: Codificacin Huffman 24
1. Sea y la hoja (smbolo) con peso x,2. Si y es la raz, aumentar x en 1 y salir3. Intercambiar y con el nodo con el nmero mayor que
tenga el mismo peso que l (salvo que sea su padre)4. Aumentar x en 15. Sea y el padre que tiene su peso x (el que sea, no el
definido en 4) ir al paso 2 del algoritmo
Actualizacin del rbol para el cdigo Huffman adaptativo
Rafael Molina Tema 3: Codificacin Huffman 25
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
Los cdigos de longitud fija que usamos son
a 000 b 001 c 010 d 011
Rafael Molina Tema 3: Codificacin Huffman 26
aabcdad en A={a,b,c,d}
salida=000
NYT
9
0 7
a
8
0
0
Paso 1 del algoritmo de codificacin
0
NYT
9Inicializacin
0 1
Rafael Molina Tema 3: Codificacin Huffman 27
NYT
9
0 7
a
8
0
1
Paso 3 del algoritmo de codificacin (actualizacin)
Paso 4 dentro del algoritmo de actualizacin
NYT
9
0 7
a
8
1
1
Paso 2 dentro del algoritmo de actualizacin
0 1
0 1
Rafael Molina Tema 3: Codificacin Huffman 28
aabcdad
salida=0001
NYT
9
0 7
a
8
1
1
Paso 2 del algoritmo de codificacin
Tenemos
NYT
9
0 7
a
8
1
1
salida=000
0 1
0 1
Rafael Molina Tema 3: Codificacin Huffman 29
NYT
9
0 7
a
8
1
2
Paso 3 del algoritmo de codificacin (actualizacin)
Paso 4 dentro del algoritmo de actualizacin
NYT
9
0 7
a
8
2
2
Paso 2 dentro del algoritmo de actualizacin
0 1
0 1
Rafael Molina Tema 3: Codificacin Huffman 30
aabcdad
Tenemos
NYT
9
0 7
a
8
2
2
salida=0001
0 1
1
salida=000100019
7
a
8
2
2Paso 1 del
algoritmo de codificacin
Cdigo de b
Cdigo de NYT
NYT
0
0
0 65
b
0
0 1
Rafael Molina Tema 3: Codificacin Huffman 31
6
1
9
7
a
8
2
2
NYT
0
0
15
b
0
0 1
5
a1
9
7 8
2
2
NYT
0
1
1 6
b
0
0 1
Paso 3 del algoritmo de codificacin (actualizacin)
a1
9
7 8
3
2
NYT
0
1
1 6
b
0
0 1
5
Rafael Molina Tema 3: Codificacin Huffman 32
a1
9
7 8
3
2
NYT
0
1
1 6
b
0
0 1
5
aabcdad
Tenemos
salida=00010001
a1
9
7 8
3
2
NYT
1
1 6
b
0
0 1
5
salida=0001000100010
0 0
0
43
c
Cdigo de NYT
c
Algoritmo de codificacin sin adaptacin del rbol
0 1
Rafael Molina Tema 3: Codificacin Huffman 33
adaptacin del rbol
a1
9
7 8
3
2
NYT
1
1 6b
0
0 1
5
0 1
0
43c
0 1
a1
9
7 8
3
2
NYT
1
1 6b
0
0 1
5
0 1
1
43
c
0 1
a1
9
7 8
3
2
NYT
2
1 6b
0
0 1
5
0 1
1
43c
0 1
a1
9
7 8
4
2
NYT
2
1 6b
0
0 1
5
0 1
1
43c
0 1
Rafael Molina Tema 3: Codificacin Huffman 34
aabcdad
Tenemos
a1
9
7 8
4
2
NYT
2
1 6b
0
0 1
5
0 1
1
43c
0 1
salida=0001000100010
a1
9
7 8
4
22
1 6b
0
0 1
5
1
1
43c
salida=0001000100010000011
NYT0 0 21
d
0
Algoritmo de codificacin sin adaptacin del rbol
d
NYT
0
0
1
1
Rafael Molina Tema 3: Codificacin Huffman 35
a1
9
7 8
4
22
1 6b
0
0 1
5
1
1
43c
NYT0 1 21
d
00
0
1
1
a1
9
7 8
4
22
1 6b
0
0 1
5
1
1
43c
NYT0 1 21
d
10
0
1
1
adaptacin del rbol
Rafael Molina Tema 3: Codificacin Huffman 36
a1
9
7 8
4
22
1 6
b
0
0 1
5
1
1
43
c
NYT0 1 21
d
10
0
1
1
a1
9
7 8
4
22
1 6b
0
0 1
5
1
1
43c
NYT0 1 21
d
10
0
1
1
adaptacin del rbolCAMBIO DE ORDEN
Rafael Molina Tema 3: Codificacin Huffman 37
a1
9
7 8
4
22
1 6
b
0
0 1
5
1
2
43
c
NYT0 1 21
d
10
0
1
1
adaptacin del rbol
a1
9
7 8
4
22
1 6
b
0
0 1
5
1
2
43
c
NYT0 1 21
d
10
0
1
1
Rafael Molina Tema 3: Codificacin Huffman 38
adaptacin del rbol
11
9
7
1
8
4
2 2
6
b
0
0 1
5
1
2
43
c
NYT0 1 21
d
10
0 1
a
11
9
7
1
8
4
2 3
6
b
0
0 1
5
1
2
43
c
NYT0 1 21
d
10
0 1
a
CAMBIO DE ORDEN
Rafael Molina Tema 3: Codificacin Huffman 39
adaptacin del rbol
11
9
7
1
8
5
2 3
6
b
0
0 1
5
1
2
43
c
NYT0 1 21
d
10
0 1
a
Rafael Molina Tema 3: Codificacin Huffman 40
11
9
7
1
8
5
2 3
6
b
0
0 1
5
1
2
43
c
NYT0 1 21
d
10
0 1
a
aabcdad
Tenemos salida=0001000100010000011
11
9
7
1
8
5
2 3
6
b
0
0 1
5
1
2
43
c
NYT0 1 21
d
10
0 1
a
Algoritmo de codificacin sin adaptacin del rbol
salida=00010001000100000110
Rafael Molina Tema 3: Codificacin Huffman 41
11
9
7
1
8
5
3 3
6
b
0
0 1
5
1
2
43
c
NYT0 1 21
d
10
0 1
a1
1
9
7
1
8
6
3 3
6
b
0
0 1
5
1
2
43
c
NYT0 1 21
d
10
0 1
a
adaptacin del rbol
Rafael Molina Tema 3: Codificacin Huffman 42
11
9
7
1
8
6
3 3
6
b
0
0 1
5
1
2
43
c
NYT0 1 21
d
10
0 1
a
aabcdad
Tenemos salida=
00010001000100000110
Algoritmo de codificacin sin adaptacin del rbol
salida=000100010001000001101101
11
9
7
1
8
6
3 3
6
b
0
0 1
5
1
2
43
c
NYT0 1 21
d
10
0 1
a
d
Rafael Molina Tema 3: Codificacin Huffman 43
11
9
7
1
8
6
3 3
6
b
0
0 1
5
1
2
43
c
NYT0 1 21
d
10
0 1
a1
1
9
7
1
8
6
3 3
6
d
0
0 1
5
1
2
43
c
NYT0 1 21
b
10
0 1
a
Observar cambio
Rafael Molina Tema 3: Codificacin Huffman 44
21
9
7
1
8
6
3 3
6
d
0
0 1
5
1
2
43
c
NYT0 1 21
b
10
0 1
a2
1
9
7
1
8
6
3 3
6
d
0
0 1
5
1
2
43
c
NYT0 1 21
b
10
0 1
a
Rafael Molina Tema 3: Codificacin Huffman 45
21
9
7
1
8
6
3 4
6
d
0
0 1
5
1
2
43
c
NYT0 1 21
b
10
0 1
a2
1
9
7
1
8
7
3 4
6
d
0
0 1
5
1
2
43
c
NYT0 1 21
b
10
0 1
a
Rafael Molina Tema 3: Codificacin Huffman 46
Ejercicio:
Usando el cdigo fijo
a=000, b=001, c=010, d=011
Decodificar la secuencia 00110000 usando el cdigo deHuffman adaptativo.
Aunque el cdigo de Huffman es uno de los mtodos decodificacin de longitud de palabra variable msconocidos, existen otros mtodos algo menos conocidospero tambin muy tiles. En particular los mtodos deGolomb-Rice y Tunstall que veremos a continuacin.
Rafael Molina Tema 3: Codificacin Huffman 47
III.4 Cdigo de Golomb
Consideremos un suceso A que tiene probabilidad p y sucomplementario Ac que tiene probabilidad q=1-p (obviamentep+q=1).
Queremos codificar el nmero de veces (racha=run length)que aparece A antes de que aparezca Ac.
Suponemos que las realizaciones son independientes.
Observa que si p es prximo a uno esperamos que aparezcamuchas veces el suceso A antes de que aparezca un Ac.
Rafael Molina Tema 3: Codificacin Huffman 48
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 Tema 3: Codificacin Huffman 49
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 variablealeatoria N definida por
N= nmero de veces que aparece A antes de que aparezcaAc.
Esta variable tiene la siguiente distribucin de probabilidad
P(N=n)=pnq n=0,1,2,.
Rafael Molina Tema 3: Codificacin Huffman 50
Una posible codificacin sera:
Cada vez que aparezca el suceso A lo codificamos con un unoy cuando se produzca el suceso Ac lo codificamos con uncero.
De esta forma el valor n de la variable aleatoria N se codificamediante n unos seguidos de un cero. Es decir,
0 01 102 110
3 1110
N cdigo
. .
. .
Este cdigo recibe el nombre decdigo unario.
Cul es el nmero medio de bits queeste cdigo, C, usa para codificar lavariable N?
Rafael Molina Tema 3: Codificacin Huffman 51
( ) pppqpq
pderivpqp
qnpqpp
q
npqpqqpnNC
n
n
n
n
n
n
n
nn
np
=+=
+=+=
+=+=
=
=
=
=
=
11
11
1
11
)1()(
2
00
1
000
Observa que si p est muy prximo a uno Cp(N) es muygrande.Cunto vale la entropa de la variable aleatoria N enfuncin de p?.
Recuerda que q=1-p
Rafael Molina Tema 3: Codificacin Huffman 52
( ) ( )
( ) ( )( )ppqq
p
pp
pqp
ppqpqq
pderivadappqpqq
npppqpqq
nppqpqqqppqNH
n
n
n
n
n
n
n
nn
n
np
loglog1
1
)log(1
log1
1)log(1
)log(
)log(1
)log(
)log(1
)log(
log)log(log)(
2
0
0
1
000
+===
=
=
==
=
=
=
=
=
Recuerda que q=1-p
Rafael Molina Tema 3: Codificacin Huffman 53
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.
Representacin grfica de Cp(N) Hp(N)
Rafael Molina Tema 3: Codificacin Huffman 54
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?.
pnpn
pnn
qqnNPqqpnNP
log1log1
log2
11
22
225.0)(5.0
2)(+====
===de donde
pnpn log1log 12 +=o
+==
pn
pnn
log1
log1
112
Muy importante
Rafael Molina Tema 3: Codificacin Huffman 55
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
45.3
35.3arribapor x a prximo ms enteroabajopor x a prximo ms entero
==
==
xx
Continuemos con el cdigo de Golomb. Sea
=p
wlog
1
Rafael Molina Tema 3: Codificacin Huffman 56
QwnRywnQ =
=Para cada n seanEn 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 bits log w ** Este cdigo va a ser mejorado despus
Rafael Molina Tema 3: Codificacin Huffman 57
Supongamos que p=2^(-1/4) ~ 0.8409, entonces
2log,4 == wwN Q R Representacin0 0 0 0001 0 1 0012 0 2 0103 0 3 0114 1 0 10005 1 1 10016 1 2 1010
Rafael Molina Tema 3: Codificacin Huffman 58
Supongamos que p=2^(-1/5) , entonces
3log,5 == wwN Q R Representacin0 0 0 00001 0 1 00012 0 2 00103 0 3 00114 0 4 01005 1 0 100006 1 1 10001
Rafael Molina Tema 3: Codificacin Huffman 59
La parte sufijo del cdigo es mejorable cuando w no sea unapotencia de 2, si usamos la siguiente representacin delongitud variable:
Sea R {0,1,,w-1}
cdigos 2Msobran nos bits logw Usando logw w=
bits logwcon binariacin representa usamos MR Si < R de bits logen cin representa la usamos R Si MwM +
Rafael Molina Tema 3: Codificacin Huffman 60
10
0 1
w=2
0
0 1
21
0 1
w=3
Resto R Representacin
0 0
1 1
Resto R Representacin
0 0
1 10
2 11
Ejemplos:
Los arcos determinan el cdigoLos nodos contienen el resto
Rafael Molina Tema 3: Codificacin Huffman 61
43
0 1
0 1
2
0 1
w=5
Resto R Representacin
0 00
1 01
2 10
3 110
4 111
10
0 1
0 1
32
0 1
w=4
Resto R Representacin
0 00
1 01
2 10
3 11
10
0 1
Ms ejemplos de la representacin de la parte sufijo
Rafael Molina Tema 3: Codificacin Huffman 62
Supongamos que p=2-1/5 . Entonces
3log,5 == wwN Q R Representacin0 0 0 0001 0 1 0012 0 2 0103 0 3 01104 0 4 01115 1 0 10006 1 1 1001
Otro ejemplo de cdigo Gollub:
CDIGO
GOLLUB
Rafael Molina Tema 3: Codificacin Huffman 63
III.5 Cdigo Tunstall Es un cdigo de longitud fija en el que cada palabra del cdigo puede representarun nmero diferente de letras.
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)< 2nseguir, 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,
Cdigo de Tunstall
Rafael Molina Tema 3: Codificacin Huffman 64
*Justificacin de la condicin de parada:
Veamos cuantos hojas tiene el rbol,
Si en un instante tiene l hojas, para expandir le quitamos una yde esa una salen m. Por tanto una vez realizada la expansintenemos l-1+m que necesitaremos que sea menor que 2n yaque necesitamos dejarnos al menos un cdigo libre como yaveremos.
Una vez construido el rbol le asignamos un cdigo de longitud n a cada una de las hojas.
Rafael Molina Tema 3: Codificacin Huffman 65
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 B C
0.6 0.3 0.1
Rafael Molina Tema 3: Codificacin Huffman 66
l=3, 3+2=5, 5
Rafael Molina Tema 3: Codificacin Huffman 67
l=5, 5+2=7, 7
Rafael Molina Tema 3: Codificacin Huffman 68
L=7, 7+2=9, 9 8, Salimos
Paso 2
Codificacin final (hay varias opciones)
A B C
A B C
A B C
000 001 010
011 100
101 110Observa que tenemos libre la palabra del cdigo 111
Rafael Molina Tema 3: Codificacin Huffman 69
El cdigo de Tunstall ha generado la siguiente representacin
Entrada Salida
AAA 000
AAB 001
AAC 010
AB 011
AC 100
B 101
C 110
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.
Rafael Molina Tema 3: Codificacin Huffman 70
Otro ejemplo. Supongamos P(A)=0.9 y P(B)=0.1 y usamos n=2.
El rbol que construiramos sera
A B
A B
00 01
10
Y dejaramos el 11 para enviar el cdigo de A
Entrada SalidaAA 00
AB 01
B 10
Rafael Molina Tema 3: Codificacin Huffman 71
Si ussemos las cuatro palabras tendramos
y no podramos enviar cdigo para A
Entrada SalidaAAA 00
AAB 01
AB 10
B 11
A B
A B
10
11
A B
00 01
Rafael Molina Tema 3: Codificacin Huffman 72
Entrada Salida
AAA 000
AAB 001
AAC 010
AB 011
AC 100
B 101
C 110
Problema: considera la tabla en la que el cdigo 111 es utilizado para anunciar que a continuacin viene el cdigo de A o AA.
Qu proceso seguiramos para codificar las secuencias
CABBAACCBBACA
?
Rafael Molina Tema 3: Codificacin Huffman 73
III.6 Aplicaciones del cdigo de Huffman En las clases de prcticas se estudiarn las siguientesaplicaciones:
Imgenes: Usaremos imgenes de niveles de gris, es decir,que en cada punto toman un valor entre 0 y 255. Estimaremosla probabilidad de ocurrencia de cada nivel de gris usando elhistograma y aplicaremos Huffman. El modelo ser por tantono adaptativo.
Como los valores de los pxeles estn muy correladoscodificaremos la diferencia entre un pxel y el anterior usandoHuffman, veremos que mejoramos el nivel de compresin.
Tambin usaremos imgenes binarias y cdigos de Huffmanadaptativos
Rafael Molina Tema 3: Codificacin Huffman 74
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 75
III.7 Resumen del tema
1. Cdigo de Huffman, no adaptativo y adaptativo,2. Cdigos unarios y de Golomb,3. Cdigos de Tunstall,4. Aplicaciones.
Rafael Molina Tema 3: Codificacin Huffman 76
III.8 BibliografaK. Sayood, Introduction to Data Compression, Morgan and Kaufmann, 2000.Material adicional de la asignaturaG. Langdon, Data Compression, Universidad de California, 1999. (langdon_Run-Length_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, IT-12: 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 77
Apndice: longitud de los cdigos de Huffman y cdigos de Huffman extendidos
Dado un cdigo de Huffman, puede probarse que, su longitud media n cumple
H(S) n < H(S) + 1
Primer Teorema de Shannon o Teorema Fundamental de la Codificacin sin Ruido:Dada una fuente S = {x1, ... xm} y un alfabeto binario, existe al menos un cdigo prefijo C cuya longitud media cumple
siendo cualquier nmero real arbitrariamente pequeo.
+< )(SHn
Rafael Molina Tema 3: Codificacin Huffman 78
1)()( + qqq SHnSH
1)()( + SHqnqSHq
qSHnSH 1)()( +
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)
Reeescribiendo esta ecuacin en funcin de la entropa de la fuente original tendremos
dividiendo por q obtendremos
Basta con elegir un tamao de bloque q suficientemente grande para conseguir 1/q < para que se cumpla lo afirmado por el teorema.
Tema 3: Codificacin Huffman ContenidosIII.1 Objetivos del temaIII.2 El algoritmo del cdigo de Huffman. Nmero de diapositiva 5Nmero de diapositiva 6Nmero de diapositiva 7Nmero de diapositiva 8Nmero de diapositiva 9Nmero de diapositiva 10Nmero de diapositiva 11III.2.1 Cdigos de Huffman de mnima varianzaNmero de diapositiva 13III.3 Cdigo de Huffman adaptativoNmero de diapositiva 15Nmero de diapositiva 16Nmero de diapositiva 17Nmero de diapositiva 18Nmero de diapositiva 19Nmero de diapositiva 20Nmero de diapositiva 21Algoritmo de codificacin para el cdigo Huffman adaptativoAlgoritmo de decodificacin para el cdigo Huffman adaptativoActualizacin del rbol para el cdigo Huffman adaptativoNmero de diapositiva 25Nmero de diapositiva 26Nmero de diapositiva 27Nmero de diapositiva 28Nmero de diapositiva 29Nmero de diapositiva 30Nmero de diapositiva 31Nmero de diapositiva 32Nmero de diapositiva 33Nmero de diapositiva 34Nmero de diapositiva 35Nmero de diapositiva 36Nmero de diapositiva 37Nmero de diapositiva 38Nmero de diapositiva 39Nmero de diapositiva 40Nmero de diapositiva 41Nmero de diapositiva 42Nmero de diapositiva 43Nmero de diapositiva 44Nmero de diapositiva 45Nmero de diapositiva 46III.4 Cdigo de GolombNmero de diapositiva 48Nmero de diapositiva 49Nmero de diapositiva 50Nmero de diapositiva 51Nmero de diapositiva 52Nmero de diapositiva 53Nmero de diapositiva 54Nmero de diapositiva 55Nmero de diapositiva 56Nmero de diapositiva 57Nmero de diapositiva 58Nmero de diapositiva 59Nmero de diapositiva 60Nmero de diapositiva 61Nmero de diapositiva 62III.5 Cdigo Tunstall Nmero de diapositiva 64Nmero de diapositiva 65Nmero de diapositiva 66Nmero de diapositiva 67Nmero de diapositiva 68Nmero de diapositiva 69Nmero de diapositiva 70Nmero de diapositiva 71Nmero de diapositiva 72III.6 Aplicaciones del cdigo de Huffman Nmero de diapositiva 74III.7 Resumen del temaIII.8 BibliografaApndice: longitud de los cdigos de Huffman y cdigos de Huffman extendidosNmero de diapositiva 78