Slides TD IV - clases (29)

Vista previa del material en texto

TD4 2022TD4 2022 2
Información de Shannon
▪ Una forma de expresar la sorpresa es cuantificándola en 
base a la probabilidad de la salida de la variable aleatoria.
▪ Es más informativo saber que ocurrió un evento improbable, 
que conocer la ocurrencia de uno probable. 
TD4 2022TD4 2022 3
Sorpresa promedio de una variable
▪ No estamos interesados en un solo evento o valor de una 
variable aleatoria. 
▪ En general, nos va a interesar saber cuánta sorpresa hay en 
promedio para todo el conjunto de valores de una variable 
aleatoria. 
TD4 2022TD4 2022 4
Entropía de una variable aleatoria
▪ Calculamos la entropía como:
bits
Distribución de probabilidades
de la variable aleatoria X
TD4 2022TD4 2022 5
Interpretando la Entropía
▪ ¿Cuánta información contiene la posición del peón en un 
tablero de ajedrez? → 6 bits
▪ El valor de entropía depende solo de la distribución de 
probabilidades, no de los símbolos de la variable aleatoria. 
▪ Si duplicamos la cantidad de casillas en el tablero de 
ajedrez, o en las caras de un dado, la entropía se incrementa 
en 1 bit. 
TD4 2022TD4 2022 6
Bits, Shannons y Bans
▪ La unidad de medición de información depende de la base del 
logaritmo que estemos utilizando. Es similar a lo que sucede 
cuando medimos agua en una receta y usamos litros o tazas. 
▪ Si medimos información usando logaritmo natural (base e = 
2.72), entonces las unidades se llaman nats en vez de bits 
(base 2). 
▪ Si usamos logaritmos en base 10, las unidades se llaman bans.
▪ Si usamos logaritmos en base 2, las unidades son los bits o 
Shannons (Sh)
TD4 2022TD4 2022 7
Primer teorema de Shannon (1948)
▪ Si deseamos comunicar muestras extraídas de alguna 
distribución, en promedio necesitaremos al menos tantos 
símbolos como la entropía de esa distribución para comunicar 
sin ambigüedades esas muestras. 
▪ La entropía proporciona un límite inferior sobre cuánto 
podemos comprimir nuestra descripción de las muestras de la 
distribución antes de que inevitablemente perdamos 
información.
TD4 2022TD4 2022
▪ Calculamos la tasa de transmisión R como:
▪ Eficiencia de un código: ratio entre la cantidad promedio de 
dígitos binarios por palabra en el código L(X) y la entropía H(S) 
promedio de los símbolos del alfabeto:
8
Eficiencia en la codificación de datos
Capacidad del canal
Entropía
bits/símbolo
3 dígitos binarios/símbolo
bits/dígito binario
TD4 2022TD4 2022 9
Fuente: dado de 6 caras
▪ Capacidad del canal
▪ Entropía
bits/s
bits/símbolo bits/dígito binario
▪ Según el Primer Teorema de 
Shannon, la tasa máxima de 
transmisión se puede calcular 
como:
bits/s
bits/símbolo
símbolos/s
▪ Eficiencia:
TD4 2022TD4 2022
Fuente: dado de 6 caras
▪ Tasa máxima (teórica):
bits/s
bits/símbolo
símbolos/s
▪ Tasa efectiva:
símbolos/s
bits/s
bits/símbolo
TD4 2022TD4 2022 11
Eficiencia en la codificación de datos
▪ No siempre que transmitimos un dígito binario estamos 
transmitiendo un bit de información.
Alice
Bob
Saqué un 4
Sacó un 4!!!
Alice envía a Bob 
el código del 4
▪ Solo se alcanza la máxima 
capacidad de transmisión 
cuando cada dígito binario 
transporta la mayor cantidad 
de información posible.
TD4 2022TD4 2022
Bob
Saqué un 4, 
un 3 y un 1 Sacó un 4, 
un 3 y un 1
Alice envía a Bob 
el código del 4,3,1
12
Recodificación de la fuente
▪ Idea! Codificar más de un símbolo a la vez. Por ejemplo, 3 
símbolos seguidos:
Alice
TD4 2022TD4 2022
Si los valores de la variable no 
representan un número entero de bits, se 
puede mejorar la codificación 
combinando varios símbolos en el código
Recodificación de la fuente
▪ Tasa máxima (teórica):
bits/s
bits/símbolo
símbolos/s
▪ Tasa efectiva:
símbolos/s
bits/s
bits/símbolo
símbolos/s
TD4 2022TD4 2022 14
Compresión de datos
▪ Consideremos el caso en el que la variable no tiene una 
distribución uniforme. Por ejemplo, transmitir la suma de las 
caras de dos dados:
TD4 2022TD4 2022 15
Compresión de datos
▪ Consideremos el caso en el que la variable no tiene una 
distribución uniforme. Por ejemplo, transmitir la suma de las 
caras de dos dados:
TD4 2022TD4 2022 16
Compresión de datos
▪ Consideremos el caso en el que la variable no tiene una 
distribución uniforme. Por ejemplo, transmitir la suma de las 
caras de dos dados:
TD4 2022TD4 2022 17
Compresión de datos
▪ Consideremos el caso en el que la variable no tiene una 
distribución uniforme. Por ejemplo, transmitir la suma de las 
caras de dos dados:
▪ Entropía:
bits/símbolo
TD4 2022TD4 2022 18
Compresión de datos
▪ Consideremos el caso en el que la variable no tiene una 
distribución uniforme. Por ejemplo, transmitir la suma de las 
caras de dos dados:
▪ Entropía:
bits/símbolo
▪ Eficiencia:
bits/dígito binario
TD4 2022TD4 2022 19
Compresión de datos
▪ Modelo general:
Datos 
originales
Datos 
comprimidos
Datos 
decodificados
Datos comprimidos
Canal de comunicación
Almacenamiento
Genera una representación 
compacta de los datos de 
entrada (mensaje de la fuente)
Reconstruye el mensaje original (o 
una aproximación) a partir de la 
representación comprimida
TD4 2022TD4 2022 20
Métodos de compresión
▪ Sin pérdida o reversibles:
• Mantienen la integridad de la información: los datos 
descomprimidos coinciden con los datos originales
• Se aplica a texto, bases de datos, código fuente, imágenes, 
etc.
• Tasas de compresión moderadas: 2:1 (texto), 4:1 (imágenes)
• La longitud media del código está acotada por la entropía
TD4 2022TD4 2022 21
Métodos de compresión
▪ Con pérdida o irreversibles:
• No mantienen la integridad de la información: los datos 
descomprimidos son una aproximación de los datos 
originales
• Se aplican a imágenes, video, sonido, etc.
• Tasas de compresión altas: 30:1 (imágenes), 200:1 (video)
• No tienen como límite la entropía (pérdida de información). 
TD4 2022TD4 2022 22
Métodos de compresión sin pérdida
Métodos de compresión 
sin pérdida
TD4 2022TD4 2022 23
Métodos de compresión sin pérdida
Métodos de compresión 
sin pérdida
Estadísticos
(codifican un 
símbolo por vez)
Con diccionario
(codifican secuencias de 
símbolos)
TD4 2022TD4 2022 24
Métodos de compresión sin pérdida
Métodos de compresión 
sin pérdida
Estadísticos
(codifican un 
símbolo por vez)
Con diccionario
(codifican secuencias de 
símbolos)
Estáticos 
(la distribución de probabilidades se asume universal)
Semiestáticos 
(la distribución de probabilidades se precomputa a partir de los datos)
Adaptativos/Dinámicos
(la distribución de probabilidades se va actualizando al leer cada símbolo)
Estáticos 
(diccionario universal)
Semiestáticos 
(el diccionario se precomputa a partir de los datos)
Adaptativos/Dinámicos
(el diccionario se va actualizando al leer cada símbolo)
TD4 2022TD4 2022 25
Métodos de compresión sin pérdida
▪ Métodos estáticos:
Ventajas:
• Requieren una única pasada por los datos para codificar
• No es necesario transmitir/almacenar la distribución de 
probabilidades al decodificador. 
TD4 2022TD4 2022 26
Métodos de compresión sin pérdida
▪ Métodos estáticos:
Ventajas:
• Requieren una única pasada por los datos para codificar
• No es necesario transmitir/almacenar la distribución de 
probabilidades al decodificador. 
Desventajas:
• La distribución de probabilidades es fija y puede diferir de 
los datos a codificar
TD4 2022TD4 2022 27
Métodos de compresión sin pérdida
▪ Métodos semiestáticos:
Ventajas:
• La distribución de probabilidades se ajusta a los datos a 
comprimir 
TD4 2022TD4 2022 28
Métodos de compresión sin pérdida
▪ Métodos semiestáticos:
Ventajas:
• La distribución de probabilidades se ajusta a los datos a 
comprimir 
Desventajas:
• Requiere dos pasadas por los datos: construcción del 
código y codificación del mensaje
• Se debe transmitir/almacenar la distribución de 
probabilidades al decodificador
TD4 2022TD4 2022 29
Métodos de compresión sin pérdida
▪ Métodos adaptativos/dinámicos:
Ventajas:
• Requierenuna única pasada por los datos para codificar
• La distribución de probabilidades se va ajustando al 
mensaje a medida que se codifica
• No se debe transmitir/almacenar la distribución de 
probabilidades al decodificador
TD4 2022TD4 2022 30
Métodos de compresión sin pérdida
▪ Métodos adaptativos/dinámicos:
Ventajas:
• Requieren una única pasada por los datos para codificar
• La distribución de probabilidades se va ajustando al 
mensaje a medida que se codifica
• No se debe transmitir/almacenar la distribución de 
probabilidades al decodificador
Desventajas:
• Algoritmos complejos 
TD4 2022TD4 2022 31
Código de Huffman (1952)
▪ Idea! Asignar códigos más cortos a 
los símbolos más frecuentes (y 
viceversa). 
▪ Requiere conocer las probabilidades 
de ocurrencia. 
▪ Asume eventos independientes: los 
resultados de cada experimento 
aleatorio no están conectados entre 
sí de ninguna manera.
TD4 2022TD4 2022 32
Código de Huffman (1952)
▪ Método de compresión sin pérdida
▪ Dos versiones: semiestática y 
adaptativa/dinámica. 
▪ Construye árboles binarios a partir 
de los símbolos de la fuente.
▪ Forma parte de la especificación de 
estándares y formatos de 
compresión muy conocidos como 
JPEG, MP3, MPEG y GZIP. 
TD4 2022TD4 2022 33
Código de Huffman: Ejemplo
▪ Ejemplo de construcción del código:
A
B
C
D
Sí
m
bo
lo
E
TD4 2022TD4 2022 34
Código de Huffman: Ejemplo
▪ Ejemplo de construcción del código:
A
B
C
D
Sí
m
bo
lo
E
1
0
TD4 2022TD4 2022 35
Código de Huffman: Ejemplo
▪ Ejemplo de construcción del código:
A
B
C
D
Sí
m
bo
lo
E
1
0
TD4 2022TD4 2022 36
Código de Huffman: Ejemplo
▪ Ejemplo de construcción del código:
A
B
C
D
Sí
m
bo
lo
E
1
0
1
0
TD4 2022TD4 2022 37
Código de Huffman: Ejemplo
▪ Ejemplo de construcción del código:
A
B
C
D
Sí
m
bo
lo
E
1
0
1
0
TD4 2022TD4 2022 38
Código de Huffman: Ejemplo
▪ Ejemplo de construcción del código:
A
B
C
D
Sí
m
bo
lo
E
1
0
1
0
1
0
TD4 2022TD4 2022 39
Código de Huffman: Ejemplo
▪ Ejemplo de construcción del código:
A
B
C
D
Sí
m
bo
lo
E
1
0
1
0
1
0
TD4 2022TD4 2022 40
Código de Huffman: Ejemplo
▪ Ejemplo de construcción del código:
A
B
C
D
Sí
m
bo
lo
1
0
E
1
0
1
0
1
0
TD4 2022TD4 2022 41
Código de Huffman: Ejemplo
▪ Ejemplo de construcción del código:
A
B
C
D
Sí
m
bo
lo
1
0
E
1
0
1
0
1
0
TD4 2022TD4 2022 42
Código de Huffman: Algoritmo
▪ Algoritmo de codificación (semiestático): 
• Paso 1: recorrer el mensaje para obtener la 
probabilidades de los símbolos y preparar las hojas del 
árbol.
• Paso 2: Construir iterativamente el árbol binario hasta 
llegar a la raíz (con probabilidad 1.) 
• Paso 3: Codificar el mensaje usando el árbol (paso 2). 
TD4 2022TD4 2022 43
Código de Huffman: Algoritmo
▪ Algoritmo de codificación (semiestático): 
• Paso 1: recorrer el mensaje para obtener la 
probabilidades de los símbolos y preparar las hojas del 
árbol.
• Paso 2: Construir iterativamente el árbol binario hasta 
llegar a la raíz (con probabilidad 1.) 
• Paso 3: Codificar el mensaje usando el árbol (paso 2). 
▪ Debemos agregar una cabecera con las probabilidades de cada 
símbolo para que el decodificador pueda reconstruir el mensaje. 
{S,p} mensaje codificado
TD4 2022TD4 2022 44
Ejercicio! 
▪ Construir la codificación de Huffman para la fuente que emite 
la suma de dos dados. Comparar la eficiencia respecto a una 
codificación directa en binario con 4 bits. 
TD4 2022TD4 2022 45
Ejercicio! 
▪ Construir la codificación de Huffman para la fuente que emite 
la suma de dos dados. Comparar la eficiencia respecto a una 
codificación directa en binario con 4 bits. 
TD4 2022TD4 2022 46
Ejercicio! 
▪ Construir la codificación de Huffman para la fuente que emite 
la suma de dos dados. Comparar la eficiencia respecto a una 
codificación directa en binario con 4 bits. 
▪ Eficiencia código 4 bits:
bits/dígito binario
▪ Eficiencia Huffman:
bits/dígito binario
TD4 2022TD4 2022 47
Código de Huffman: Propiedades
▪ Los códigos construidos mediante el método de Huffman 
satisfacen: 
TD4 2022TD4 2022 48
Código de Huffman: Propiedades
▪ Los códigos construidos mediante el método de Huffman 
satisfacen: 
▪ Cumplen con la propiedad de prefijo: ningún símbolo codificado 
completo es prefijo otro en el conjunto -> Resulta fácil detectar 
el borde entre dos símbolos codificados. 
▪ Un código que cumple la propiedad del prefijo se puede 
decodificar unívocamente. Ej. 10011110111
TD4 2022TD4 2022 49
Código de Huffman Adaptativo (FGK)
▪ Codificación on the fly: no conocemos las probabilidades de 
los símbolos. 
▪ Comienza con un árbol vacío
▪ Cada nodo del árbol almacena un valor de frecuencia de 
aparición (entero): 
• Las hojas del árbol contienen los símbolos observados 
hasta el momento y su frecuencia. 
• Los nodos internos contienen la suma de las frecuencias 
de sus hijos.
TD4 2022TD4 2022 50
Código de Huffman Adaptativo (FGK)
▪ Se utiliza un nodo especial (“nodo cero” ∅) para identificar el 
punto de inserción
▪ Para que sea un árbol de Huffman debe cumplir la propiedad 
de sibling:
“Al recorrer los nodos de abajo 
hacia arriba, de izquierda a 
derecha, las frecuencias deben 
aparecer en orden creciente”
TD4 2022TD4 2022 51
Código de Huffman Adaptativo (FGK)
▪ Se utiliza un nodo especial (“nodo cero” ∅) para identificar el 
punto de inserción
▪ Para que sea un árbol de Huffman debe cumplir la propiedad 
de sibling:
“Al recorrer los nodos de abajo 
hacia arriba, de izquierda a 
derecha, las frecuencias deben 
aparecer en orden creciente” A
B∅
A
B∅
10
10
TD4 2022TD4 2022 52
Código de Huffman Adaptativo (FGK)
▪ Se utiliza un nodo especial (“nodo cero” ∅) para identificar el 
punto de inserción
▪ Para que sea un árbol de Huffman debe cumplir la propiedad 
de sibling:
“Al recorrer los nodos de abajo 
hacia arriba, de izquierda a 
derecha, las frecuencias deben 
aparecer en orden creciente” A
B
A
B
verifica la propiedad no verifica la propiedad
10
10
∅ ∅
TD4 2022TD4 2022 53
Código de Huffman Adaptativo (FGK): Algoritmo
Mientras haya símbolos: 
▪ Paso 1: Leer el próximo símbolo
▪ Paso 2: Generar el código
• Si el símbolo está en el árbol: transmitir el código asociado
• Si el símbolo no está en el árbol: transmitir el código ∅ + símbolo literal (no hay código para la 
primera ocurrencia de un símbolo).
▪ Paso 3: Actualizar el árbol
• Si el símbolo está en el árbol: incrementar la frecuencia del nodo y propagarlo hacia arriba.
• Si el símbolo no está en el árbol: dividir el nodo ∅ en dos: el nodo ∅ a la izquierda y el nuevo 
símbolo con frecuencia 1 a la derecha. 
▪ Paso 4: Verificar la propiedad de sibling
• Si no se cumple: Reestructurar el árbol. Se deben intercambiar los 2 nodos en conflicto (junto 
con sus subárboles si los tuvieran). El nodo de mayor peso y más próximo al inicio del 
recorrido se intercambia con el nodo de menor peso y más cercano a la raíz. 
• Volver a verificar la propiedad y reestructurar (hasta que se cumpla)
TD4 2022TD4 2022 54
Huffman Adaptativo (FGK): Ejemplo compresión
∅
1) Leer símbolo 2) Generar código 3) Actualizar el árbol 4) Verificar propiedad de sibling
TD4 2022TD4 2022 55
∅
1) Leer símbolo 2) Generar código 3) Actualizar el árbol 4) Verificar propiedad de sibling
In: A
Out: 
Huffman Adaptativo (FGK): Ejemplo compresión
TD4 2022TD4 2022 56
∅
1) Leer símbolo 2) Generar código 3) Actualizar el árbol 4) Verificar propiedad de sibling
In: A
Out: A
Huffman Adaptativo (FGK): Ejemplo compresión
TD4 2022TD4 2022 57
∅
1) Leer símbolo 2) Generar código 3) Actualizar el árbol 4) Verificar propiedad de sibling
In: A
Out: A 
∅
10
A
Huffman Adaptativo (FGK): Ejemplo compresión
TD4 2022TD4 2022 58
∅
1) Leer símbolo 2) Generar código 3) Actualizar el árbol 4) Verificar propiedad de sibling
In: A
Out: A 
∅
10
A
Lista sibling:∅
Huffman Adaptativo (FGK): Ejemplo compresión
TD4 2022TD4 2022 59
∅
1) Leer símbolo 2) Generar código 3) Actualizar el árbol 4) Verificar propiedad de sibling
In: A
Out: A 
∅
10
A
In: B
Out: 
Lista sibling: ∅
Huffman Adaptativo (FGK): Ejemplo compresión
TD4 2022TD4 2022 60
∅
1) Leer símbolo 2) Generar código 3) Actualizar el árbol 4) Verificar propiedad de sibling
In: A
Out: A 
∅
10
A
In: B
Out: 0B
Lista sibling: ∅
Huffman Adaptativo (FGK): Ejemplo compresión
TD4 2022TD4 2022 61
∅
1) Leer símbolo 2) Generar código 3) Actualizar el árbol 4) Verificar propiedad de sibling
In: A
Out: A 
∅
10
A
Lista sibling: ∅
In: B
Out: 0B
10
A10
B∅
Huffman Adaptativo (FGK): Ejemplo compresión
TD4 2022TD4 2022 62
∅
1) Leer símbolo 2) Generar código 3) Actualizar el árbol 4) Verificar propiedad de sibling
In: A
Out: A 
∅
10
A
Lista sibling: ∅
In: B
Out: 0B
10
A10
B∅
∅
Huffman Adaptativo (FGK): Ejemplo compresión
TD4 2022TD4 2022 63
∅
1) Leer símbolo 2) Generar código 3) Actualizar el árbol 4) Verificar propiedad de sibling
In: A
Out: A 
∅
10
A
Lista sibling: ∅
In: B
Out: 0B
10
A10
B∅
∅
In: B
Out: 
Huffman Adaptativo (FGK): Ejemplo compresión
TD4 2022TD4 2022 64
∅
1) Leer símbolo 2) Generar código 3) Actualizar el árbol 4) Verificar propiedad de sibling
In: A
Out: A 
∅
10
A
Lista sibling: ∅
In: B
Out: 0B
10
A10
B∅
∅
In: B
Out: 01
Huffman Adaptativo (FGK): Ejemplo compresión
TD4 2022TD4 2022 65
∅
1) Leer símbolo 2) Generar código 3) Actualizar el árbol 4) Verificar propiedad de sibling
In: A
Out: A 
∅
10
A
Lista sibling: ∅
In: B
Out: 0B
10
A10
B∅
∅
In: B
Out: 01
10
A10
B∅
Huffman Adaptativo (FGK): Ejemplo compresión
TD4 2022TD4 2022 66
∅
1) Leer símbolo 2) Generar código 3) Actualizar el árbol 4) Verificar propiedad de sibling
In: A
Out: A 
∅
10
A
Lista sibling: ∅
In: B
Out: 0B
10
A10
B∅
∅
In: B
Out: 01
10
A10
B∅
∅
Huffman Adaptativo (FGK): Ejemplo compresión
TD4 2022TD4 2022 67
∅
1) Leer símbolo 2) Generar código 3) Actualizar el árbol 4) Verificar propiedad de sibling
In: A
Out: A 
∅
10
A
Lista sibling: ∅
In: B
Out: 0B
10
A10
B∅
∅
In: B
Out: 01
10
A10
B∅
∅
10
B10
A∅
Huffman Adaptativo (FGK): Ejemplo compresión
TD4 2022TD4 2022 68
∅
1) Leer símbolo 2) Generar código 3) Actualizar el árbol 4) Verificar propiedad de sibling
In: A
Out: A 
∅
10
A
Lista sibling: ∅
In: B
Out: 0B
10
A10
B∅
∅
In: B
Out: 01
10
A10
B∅
∅
10
B10
A∅
Huffman Adaptativo (FGK): Ejemplo compresión
TD4 2022TD4 2022 69
∅
1) Leer símbolo 2) Generar código 3) Actualizar el árbol 4) Verificar propiedad de sibling
In: A
Out: A 
∅
10
A
Lista sibling: ∅
In: B
Out: 0B
10
A10
B∅
∅
In: B
Out: 01
10
A10
B∅
∅
10
B10
A∅
∅
Huffman Adaptativo (FGK): Ejemplo compresión
TD4 2022TD4 2022 70
Huffman Adaptativo (FGK): Ejemplo descompresión
El descompresor es simétrico: recibe el input codificado (A0B01) , construye el mismo árbol y decodifica 
con los mismos pasos que el codificador. 
∅
In: A
Out: 
TD4 2022TD4 2022
Huffman Adaptativo (FGK): Ejemplo descompresión
El descompresor es simétrico: recibe el input codificado (A0B01) , construye el mismo árbol y decodifica 
con los mismos pasos que el codificador. 
∅
In: A
Out: A 
∅
10
A
TD4 2022TD4 2022
Huffman Adaptativo (FGK): Ejemplo descompresión
El descompresor es simétrico: recibe el input codificado (A0B01) , construye el mismo árbol y decodifica 
con los mismos pasos que el codificador. 
∅
In: A
Out: A 
∅
10
A
In: 0B
Out: 
TD4 2022TD4 2022
Huffman Adaptativo (FGK): Ejemplo descompresión
El descompresor es simétrico: recibe el input codificado (A0B01) , construye el mismo árbol y decodifica 
con los mismos pasos que el codificador. 
∅
In: A
Out: A 
∅
10
A
In: 0B
Out: 0B
10
A10
B∅
TD4 2022TD4 2022
Huffman Adaptativo (FGK): Ejemplo descompresión
El descompresor es simétrico: recibe el input codificado (A0B01) , construye el mismo árbol y decodifica 
con los mismos pasos que el codificador. 
∅
In: A
Out: A 
∅
10
A
In: 0B
Out: 0B
10
A10
B∅
In: 01
Out: 
TD4 2022TD4 2022 75
Huffman Adaptativo (FGK): Ejemplo descompresión
El descompresor es simétrico: recibe el input codificado (A0B01) , construye el mismo árbol y decodifica 
con los mismos pasos que el codificador. 
∅
In: A
Out: A 
∅
10
A
In: 0B
Out: 0B
10
A10
B∅
In: 01
Out: B
10
A10
B∅
No respeta sibling
TD4 2022TD4 2022 76
Huffman Adaptativo (FGK): Ejemplo descompresión
El descompresor es simétrico: recibe el input codificado (A0B01) , construye el mismo árbol y decodifica 
con los mismos pasos que el codificador. 
∅
In: A
Out: A 
∅
10
A
In: 0B
Out: 0B
10
A10
B∅
In: 01
Out: B
10
A10
B∅
10
B10
A∅
TD4 2022TD4 2022 77
Métodos con diccionarios
▪ Se reemplazan frases (secuencias de símbolos) repetidas en el 
mensaje por un índice a una ocurrencia anterior. 
▪ Construcción dinámica de un diccionario de frases.
▪ Los índices ocupan menos espacio que las frases.
▪ A mayor longitud de las frases repetidas, mayor tasa de 
compresión.
▪ Son asimétricos: el compresor es más costoso (por la 
búsqueda de coincidencias) que el descompresor (solo debe 
recuperar las frases indicadas por los elementos del 
diccionario)
TD4 2022TD4 2022 78
Run Length Encoding (RLE)
▪ Reemplaza secuencias de símbolos consecutivos iguales 
por un par símbolo/repeticiones (S,R):
TD4 2022TD4 2022 79
Run Length Encoding (RLE)
▪ Reemplaza secuencias de símbolos consecutivos iguales 
por un par símbolo/repeticiones (S,R):
Original: AAAAAAAABBBCCCCC (16 bytes)
Comprimido: A8B3C5 (6 bytes)
TD4 2022TD4 2022 80
Run Length Encoding (RLE)
▪ Reemplaza secuencias de símbolos consecutivos iguales 
por un par símbolo/repeticiones (S,R):
Original: AAAAAAAABBBCCCCC (16 bytes)
Comprimido: A8B3C5 (6 bytes)
Original: FUI PAL MALL Y ME GASTE CINCO MIL (26 bytes)
Comprimido: F1U1I1P1A1L1M1A1L2Y1M1E1G1A1S1T1E1C1I1N1C1O1M1I1L1 (50 bytes!!!)
TD4 2022TD4 2022 81
Run Length Encoding (RLE)
▪ Método aplicable siempre y cuando sepamos que los datos 
tienen repeticiones consecutivas de símbolos (imágenes)
TD4 2022TD4 2022 82
Run Lenght Encoding (RLE)
▪ Método aplicable siempre y cuando sepamos que los datos 
tienen repeticiones consecutivas de símbolos (imágenes)
▪ Forma parte de estándares de compresión (JPEG, MPEG, etc.)
TD4 2022TD4 2022 83
RLE para imágenes binarias
▪ Secuencias alternadas de pixeles 
blancos y negros
▪ No se modifican los símbolos 
(redundante), solo la longitud. 
▪ Convención: La longitud inicial 
siempre es para el símbolo 0 
(secuencia de pixeles negros). Si la 
imagen presenta un 1, se comienza 
con R=0.