03 CODIGO DE HUFFMAN

Rafael Molina Tema 3: Codificación Huffman 1

Tema 3: Codificación Huffman

Rafael MolinaDepto. Ciencias de la Computación

e Inteligencia ArtificialUniversidad de Granada


• Objetivos del tema• El algoritmo del código de Huffman

– Códigos de Huffman de mínima varianza • Códigos de Huffman Adaptativos

– Procedimiento de codificación– Procedimiento de decodificación– Procedimiento de actualización

• (*) Códigos de Golomb• (*)Código Tunstall• Aplicaciones del código de Huffman• Resumen

• Bibliografía• Apéndice: Longitud del código de Huffman y código de

Huffman extendido (*) Estas secciones son ilustrativas, no entran en el examen

Contenidos


III.1 Objetivos del tema

En este tema vamos a describir un algoritmo de codificaciónmuy conocido: el código de Huffman. Primero supondremosque es conocida la distribución de probabilidad de la fuentey luego construiremos el código cuando dichasprobabilidades no son conocidas.

A continuación veremos algunos esquemas de codificación,en algún sentido, similares al código de Huffman.

Finalmente veremos algunos ejemplos de aplicación acompresión de imágenes, sonido y texto.


III.2 El algoritmo del código de Huffman.

La codificación usando el método de Huffman (códigoHuffman) es un código prefijo óptimo para un conjuntodado de probabilidades.

Puede alcanzar la entropía, aunque no lo hace siempre.

Sí es óptimo entre los códigos prefijo.


El código de Huffman está basado en dos propiedades de loscódigos prefijo óptimos:

1. En un código prefijo óptimo, los símbolos más frecuentes–los que tienen mayor probabilidad- tienen palabras delcódigo más cortas que las palabras menos frecuentes.

2. En un código prefijo óptimo, los dos símbolos que ocurrencon menos frecuencia tendrán la misma longitud.

Demostración de que estas condiciones las cumple un códigoprefijo óptimo:

La primera condición es obvia. El número medio de bits porsímbolo sería mayor si esta condición no se cumpliese.


Para probar la segunda condición usaremos reducción alabsurdo.

Supongamos que existe un código prefijo óptimo, C, en elque los dos símbolos menos probables no tienen la mismalongitud.

Sean P1 y P2 las correspondientes palabras del código ysupongamos que long(P1)=k y long(P2)=n con k<n.

Al ser un código prefijo, P1 no puede ser prefijo de P2. Portanto podemos suprimir los n-k últimos dígitos de P2 y teneraún dos códigos distintos. Sea C’ el nuevo código, ¿siguesiendo prefijo?


Como estos símbolos son los menos probables ninguna otrapalabra puede ser más larga que estas dos y por tanto nohay peligro de que al hacer más corta esta palabra del código(la de P2) se convierta en prefijo de ninguna otra. Por tanto,C’ sigue siendo prefijo.

Hemos creado un nuevo código, C’, que hace que C no seaóptimo, lo que contradice la hipótesis inicial sobre C.

Para construir el código de Huffman le añadimos la siguientecondición a las dos propiedades vistas de los códigos prefijoóptimos:Si u y v son los dos símbolos menos probables en el alfabeto,si la codificación de u es m*0, la de v será m*1. Donde m esuna hilera de ceros y unos y * denota concatenación.


Genera el código de Huffmancorrespondiente a lassiguientes probabilidades

1. Ordena los símbolos de más probable a menos probable,

2. Comienza a construir un árbol por las hojas combinando los dos símbolos menos probables,

3. Itera el procedimiento

Algoritmo del código de Huffman

P( )=0.5P( )=0.4P( )=0.09P( E )=0.01


E 0.01

0.09

0.4

0.5

1

0

0.1

0

10.5

0

11.0

¿Cuál es la longitud media del código?

¿Cuál es la entropía de la fuente?

probabilidades

Probabilidades acumuladas

Nota: asignamos 1 a la rama menos probableE

0

10

110

111

CódigoSímbolo CódigoSímbolo


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


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 sólo tenemos querecorrer el árbol del código prefijo correspondiente al códigoHuffman como vimos en el capítulo anterior.

Otro ejemplo


