Tpicos I

Unidad II

Seguridad y Criptografa

Semana 8

Compresin de archivos

Objetivos Generales
Entender el manejo, uso de algoritmos y
estructuras de datos avanzados, haciendo
nfasis en los algoritmos de internet,
seguridad y redes.

Objetivo Especfico
Implementar algoritmos para seguridad
y compresin de archivos

Objetivo Instruccional
Implementar algoritmos para la
compresin de archivos.

Contenidos

Introduccin
Codificacin por longitud de series

Codificacin de longitud variable

Algoritmo de Huffman

Introduccin

Compresin de datos
En general, la mayor parte de los
archivos tienen un gran nivel de
redundancia.
Las tcnicas de compresin de
archivos sirven a menudo para
archivos de texto (en los que ciertos
caracteres aparecen con mucha mas frecuencia
que otras),

para archivos de exploracin

de imgenes codificadas (que presentan
grandes zonas homogneas) y para archivos
de representacin digital de sonido y
de otras seales analgicas (que
presentan un gran numero de patrones repetidos).

Introduccin

En que consiste?
Bsicamente la compresin consiste en tomar una
trama
de
smbolos
y
transformarlos
en
cdigos/claves. Si la compresin es eficiente, las
claves resultantes ocuparn menor espacio que los
smbolos originales. La decisin de obtener una
codificacin a partir de ciertos smbolos (o conjunto de
ellos) est basada en un modelo.
El modelo es simplemente una coleccin de datos y
reglas usados para procesar la entrada de smbolos
y determinar su correspondiente codificacin a la
salida.
Por ejemplo un programa usa el modelo para definir
aproximadamente las probabilidades para cada smbolo
y el codificador para producir una codificacin
apropiada basada en esas probabilidades.

Modelo y Codificacin

Introduccin

Los conceptos de modelo y codificacin son cosas

diferentes.

Usualmente se cae en el error de emplear el trmino

de "codificacin" para referirse a todo el proceso de
compresin de datos en vez de considerarlo como
un simple componente de ese proceso.

Introduccin

Compresin de datos basada en

modelos
Cualquier compresor de datos puede describirse en trminos
de un modelo de la fuente de datos a comprimir ms un
codificador.
En el caso de la compresin de texto, frecuentemente se
utiliza un modelo probabilstico (que en estas implementaciones es de
orden 0 o sin memoria) y un codificador de Huffman.
El objetivo del modelo probabilstico es averiguar las
probabilidades de ocurrencia de los smbolos codificados.
Concretamente, un modelo de orden 0 calcula la
probabilidad de un smbolo contando el nmero de veces
que ese smbolo aparece en la secuencia de smbolos.
Por otro lado, la finalidad del codificador de longitud variable
es utilizar las probabilidades calculadas por el modelo para
asignar un cdigo de compresin corto a los smbolos ms
frecuentes a costa de asignar un cdigo de compresin largo
a los smbolos ms raros

Introduccin

Compresin de datos basada en

modelos

Tcnicas de compresin

Introduccin

Dentro de las tcnicas de compresin de datos, y

atendiendo a la reversibilidad de la informacin
original, hay dos grandes familias:

- "lowless" sin perdida.

Para datos en los

que es imprescindible que no se pierda nada de
informacin, como por ejemplo registros de
bases de datos, ficheros ejecutables, hojas de
clculo...etc.

- "lossy" con perdida.

Para datos en los

que se permite cierta prdida de informacin
"sin que se note demasiado", como por ejemplo
en ficheros en MP3, imgenes en JPEG,
PNG...etc. Aqu una pequea disminucin en la
calidad final no se nota demasiado, pero influye
muy positivamente en la reduccin del peso del
fichero.

Tipos de compresin lowless

- Algoritmos estadsticos. Utilizan las propiedades

Introduccin

estadsticas de la fuente para mejorar la codificacin

(a cada
mensaje de la fuente asigna una cadena de smbolos del alfabeto de
salida). Se trata de aprovechar la redundancia de informacin

de la fuente para conseguir esa compresin.

Algoritmo huffman
Algoritmo Shannon-Fano
Algoritmos Aritmticos

