Tema 3: Codificación Huffman · El código de Huffman necesita conocer la probabilidad de...

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

Contenidos


III.1 Objetivos del tema

En este tema vamos a describir un algoritmo de codificación muy conocido: el código de Huffman. Primero supondremos que es conocida la distribución de probabilidad de la fuente y luego construiremos el código cuando dichas probabilidades 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 a compresió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ódigo Huffman) es un código prefijo óptimo para un conjunto dado 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 observaciones sobre los códigos prefijo óptimos:

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

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

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

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


Para probar la segunda condición usaremos reducción al absurdo.

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

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

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


Como estos símbolos son los menos probables ninguna otra palabra puede ser más larga que estas dos y por tanto no hay 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.


Genera el código de Huffmancorrespondiente a las siguientes 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.5P( )=0.4P( )=0.4P( )=0.09P( )=0.09P( E )=0.01P( 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 que recorrer el árbol del código prefijo correspondiente al código Huffman 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. El nú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 canal iría en media bien. Sin embargo, si tenemos que transmitir muchas veces seguidas los símbolos D o E podemos necesitar un buffer mucho mayor.

Lo mejor sería que, manteniendo la misma longitud media, pudiésemos diseñar un código de Huffman con menor varianza 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 en las probabilidades de los nodos, los nodos ya utilizados lo má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 de aparición de cada símbolo.

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

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

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


Consideremos un árbol binario correspondiente a un alfabeto de tamañ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 dos campos: Número del nodo y peso del nodo.

El número de nodo es un número único asignado a cada nodo del á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 veces que aparece el símbolo correspondiente y el de uno interno la suma de los pesos de sus dos hijos. Los pesos los notaremos x1,…,x2n-1.


Puede probarse que:

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

El árbol obtenido es un árbol binario correspondiente a un código de Huffman para dichos símbolos.

La propiedad anterior recibe el nombre de sibling property o node number invariant.


En el ejemplo de la derecha:•Entre paréntesis los pesos de cada nodo. (16)

(7)

(9)

(3) (4)

(2)(2)(1) (2)

1 2

7

8

5 6

9

3 4

número asignado a cada nodo.

correspondiente al código de Huffman para estos símbolos con las probabilidades que se obtienen a partir del número de veces que ha aparecido cada símbolo dividido por el número de símbolo leídos.


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

1. Codificador y decodificar comienzan con un árbol con un nodo único que corresponde a todos los símbolos no transmitidos (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 por primera vez, se modificarán los pesos (tanto si el símbolo es nuevo como si es ya existente) y se actualizará el árbol para que siga cumpliendo the siblingproperty (siga siendo de Huffman).


El algoritmo de Huffman adaptativo consta de los siguientes elementos:

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

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 mantenga the sibling property.


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

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

•En el caso en que sea el primer símbolo que aparece en la secuencia 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 entonces generar el código del nodo NYT seguido del código fijo del símbolo. Añadir el nuevo símbolo al árbol,

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

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

Nota: Recordemos que para el primer símbolo no hace falta transmitir el código de NYT.

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 para decodificar el símbolo que viene a continuación. Añadir el 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 el có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

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

algoritmo de actualización

0 1

0 1


•• aaaabcdadbcdad

salida=0001salida=0001

NYTNYT

99

00 77

aa

88

11

11

Paso 2 del algoritmo de algoritmo de codificación codificación

Tenemos Tenemos

NYTNYT

99

00 77

aa

88

11

11

salida=000salida=000

00 11

00 11


NYT

9

0 7

a

8

1

2


Paso 4 dentro del algoritmo de actualización

NYT

9

0 7

a

8

2

2

algoritmo de actualización

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 1

10



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

05

0 1

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 de Huffman adaptativo.

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


III.4 Código de Golomb

Consideremos un suceso A que tiene probabilidad p y su complementario Ac que tiene probabilidad q=1-p (obviamente p+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 aparezca muchas 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 variable aleatoria N definida por

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

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 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 codificamediante n unos seguidos de un cero. Es decir,

0 01 102 110

3 1110. .. .

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

¿Cuál es el número medio de bits que este código, C, usa para codificar la variable N?

N código


( ) 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 muy grande.¿Cuánto vale la entropía de la variable aleatoria N en funció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 bitmá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 Supongamos que p=2p=2^(^(--1/4) 1/4) ~ ~ 0.8409, entonces 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 Supongamos que p=2p=2^(^(--1/5) 1/5) , entonces , entonces

⎡ ⎤ 3log,5 == ww



La parte sufijo del código es mejorable cuando w no sea una potencia de 2, si usamos la siguiente representación de longitud 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 +≥


110000 11

w=2w=2

00

00 11

2211

00 11

w=3w=3

Resto R Representación

0 0

1 1


0 0

1 10

2 11

Ejemplos: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 TunstallEs un código de longitud fija en el que cada palabra del código puede representar un 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 y de esa una salen m. Por tanto una vez realizada la expansión tenemos l-1+m que necesitaremos que sea menor que 2n ya que necesitamos dejarnos al menos un código libre como ya veremos.

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 011 100

101 110Observa que tenemos libre la palabra del código 111

000 001 010


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

Entrada Salida

B 101

AAA 000

AAB

AAC

AB

AC

C

001

010

011

100

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

10


Si usásemos las cuatro palabras tendríamos

y no podríamos enviar código para A

Entrada Salida

AAB 01

AAA 00

AB

B

10

11

A B

A B

10

11

A B

00 01


Entrada Salida

B 101

AAA 000

AAB

AAC

AB

AC

C

001

010

011

100

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 HuffmanEn las clases de prácticas se estudiarán las siguientes aplicaciones:

Imágenes: Usaremos imágenes de niveles de gris, es decir, que en cada punto toman un valor entre 0 y 255. Estimaremos la probabilidad de ocurrencia de cada nivel de gris usando el histograma y aplicaremos Huffman. El modelo será por tanto no adaptativo.

Como los valores de los píxeles están muy correladoscodificaremos la diferencia entre un píxel y el anterior usando Huffman, 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 BrookUniversity (NY, USA), (tema[2,3,4]_stony.pdf).•Tema 3 del curso de compresión de datos impartido en Chalmers University ofTechnology (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.

Tema 3: Codificación Huffman · El código de Huffman necesita conocer la probabilidad de...

Documents

Transcript of Tema 3: Codificación Huffman · El código de Huffman necesita conocer la probabilidad de...