III.2.1 Códigos de Huffman de mínima varianzaConsideremos el código de Huffman del ejemplo anterior. Elnúmero medio de bits por símbolo es

L=0.4x1+0.2x2+0.2x3+0.1x4+0.1x4=2.2 bits/símbolo

Supongamos que queremos transmitir 10000 símbolos/sg.Con una capacidad de transmisión de 22000 bits/sg el canaliría en media bien. Sin embargo, si tenemos que transmitirmuchas veces seguidas los símbolos D o E podemos necesitarun buffer mucho mayor.

Lo mejor sería que, manteniendo la misma longitud media,pudiésemos diseñar un código de Huffman con menorvarianza en la longitud de la codificación de cada símbolo.

Rafael Molina Tema 3: Codificación 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 lomás alto posible procurando utilizarlos lo más tarde posible.Retomemos el ejemplo de la sección anterior.

0.6

0

1


III.3 Código de Huffman adaptativo

El código de Huffman necesita conocer la probabilidad deaparición de cada símbolo.

Para la construcción del árbol adaptativamente, veamos acontinuación qué propiedades caracterizan a un árbol binariopara que sea el correspondiente a un código de Huffman.

1. Para tener estas probabilidades podemos leer los datospara obtenerlas y luego codificar los símbolos usando elcódigo de Huffman para dichas probabilidades,

2. o bien podemos ir construyéndolo (adaptativamente)mientras vamos leyendo los símbolos. Esta es la base delcódigo Huffman adaptativo.


Consideremos un árbol binario correspondiente a un alfabeto detamaño n en el que los símbolos del alfabeto son las hojas.Entonces, el número de nodos del árbol es 2n-1 (pruébalo por

inducción).

A cada nodo del árbol binario le vamos a asignar doscampos: Número del nodo y peso del nodo.

El número de nodo es un número único asignado a cada nododel árbol entre 1 y 2n-1. Los números los notaremos y1,…,y2n-1.

El peso de un nodo hoja es simplemente el número de vecesque aparece el símbolo correspondiente y el de uno interno lasuma de los pesos de sus dos hijos. Los pesos los notaremosx1,…,x2n-1.


Puede probarse que:

Si al asignar números 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 raíz(arriba) los pesos de los nodos quedan ordenados en unorden no decreciente

El árbol obtenido es un árbol binario correspondiente a uncódigo de Huffman para dichos símbolos 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.


En el ejemplo de la derecha:•Entre paréntesis 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 elnúmero asignado a cadanodo.

Por tanto, este árbol es elcorrespondiente al código deHuffman para estos símboloscon las probabilidades que seobtienen a partir del número deveces que ha aparecido cadasímbolo dividido por el númerode símbolo leídos.


En el código Huffman adaptativo ni el transmisor ni elreceptor conocen al principio las probabilidades de lossímbolos. Por eso:

1. Codificador y decodificar comienzan con un árbol con unnodo único que corresponde a todos los símbolos notransmitidos (NYT) y que tiene peso cero.

2. Mientras progresa la transmisión se añadirán nodos alárbol correspondientes a símbolos que aparezcan porprimera vez, se modificarán los pesos (tanto si elsímbolo es nuevo como si es ya existente) y seactualizará el árbol para que siga cumpliendo the siblingproperty (siga siendo de Huffman).


El algoritmo de Huffman adaptativo consta de los siguienteselementos:

1. Inicialización (la misma para el codificador ydecodificador).

Antes de describir estas partes comentaremos brevemente sobre la codificación de los símbolos:

2 Algoritmo de codificación.

3. Algoritmo de decodificación.

4. Proceso de actualización del árbol para que mantengathe sibling property.


Codificación de un símbolo que aparece por primeravez:

•Salvo que sea el primero de todos lo símbolos de lasecuencia, la codificación de un símbolo que aparece porprimera vez consta de la codificación que proporciona elárbol del nodo NYT seguido de un código fijo para el símboloque deben conocer codificador y decodificador

•En el caso en que sea el primer símbolo que aparece en lasecuencia no necesitamos transmitir el código de NYT.

Si el símbolo ya ha aparecido

•Utilizamos la codificación que proporciona el árbol que vamos construyendo.