- Algoritmos basados en diccionarios. Son las tcnicas

ms utilizadas, generalmente se las implementa en
conjuncin con compresores estadsticos
Algoritmo Run-Length
Algoritmo LZW
Algoritmo LZ77

Codificacin por longitud de series

El tipo mas simple de redundancia que se puede

encontrar en un archivo son las largas series de
caracteres repetidos.
Por ejemplo, en la cadena siguiente:

AAAABBBAABBBBBCCCCCCCCDABCBAAABBBBCCCD

Esta cadena se puede codificar de forma mas compacta

reemplazando cada repeticin por un solo ejemplar del
carcter repetido seguido del numero de veces que se repite.
Seria mejor decir que esta cadena consiste de 4 letras A,
seguida de 3 B, seguidas de 2 A, seguidas de 5 B, etc. Esta forma
de comprimir una cadena se denomina codificacin por
longitud de series.
4A3BAA5B8CDABCB3A4B3CD
Ningn mtodo de longitud de series es eficaz a menos que la mayor
parte de las series sean largas

Codificacin por longitud de series

Algunos inconvenientes:
El mtodo de compresin de caracteres no funciona con
cadenas que contienen dgitos.
Si se utilizan otros caracteres para codificar las longitudes de
las series, no podra aplicarse el mtodo a cadenas que
contengan esos caracteres.

Cmo se puede lograr que algunas letras representen dgitos y

otras formen parte de la cadena que se va a codificar?
Una solucin consiste en
utilizar un carcter con pocas
probabilidades de aparecer en el texto, al que se denomina
carcter de escape. Cada aparicin de dicho carcter indica
que las dos letras siguientes forman un par (longitud , carcter),
en el que la i-sima letra del alfabeto representa una longitud
igual a i.
QDABBBAAQEBQHCDABCBAAAQDBCCCD
Tomando Q como carcter de escape

Codificacin por longitud de series

Nueva interrogante:
Pero que pasa si el carcter de escape aparece tambin en la
serie de entrada?
Una solucin a este problema consiste en utilizar para
representar al carcter de escape una secuencia de escape
con una longitud de serie cero. De esta manera el espacio en
blanco podra representar al cero, y la secuencia de escape
Q<espacio> representara a cualquier aparicin de Q en la
entrada.

AAAAQBBBAABBBBBQQQQQCCCCCCCCDABCBAAABBBBCCCD
QDAQ BBBAAQEBQEQQHCDABCBAAAQDBCCCD
Otro ejemplo: Una secuencia de 51 A, debera codificarse
como:
QZAQYA

Codificacin por longitud de series

Matriz de puntos tpica, con informacin de la codificacin por longitud de series (q apaisada)

Si se utilizan 6 bits para representar cada longitud, el archivo

completo se representa con 384 bits (6 bits x 63 informaciones + 6 bits
para representar la cantidad de bits por lnea (51)) con respecto a los 975
(51x19 + 6) bits que se necesitan para almacenarlo de forma
explicita.

Codificacin de longitud variable

La idea es abandonar la forma como se almacenan

habitualmente los archivos de texto; en lugar de emplear siete u
ocho bits por carcter, se utilizaran solamente unos pocos bits
para los caracteres mas frecuentes y algunos mas para los que
aparecen raramente.

Ejemplo:
Palabra a codificar : ABRACADABRA
Empleando el cdigo binario compacto estndar, en el que la
representacin con cinco bits de i reproduce a la i-sima letra
del alfabeto (0 para los espacios en blanco), proporcionan la
siguiente serie de bits.
0000100010100100000100011000010010000001000101001000001

Codificacin de longitud variable

Con el cdigo estndar visto anteriormente, la D que aparece

una sola vez, necesita el mismo numero de bits que la A, que
aparece cinco veces.
Con un cdigo de longitud variable se puede alcanzar ahorros
de espacio codificando los caracteres mas frecuentemente
utilizados con el menor numero de bits posible, de forma que se
minimice el numero total de bits.
Codificando A por 0, B por 1, R por 01, C por 10 y D por 11 se
tendra la siguiente codificacin:

