PDF de programación - Algoritmos básicos para la compresión sin pérdidas - (CTI: Parte II de la Lección 2, Compresores sin pérdidas)

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Algoritmos básicos para la compresión sin

pérdidas

(CTI: Parte II de la Lección 2, Compresores sin pérdidas)

Ramiro Moreno Chiral

Dpt. Matemàtica (UdL)

Febrero de 2010

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

1 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Índice

1 Algoritmos Huffman

2 Algoritmos Lempel–Ziv

3 Compresión aritmética

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

2 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Índice

1 Algoritmos Huffman

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

2 Algoritmos Lempel–Ziv

3 Compresión aritmética

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

3 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Resumen

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

4 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Resumen

Veremos en este apartado

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

4 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Resumen

Veremos en este apartado

Por qué los códigos Huffman son optimales.

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

4 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Resumen

Veremos en este apartado

Por qué los códigos Huffman son optimales.
El algoritmo del Huffman básico, algoritmo en dos pasos.

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

4 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Resumen

Veremos en este apartado

Por qué los códigos Huffman son optimales.
El algoritmo del Huffman básico, algoritmo en dos pasos.
Finalmente, el algoritmo de Gallager–Knuth para los
Huffman adaptativos o en un paso o universal.

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

4 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Cota inferior de la longitud media de un código
instantáneo

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

5 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Cota inferior de la longitud media de un código
instantáneo

Proposición
La longitud esperada, L, no necesariamente mínima, de un
código instantáneo d-ario para una fuente simple S = (X , X ),
con |X| = r, es

L ≥ Hd (X ),

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

5 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Cota inferior de la longitud media de un código
instantáneo

Proposición
La longitud esperada, L, no necesariamente mínima, de un
código instantáneo d-ario para una fuente simple S = (X , X ),
con |X| = r, es

L ≥ Hd (X ),

alcanzándose la igualdad cuando pi = d−li , 1 ≤ i ≤ r, es decir,
cuando X tiene una distribución de probabilidad d-ádica
respecto a las longitudes de las palabras–código.

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

5 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Cota inferior de la longitud media de un código
instantáneo

Proposición
La longitud esperada, L, no necesariamente mínima, de un
código instantáneo d-ario para una fuente simple S = (X , X ),
con |X| = r, es

L ≥ Hd (X ),

alcanzándose la igualdad cuando pi = d−li , 1 ≤ i ≤ r, es decir,
cuando X tiene una distribución de probabilidad d-ádica
respecto a las longitudes de las palabras–código.

Para esas fuentes d-ádicas los códigos de Shannon alcanzan
su longitud media mínima, igualando la entropía.

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

5 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Árboles ponderados por hojas

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

6 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Árboles ponderados por hojas

Definición

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

6 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Árboles ponderados por hojas

Definición
Dados un árbol con raíz T , con r hojas, y un conjunto de pesos
F = {f1, . . . , fr}, fi ∈ Z>0, asociamos a cada hoja un peso fi y a
cada vértice interno la suma de los pesos de las hojas
descendientes de ese vértice.

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

6 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Árboles ponderados por hojas

Definición
Dados un árbol con raíz T , con r hojas, y un conjunto de pesos
F = {f1, . . . , fr}, fi ∈ Z>0, asociamos a cada hoja un peso fi y a
cada vértice interno la suma de los pesos de las hojas
descendientes de ese vértice. Llamaremos árbol ponderado
por hojas según F al par (T , F )

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

6 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Árboles ponderados por hojas

Definición
Dados un árbol con raíz T , con r hojas, y un conjunto de pesos
F = {f1, . . . , fr}, fi ∈ Z>0, asociamos a cada hoja un peso fi y a
cada vértice interno la suma de los pesos de las hojas
descendientes de ese vértice. Llamaremos árbol ponderado
por hojas según F al par (T , F ) y definimos el peso de (T , F )
como

r

Peso(T ) =

fihi ,

siendo hi , 1 ≤ i ≤ r, los niveles de las hojas de T .

i=1

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

6 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Costo de un código

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

7 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Costo de un código

Definición
Sea C un código instantáneo par a una fuente S con
estadística F = {f1, . . . , fr}, y sea T su árbol de representación
literal.

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

7 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Costo de un código

Definición
Sea C un código instantáneo par a una fuente S con
estadística F = {f1, . . . , fr}, y sea T su árbol de representación
literal.

Llamaremos árbol ponderado asociado a C al árbol
ponderado por hojas de T según F .

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

7 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Costo de un código

Definición
Sea C un código instantáneo par a una fuente S con
estadística F = {f1, . . . , fr}, y sea T su árbol de representación
literal.

Llamaremos árbol ponderado asociado a C al árbol
ponderado por hojas de T según F .
Llamaremos costo del código C al peso de su árbol
ponderado asociado.

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

7 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Costo de un código

Definición
Sea C un código instantáneo par a una fuente S con
estadística F = {f1, . . . , fr}, y sea T su árbol de representación
literal.

Llamaremos árbol ponderado asociado a C al árbol
ponderado por hojas de T según F .
Llamaremos costo del código C al peso de su árbol
ponderado asociado.
Diremos que C es un código de costo mínimo, o un código
optimal, si cualquier otro código instantáneo sobre S tiene
un costo mayor o igual.

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

7 / 25

Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adaptativo

Costo de un código: Ejemplo

Ramiro Moreno (Matemàtica, UdL)

Algoritmos básicos compresión sin pérdidas

Febrero de 2010

8 / 25

•00•1100•111001111•;1000;500•;50110;300•;201110;150111;51•;1000;500•;50110;300•;201110;150111;51•;1000;500•;50110;300•;201110;150111;51•;10;0’50•;0’5110;0’30•;0’21110;0’150111;0’051Algoritmos Huffman
Algoritmos Lempel–Ziv
Compresión aritmética

Los códigos Huffman son optimales
Huffman básico
Huffman adap