Inicialización del código de Huffman adaptativo (tanto para el codificador como para el decodificador

1. Nuestro árbol ha de codificar n+1 símbolos incluyendo el correspondiente a NYT,

2. Necesitamos por tanto 2(n+1)-1=2n+1 números para los nodos,

3. El árbol de Huffman inicial tiene un nodo único:

0

NYT2n+1

Número del nodo

peso


1. Si encontramos un símbolo nuevo (ver nota) entoncesgenerar el código del nodo NYT seguido del código fijo(ver nota) del símbolo. Añadir el nuevo símbolo alárbol,

2. Si el símbolo ya está presente, generar su códigousando el árbol,

3. Actualizar el árbol para que siga conservando thesibling property.

Nota: Recordemos que para el primer símbolo no hace falta transmitir elcódigo de NYT. El código fijo es conocido al principio por codificador ydecodificador.

Algoritmo de codificación para el código Huffman adaptativo


1. Decodificar el símbolo usando el árbol actual,

2. Si encontramos el nodo NYT, usar el código fijo paradecodificar el símbolo que viene a continuación. Añadirel nuevo símbolo al árbol,

3. Actualizar el árbol para que siga conservando thesibling property.

Nota: recordar, de nuevo, que el primer símbolo no va precedido por elcódigo de NYT

Algoritmo de decodificación para el código Huffman adaptativo


1. Sea y la hoja (símbolo) con peso x,2. Si y es la raíz, aumentar x en 1 y salir3. Intercambiar y con el nodo con el número 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

Actualización del árbol para el código Huffman adaptativo


Ejemplo

Consideremos el alfabeto A={a,b,c,d} y realicemos la codificación de la secuencia

aabcdad

Primero vemos el número de nodos que necesitaremos

Nodos=2*4+1=9

Los códigos de longitud fija que usamos son

a 000 b 001 c 010 d 011


• aabcdad en A={a,b,c,d}

salida=000

NYT

9

0 7

a

8

0

0

Paso 1 del algoritmo de codificación

0

NYT

9Inicialización

0 1


NYT

9

0 7

a

8

0

1

Paso 3 del algoritmo de codificación (actualización)

Paso 4 dentro del algoritmo de actualización

NYT

9

0 7

a

8

1

1


0 1

0 1


• aabcdad

salida=0001

NYT

9

0 7

a

8

1

1

Paso 2 del algoritmo de codificación

Tenemos

NYT

9

0 7

a

8

1

1

salida=000

0 1

0 1


NYT

9

0 7

a

8

1

2



NYT

9

0 7

a

8

2

2


0 1

0 1


• 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 codificación

Código de b

Código de NYT

NYT

0

0

0 65

b

0

0 1


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


a1

9

7 8

3

2

NYT

0

1

1 6

b

0

0 1

5


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

Código de NYT

c

Algoritmo de codificación sin adaptación del árbol

0 1


adaptación 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 6

b

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


• 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


d

NYT

0

0

1

1


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



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

adaptación del árbolCAMBIO DE ORDEN


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


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



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



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


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


salida=00010001000100000110


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



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


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


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


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


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


Ejercicio:

Usando el código fijo

a=000, b=001, c=010, d=011

Decodificar la secuencia 00110000 usando el código deHuffman adaptativo.

Aunque el código de Huffman es uno de los métodos decodificación de longitud de palabra variable másconocidos, existen otros métodos algo menos conocidospero también muy útiles. En particular los métodos deGolomb-Rice y Tunstall que veremos a continuación.


III.4 Código 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 número de veces (racha=run length)que aparece A antes de que aparezca Ac.

Suponemos que las realizaciones son independientes.

Observa que si p es próximo a uno esperamos que aparezcamuchas veces el suceso A antes de que aparezca un Ac.


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 números del 0 al 36).

3. Puntos en blanco y negro como podría ser el contenido de una hoja.


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 podría estimar p.

Los fabricantes de impresoras suponen p=0.05

Lo que queremos codificar son las realizaciones de la variablealeatoria N definida por

N= número de veces que aparece A antes de que aparezcaAc.

Esta variable tiene la siguiente distribución de probabilidad

P(N=n)=pnq n=0,1,2,….


Una posible codificación sería:

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 código

. .

. .

Este código recibe el nombre decódigo unario.