0 1 01 0 10 0 11 0 1 01 0
Esta cadena utiliza solo 15 bits en lugar de los 55 anteriores, pero
depende de los espacios en blanco como delimitador, aun con
estos (10 delimitadores) que sumarian 25 bits, aun sigue siendo
mucho mas compacto.

Codificacin de longitud variable

Los delimitadores no son necesarios si el cdigo de un carcter

no es el prefijo de otro. Por ejemplo si se codifica A por 0, B por
110, C por 1111, D por 1110 y R por 10, no hay mas que una sola
forma de codificar la cadena que emplea 23 bits.

01101001111011100110100
Una forma fcil de representar el cdigo es a travs de un trie
(ordenacin por residuos).
0

0
R

1
0
B

0
D

1
C

El cdigo de cada carcter se

determina por el camino desde la raz
al carcter con 0 para ir a la
izquierda y 1 para ir a la derecha,
como es habitual en un trie. Cada vez
que se encuentra un nodo externo, se
da salida al carcter del nodo y se
comienza de nuevo en la raz.

Pero que trie es el mejor para utilizar?

Algoritmo de Huffman

Introduccin
El algoritmo de Huffman es un algoritmo para la
construccin de cdigos de Huffman, desarrollado
por David A. Huffman en 1952 y descrito en A
Method for the Construction of Minimum-Redundancy
Codes.
Este algoritmo toma un alfabeto de n smbolos, junto
con sus frecuencias (cantidad porcentajes) de aparicin
asociadas, y produce un cdigo de Huffman para
ese alfabeto y esas frecuencias.

Algoritmo de Huffman

Descripcin
El algoritmo consiste en la creacin de un rbol binario (trie) que tiene
cada uno de los smbolos por hoja, y construido de tal forma que
siguindolo desde la raz a cada una de sus hojas se obtiene el cdigo
Huffman asociado.

1. Se crean varios rboles, uno por cada uno de los smbolos del alfabeto,
consistiendo cada uno de los rboles en un nodo sin hijos, y etiquetado
cada uno con su smbolo asociado y su frecuencia de aparicin.
2. Se toman los dos rboles de menor frecuencia, y se unen creando un
nuevo rbol. La etiqueta de la raz ser la suma de las frecuencias de las
races de los dos rboles que se unen, y cada uno de estos rboles ser
un hijo del nuevo rbol. Tambin se etiquetan las dos ramas del nuevo
rbol: con un 0 la de la izquierda, y con un 1 la de la derecha.
3. Se repite el paso 2 hasta que slo quede un rbol.
Con este rbol se puede conocer el cdigo asociado a un smbolo, as
como obtener el smbolo asociado a un determinado cdigo.

Algoritmo de Huffman

Obtencin del cdigo

asociado a un smbolo
PROCEDIMIENTO:

1. Comenzar con un cdigo vaco

2. Iniciar el recorrido del rbol en la hoja asociada al
smbolo
3. Comenzar un recorrido del rbol hacia arriba
4. Cada vez que se suba un nivel, aadir al cdigo la
etiqueta de la rama que se ha recorrido
5. Tras llegar a la raz, invertir el cdigo
6. El resultado es el cdigo Huffman deseado

Algoritmo de Huffman

Obtencin de un smbolo a
partir del cdigo
PROCEDIMIENTO:

1. Comenzar el recorrido del rbol en la raz de ste

2. Extraer el primer smbolo del cdigo a descodificar
3. Descender por la rama etiquetada con ese
smbolo
4. Volver al paso 2 hasta que se llegue a una hoja,
que ser el smbolo asociado al cdigo
En la prctica, casi siempre se utiliza el rbol para obtener todos los
cdigos de una sola vez; luego se guardan en tablas y se descarta el
rbol.

Algoritmo de Huffman

Ejemplo de uso
La tabla describe el alfabeto a codificar, junto con las
frecuencias de sus smbolos. En el grfico se muestra el rbol
construido a partir de este alfabeto siguiendo el algoritmo
descrito.
Smbolo
A
B
C
D
E
F
G

rbol para construir el cdigo

Huffman del ejemplo

