View
15
Download
2
Category
Preview:
DESCRIPTION
Compresion de Archivos
Citation preview
Tpicos I
Unidad II
Compresin de archivos
Semana 8
Seguridad y Criptografa
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
Implementar algoritmos para la
compresin de archivos.
Objetivo Instruccional
Conte
nid
os
Introduccin
Codificacin por longitud de series
Codificacin de longitud variable
Algoritmo de Huffman
Intr
od
uc
ci
n
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).
Compresin de datos
En general, la mayor parte de los
archivos tienen un gran nivel de
redundancia.
Intr
od
uc
ci
n
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.
En que consiste?
Intr
od
uc
ci
n
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.
Modelo y Codificacin
Intr
od
uc
ci
n
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
Compresin de datos basada en
modelos
Intr
od
uc
ci
n
Compresin de datos basada en
modelos
Intr
od
uc
ci
n
- "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.
Dentro de las tcnicas de compresin de datos, y
atendiendo a la reversibilidad de la informacin
original, hay dos grandes familias:
Tcnicas de compresin
Intr
od
uc
ci
n
- Algoritmos estadsticos. Utilizan las propiedades 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
Tipos de compresin lowless
Co
dific
ac
in
po
r lo
ng
itu
d d
e s
erie
s 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
Co
dific
ac
in
po
r lo
ng
itu
d d
e s
erie
s 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
Co
dific
ac
in
po
r lo
ng
itu
d d
e s
erie
s 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 representara a cualquier aparicin de Q en la entrada.
AAAAQBBBAABBBBBQQQQQCCCCCCCCDABCBAAABBBBCCCD
QDAQ BBBAAQEBQEQQHCDABCBAAAQDBCCCD
Otro ejemplo: Una secuencia de 51 A, debera codificarse
como:
QZAQYA
Co
dific
ac
in
po
r lo
ng
itu
d d
e s
erie
s
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.
Matriz de puntos tpica, con informacin de la codificacin por longitud de series (q apaisada)
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
Co
dific
ac
in
de
lon
gitu
d v
aria
ble
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.
Co
dific
ac
in
de
lon
gitu
d v
aria
ble
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).
Co
dific
ac
in
de
lon
gitu
d v
aria
ble
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.
R
B
C D
A
0
1
1
1
0
1 0
0
Pero que trie es el mejor para utilizar?
Alg
oritm
o d
e H
uff
ma
n
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.
Introduccin
Alg
oritm
o d
e H
uff
ma
n 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.
Descripcin
Alg
oritm
o d
e H
uff
ma
n
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
Obtencin del cdigo
asociado a un smbolo
Alg
oritm
o d
e H
uff
ma
n
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.
Obtencin de un smbolo a
partir del cdigo
Alg
oritm
o d
e H
uff
ma
n 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.
Ejemplo de uso
rbol para construir el cdigo
Huffman del ejemplo
Smbolo Frecuencia
A 0,15
B 0,30
C 0,20
D 0,05
E 0,15
F 0,05
G 0,10
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.
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.
Alg
oritm
o d
e H
uff
ma
n
Ejemplo de construccin Smbolo Frecuencia
A 0,15
B 0,30
C 0,20
D 0,05
E 0,15
F 0,05
G 0,10
0..30 B
0.15 A
0..15 E
0..20 C
0..10 G
0..05 D
0..05 F
0..30
0..60
0..10
0..20
0..40
1.00
0
0
0
0
0
0
1
1
1
1
1
1
Alg
oritm
o d
e H
uff
ma
n 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.
Limitaciones
Alg
oritm
o d
e H
uff
ma
n 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.
Ejemplo
Alg
oritm
o d
e H
uff
ma
n
Ejemplo (continuacin)
Smbolo Frecuencia
A 0,9844
B 0,0156
Smbolo Frecuencia
AA 0,9688
AB 0,0312
1.0
B A B
0 1
1.0
AB AA
0 1
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.
Alg
oritm
o d
e H
uff
ma
n 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.
Y para la decodificacin?
Alg
oritm
o d
e H
uff
ma
n 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?
Ejercicio
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
Compresin de archivos
Semana 8
Seguridad y Criptografa
Recommended