¿Cuál es el número medio de bits queeste código, C, usa para codificar lavariable N?


( ) pppq

pq

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 próximo a uno Cp(N) es muygrande.¿Cuánto vale la entropía de la variable aleatoria N enfunción de p?.

Recuerda que q=1-p


( ) ( )

( )( )

( )ppqqp

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


Observa que para p grande deberíamos ser capaces de mejorar el código unario.

Sin embargo, para p=0.5, Cp(N) –Hp(N)=0 y el código unario es el mejor que podemos utlizar.

Representación gráfica de Cp(N) –Hp(N)


Veamos la idea del código 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.

¿Cómo están relacionados n2 y n1?.

pnpn

pnn

qqnNP

qqpnNPlog1log

1

log2

11

22

225.0)(5.0

2)(+−===×=

===

de dondepnpn log1log 12 +−=

o⎟⎟⎠

⎞⎜⎜⎝

⎛−+=−=

pn

pnn

log1

log1

112

Muy importante


Intutivamente, nos gustaría que el código de n2 fuese un bit más largo que el de n1. Esto es lo que consigue el código de Golomb.

Antes un poco de notación

⎣ ⎦⎡ ⎤

⎣ ⎦⎡ ⎤ 45.3

35.3arribapor x a próximo más enteroabajopor x a próximo más entero

==

==

xx

Continuemos con el código de Golomb. Sea

⎥⎥

⎤⎢⎢

⎡−=

pw

log1


QwnRywnQ −=⎥⎦⎥

⎢⎣⎢=Para cada n sean

En otras palabras Q es el cociente y R es el resto de la división de n por w

(Observa que si n’=n+w entonces Q’=Q+1)

La codificación 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 código va a ser mejorado después


Supongamos que p=2^(-1/4) ~ 0.8409, entonces

⎡ ⎤ 2log,4 == ww

N Q R Representación0 0 0 0001 0 1 0012 0 2 0103 0 3 0114 1 0 10005 1 1 10016 1 2 1010


Supongamos que p=2^(-1/5) , entonces

⎡ ⎤ 3log,5 == ww



La parte sufijo del código es mejorable cuando w no sea unapotencia de 2, si usamos la siguiente representación delongitud variable:

Sea R ε {0,1,…,w-1}

⎡ ⎤ ⎡ ⎤ códigos 2Msobran nos bits logw Usando logw w−=

⎣ ⎦ bits logwcon binariación representa usamos MR Si <

⎡ ⎤ R de bits logen ción representa la usamos R Si MwM +≥


10

0 1

w=2

0

0 1

21

0 1

w=3

Resto R Representación

0 0

1 1


0 0

1 10

2 11

Ejemplos:

Los arcos determinan el códigoLos nodos contienen el resto


43

0 1

0 1

2

0 1

w=5


0 00

1 01

2 10

3 110

4 111

10

0 1

0 1

32

0 1

w=4


0 00

1 01

2 10

3 11

10

0 1

Más ejemplos de la representación de la parte sufijo


Supongamos que p=2-1/5 . Entonces

⎡ ⎤ 3log,5 == ww


Otro ejemplo de código Gollub:

CÓDIGO

GOLLUB


III.5 Código Tunstall Es un código de longitud fija en el que cada palabra del código puede representarun número diferente de letras.

Supongamos que tenemos inicialmente m símbolos y queremos usar como salida representaciones de longitud fija con n bits, siendo 2n>m. Suponemos que las realizaciones de dichos símbolos son independientes. Construcción del árbol:

•Formar un árbol con una raíz y m hijos con arcos etiquetados con los símbolos del alfabeto,•Si el número 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 símbolos del camino de la raíz a las hojas) y expandirla para que tenga m hijos. Volver al paso anterior,

Código de Tunstall


*Justificación de la condición 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 expansióntenemos l-1+m que necesitaremos que sea menor que 2n yaque necesitamos dejarnos al menos un código libre como yaveremos.

Una vez construido el árbol le asignamos un código de longitud n a cada una de las hojas.


Supongamos que P(A)=0.6, P(B)=0.3 y P(C)=0.1 y n=3. Por tanto, deseamos generar una representación de longitud fija 3.

Paso 1

A B C

0.6 0.3 0.1


l=3, 3+2=5, 5<8 Seguimos