Frecuencia
0,15
0,30
0,20
0,05
0,15
0,05
0,10

Se puede ver con facilidad

cul es el cdigo del smbolo
E: subiendo por el rbol se
recorren ramas etiquetadas
con 1, 1 y 0; por lo tanto, el
cdigo es 011.
Para obtener el cdigo de D
se recorren las ramas 0, 1, 1 y
1, por lo que el cdigo es 1110.

La operacin inversa tambin es fcil de

realizar: dado el cdigo 10 se recorren desde
la raz las ramas 1 y 0, obtenindose el
smbolo C.
Para descodificar 010 se recorren las ramas
0, 1 y 0, obtenindose el smbolo A.

Algoritmo de Huffman

Ejemplo de construccin
Smbolo
A
B
C
D
E
F
G

1.00

1
0

0..40

1
0..60

0..20

0..30

0
0..30
B

0.15
A

0..10

0
1
0..15
E

0
0..20
C

0..10
G

0..05
D

1
0..05
F

Frecuencia
0,15
0,30
0,20
0,05
0,15
0,05
0,10

Algoritmo de Huffman

Limitaciones
Para poder utilizar el algoritmo de Huffman es
necesario conocer de antemano las frecuencias de
aparicin de cada smbolo, y su eficiencia depende
de lo prximas a las frecuencias reales que sean las
estimadas. Algunas implementaciones del algoritmo
de Huffman son adaptativas, actualizando las
frecuencias de cada smbolo conforme recorre el
texto.
La eficiencia de la codificacin de Huffman
tambin depende del balance que exista entre los
hijos de cada nodo del rbol, siendo ms eficiente
conforme menor sea la diferencia de frecuencias
entre los dos hijos de cada nodo.

Ejemplo
Algoritmo de Huffman

Se tiene la cadena de longitud 64:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAB
El algoritmo de Huffman aplicado nicamente a los smbolos devuelve el
cdigo:
1111111111111111111111111111111111111111111111111111111111111110
Tambin de longitud 64.
Sin embargo, si antes de utilizar el algoritmo, se agrupan los smbolos en las
palabras "AA", "AB" (que se codifican como 1, 0), el algoritmo devuelve la
siguiente cadena:
11111111111111111111111111111110
que tiene longitud 32, la mitad que si no se hubiera agrupado.

Algoritmo de Huffman

Ejemplo (continuacin)
Si observa el rbol de Huffman, se puede comprobar
que la diferencia de frecuencias entre las ramas del
rbol es menor cuando esta se agrupa.
1.0
1.0

BB

Smbolo
A
B

Frecuencia
0,9844
0,0156

AB

AA

Smbolo
AA
AB

Frecuencia
0,9688
0,0312

Algoritmo de Huffman

Y para la decodificacin?
El rbol se debe almacenar o bien enviarlo junto con
el mensaje para decodificarlo. As el ahorro de
espacio antes mencionado no es totalmente exacto,
porque el mensaje no se puede decodificar sin el trie
y se debe en tener en cuenta el coste que significa
almacenar el rbol (array cdigo) junto con el mensaje.
Por lo tanto, la codificacin Huffman solo es efectiva
para archivos largos donde el ahorro de espacio en
el mensaje es suficiente como para compensar el
coste.

Algoritmo de Huffman

Ejercicio
Mostrar el proceso de construccin del rbol de
codificacin de Huffman cuando se aplica el
mtodo descrito a la cadena ABRACADABRA.
cuantos bits necesita el mensaje cifrado?

TRABAJO DE INVESTIGACION

Run-Length
LZ77
LZW
Aritmticos
RLE
Shannon-Fano
Deflate
GZIP
Basados en TDC
Basados en WAVELETS

TRABAJO PRACTICO
Implementar
los
procedimientos
de
compresin y descompresin descritos para
el mtodo de codificacin por longitud de
series, considerando un alfabeto fijo y
utilizando la letra Q como carcter de
escape.
Implementar
los
procedimientos
de
compresin y descompresin descritos para
el mtodo de codificacin de archivos
binarios.

Tpicos I
Unidad II

Seguridad y Criptografa

Semana 8

Compresin de archivos