Paso 2

Paso 3

A B C

A B C

0.3 0.1

0.36 0.18 0.06


l=5, 5+2=7, 7<8 Seguimos

Paso 2

Paso 3

A B C

A B C

A B C


L=7, 7+2=9, 9 ≥8, Salimos

Paso 2

Codificación 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 código 111


El código de Tunstall ha generado la siguiente representación

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 representación.

Para codificar el AA enviamos el código no utilizado (111) y un código fijo para AA.Generalmente, si hay k nodos internos en el árbol necesitaremos k-1 códigos fijos. En nuestro problema A y AA.


Otro ejemplo. Supongamos P(A)=0.9 y P(B)=0.1 y usamos n=2.

El árbol que construiríamos sería

A B

A B

00 01

10

Y dejaríamos el 11 para enviar el código de A

Entrada SalidaAA 00

AB 01

B 10


Si usásemos las cuatro palabras tendríamos

y no podríamos enviar código para A

Entrada SalidaAAA 00

AAB 01

AB 10

B 11

A B

A B

10

11

A B

00 01


Entrada Salida

AAA 000

AAB 001

AAC 010

AB 011

AC 100

B 101

C 110

Problema: considera la tabla en la que el código 111 es utilizado para anunciar que a continuación viene el código de A o AA.

¿Qué proceso seguiríamos para codificar las secuencias

CABBAACCBBACA

?


III.6 Aplicaciones del código de Huffman En las clases de prácticas se estudiarán las siguientesaplicaciones:

Imágenes: Usaremos imágenes 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 píxeles están muy correladoscodificaremos la diferencia entre un píxel y el anterior usandoHuffman, veremos que mejoramos el nivel de compresión.

También usaremos imágenes binarias y códigos de Huffmanadaptativos


Texto: Usaremos diferentes tipos de texto y aplicaremos Huffman habiendo calculado antes las probabilidades de cada letra a partir del texto.

Eliminar la correlación aquí es más complicado y veremos como hacerlo en capítulos posteriores.

Sonido: Cada canal estéreo se muestrea a 44.1 kHz y utiliza una representación de 16 bits. Aunque no vamos a construir el código Huffman (tendría 216 entradas), calcularemos la entropía y por tanto una estimación de la mejor compresión que podemos alcanzar. Podemos también eliminar (o disminuir) la correlación entre los datos y volver a calcular la entropía y por tanto una estimación de la compresión a alcanzar con este modelo.


III.7 Resumen del tema

1. Código de Huffman, no adaptativo y adaptativo,2. Códigos unarios y de Golomb,3. Códigos de Tunstall,4. Aplicaciones.


III.8 BibliografíaK. Sayood, “Introduction to Data Compression”, Morgan and Kaufmann, 2000.Material adicional de la asignatura•G. Langdon, Data Compression, Universidad de California, 1999. (langdon_Run-Length_Encodings.pdf).•Roque Marín,”Compresores estadísticos”, Universidad de Murcia, (00_compresores_estadísticos_univ.murcia.pdf).•Notas sobre el código de Golomb (Golomb_Notes.pdf).•Otra presentación sobre compresores estadísticos, (00_compresores_estadísticos_II.pdf).•Temas 2, 3 y 4 del curso de compresión de datos impartido en Stony Brook University (NY, USA), (tema[2,3,4]_stony.pdf).•Tema 3 del curso de compresión 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.


Apéndice: longitud de los códigos de Huffman y códigos de Huffman extendidos

Dado un código 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 Codificación sin Ruido:Dada una fuente S = {x1, ... xm} y un alfabeto binario, existe al menos un código prefijo C cuya longitud media cumple

siendo ε cualquier número real arbitrariamente pequeño.

ε+< )(SHn


1)()( +≤≤ qq

q SHnSH

1)()( +≤≤ SHqnqSHq

qSHnSH 1)()( +≤≤

La demostración 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 ecuación en función de la entropía de la fuente original tendremos

dividiendo por q obtendremos

Basta con elegir un tamaño de bloque q suficientemente grande para conseguir 1/q < ε para que se cumpla lo afirmado por el teorema.

03 CODIGO DE HUFFMAN

Documents

Transcript of 03 CODIGO DE HUFFMAN