Download - Programación 3: compresión de archivos
Programación 3
Compresión de archivos
Angel Vázquez-Patiñ[email protected]
Departamento de Ciencias de la ComputaciónUniversidad de Cuenca
5 de diciembre de 2016
05/12/16 Angel Vázquez-Patiño 2/33
Objetivos
1. Conocer los conceptos más importantes sobre compresión de archivos
2. Conocer la idea que soporta la mayoría de métodos de compresión
3. Conocer los métodos más importantes de compresión que hay
4. Conocer cómo comparar diferentes métodos de compresión con una medida de calidad
05/12/16 Angel Vázquez-Patiño 3/33
Contenido
Introducción
Conceptos de compresión de datos
Técnicas de compresión
Medidas de calidad
05/12/16 Angel Vázquez-Patiño 4/33
Introducción
05/12/16 Angel Vázquez-Patiño 5/33
Introducción● Una de las preguntas que más respuestas
falsas tiene en la redes. Casi siempre conlleva términos complicados que presupone ciertos conocimientos técnicos
● La idea fundamental es guardar la mayor cantidad de datos posibles en la menor cantidad de espacio posible
● Representar información de una forma compacta
05/12/16 Angel Vázquez-Patiño 6/33
Introducción● Los algoritmos de compresión a lo largo de la
historia fueron progresando comprimiendo cada vez más
● Hoy en día coexisten algoritmos muy simples, otros muy complejos, algunos muy extraños y otros muy ingeniosos
● Sin compresión no tendría sentido poner imágenes, audio o vídeo en Internet, la calidad de las comunicaciones celulares no sería la misma y desde luego la TV digital no sería posible
05/12/16 Angel Vázquez-Patiño 7/33
Compresión de datos
05/12/16 Angel Vázquez-Patiño 8/33
Compresión de datos
Idea● Reducir tamaño de archivo para ocupar menos
espacio y que pueda recuperarse el archivo original
● Para la compresión de datos la fuente es el archivo a comprimir y los mensajes son los caracteres que componen el archivo
● Dado un archivo, representar a los caracteres más probables con menos bits que los caracteres menos probables
05/12/16 Angel Vázquez-Patiño 9/33
Compresión de datosCompactación vs compresión● La compactación se refiere a técnicas destructivas, i.e.,
una vez compactado un archivo se pierde información y no puede recuperarse el original, la compactación se puede aplicar a imágenes o sonido para las cuales la pérdida de fidelidad puede llegar a justificarse por el nivel de compresión
● La compresión de datos es la reducción del volumen de datos tratables para representar una determinada información empleando una menor cantidad de espacio
● La compresión es un caso particular de la codificación, cuya característica principal es que el código resultante tiene menor tamaño que el original
05/12/16 Angel Vázquez-Patiño 10/33
Compresión de datos● Buscar repeticiones en series de datos para
después almacenar sólo el dato junto al número de veces que se repite
● E.g., si en un archivo aparece una secuencia como "AAAAAA", ocupando 6 bytes se podría almacenar simplemente 6A que ocupa sólo 2 bytes
05/12/16 Angel Vázquez-Patiño 11/33
Compresión de datos
Tipos de fuentes de datos● Texto, fotografía, audio, vídeo, otras señales (e.g.,
datos de sensores)
Importancia
Muchas fuentes de datos, una vez digitalizadas, requieren:● Gran cantidad de bits en comparación con la
capacidad de almacenamiento disponible● Gran velocidad de transmisión en comparación con la
máxima velocidad admisible por el Sistema de Comunicación Digital a través del que deben enviarse
05/12/16 Angel Vázquez-Patiño 12/33
Compresión de datos
Tasa de bits● Bits por unidad de tiempo producidos por una fuente
de datos (bits/s, bps). Por extensión, bits requeridos para almacenar un archivo (e.g., bits/imagen)
Partes de una técnica (algoritmo) de compresión
1) Algoritmo de compresión que toma una entrada X y genera una representación Xc que necesita menos bits
2) Algoritmo de reconstrucción que trabaja en la representación comprimida Xc y genera la reconstrucción Y
05/12/16 Angel Vázquez-Patiño 13/33
Compresión de datos
Compresión
Reconstrucción
X
YX
c
05/12/16 Angel Vázquez-Patiño 14/33
Compresión de datos
Clases de algoritmos● Sin pérdida (compresión)
– Entrada al codificador, X, y la salida del decodificador, Y, coinciden
● Con pérdida (compactación)– Suelen proporcionar mayor compresión pero en los
que X e Y no coinciden, aunque se parecen
¿Cuándo usar la una o la otra?
05/12/16 Angel Vázquez-Patiño 15/33
Compresión de datos
Algoritmos sin pérdida vs con pérdida● Compresión sin pérdida: una mayor
compresión sólo implica más tiempo de proceso. Se utiliza principalmente en la compresión de texto
● La base matemática de las técnicas de compresión es la Teoría de la Información
● Vea https://youtu.be/vVokVFHz8uA
05/12/16 Angel Vázquez-Patiño 16/33
Compresión de datosAlgoritmos sin pérdida vs con pérdida● Compresión con pérdida: se suele reducir la calidad. Hay que tener
en cuenta que una vez realizada la compresión, no se puede obtener la señal original, aunque sí una aproximación cuya semejanza con la original dependerá del tipo de compresión
● Suele restringirse a información analógica que ha sido digitalizada (imágenes, audio, vídeo, etc.), donde la información puede ser "parecida" y, al mismo tiempo, ser subjetivamente la misma
● Su mayor ventaja reside en las altas razones de compresión que ofrece en contraposición a un algoritmo de compresión sin pérdida
● A menudo, el observador humano no aprecia las diferencias● También llamadas técnicas de reducción de entropía o de reducción
de información
05/12/16 Angel Vázquez-Patiño 17/33
Compresión de datos
Algoritmos comunes de compresión con pérdida● Códecs de transformación: los datos
originales son transformados de tal forma que se simplifican. Creando un nuevo conjunto de datos proclives a altas razones de compresión sin pérdida
● Códecs predictivos: los datos originales son analizados para predecir el comportamiento de los mismos. Después se compara esta predicción con la realidad, codificando el error y la información necesaria para la reconstrucción
05/12/16 Angel Vázquez-Patiño 18/33
Compresión de datos
Algoritmos comunes de compresión con pérdida● Otros ejemplos
– Cuantificación escalar y de vectores
– Wavelets
– Transformaciones por bloques
– Estándares: JPEG, JPEG 2000, MPEG (1, 2, 4)
05/12/16 Angel Vázquez-Patiño 19/33
Compresión de datos
Algoritmos de compresión sin pérdida● Duplicado exacto del flujo de datos de entrada
después de un ciclo de compresión / reconstrucción. Es generalmente implementada usando uno o dos diferentes tipos de modelos: estático o basado en diccionario
● El modelo estático lee y codifica mientras utiliza la probabilidad de aparición de un carácter. Su forma más simple usa una tabla estática de probabilidades
05/12/16 Angel Vázquez-Patiño 20/33
Compresión de datos
Algoritmos de compresión sin pérdida● El modelo basado en diccionario usa un código
simple para reemplazar cadenas de símbolos, los modelos estáticos generalmente codifican un símbolo a la vez. El esquema de compresión basada en diccionario utiliza un concepto diferente. Lee una entrada de datos y observa por grupos de símbolos que aparecen en el diccionario. Si una cadena concuerda, un indicador o índice en el diccionario puede salir en lugar del código del símbolo
● También se llaman técnicas de reducción de redundancia. E.g., SO.
05/12/16 Angel Vázquez-Patiño 21/33
Compresión de datos
Algoritmos de compresión sin pérdida● Campos de aplicación
– Compresión de datos bancarios
– Compresión de datos empresariales/financieros
– Compresión de binarios/ejecutables
– Compresión de imágenes médicas
05/12/16 Angel Vázquez-Patiño 22/33
Un vistazo generalTécnicas estadísticas● Código de Huffman● Códigos aritméticos● Código de Golomb
Técnicas basadas en diccionarios● LZW, LZ77
Técnicas predictivas● PPM, método de Burrows-Wheeler
Estándares● Morse, Braille, Unix compress, gzip, zip, bzip, gif, bmp,jbig,
jpeg sin pérdida, etc.
05/12/16 Angel Vázquez-Patiño 23/33
Medidas de calidad
05/12/16 Angel Vázquez-Patiño 24/33
Medidas de calidad
1) Complejidad del algoritmo
2) Necesidades de memoria
3) Tiempo de ejecución en una determinada plataforma
4) Razón compresión
5) Cuánto se parece la reconstrucción a los datos originales
05/12/16 Angel Vázquez-Patiño 25/33
Medidas de calidad
Razón de compresión● Cociente entre el número de bits necesarios
para representar los datos antes de la compresión y el número de bits necesarios para representar los datos después de la compresión
Ejemplo● Imagen 256×256, un byte por píxel, tras
compresión 16384 bytes:
05/12/16 Angel Vázquez-Patiño 26/33
Medidas de calidad
Razón de compresión● También se puede representar la razón de
compresión como porcentaje del tamaño original de los datos
Ejemplo● Imagen 256×256, un byte por píxel, tras
compresión 16384 bytes: reducción del 75%.
05/12/16 Angel Vázquez-Patiño 27/33
Medidas de calidad
Compresión con pérdida● Se utiliza, a más de la razón de compresión
obtenida, una medida para determinar la diferencia entre los datos originales y los reconstruidos, la distorsión
05/12/16 Angel Vázquez-Patiño 28/33
Tarea● Vea https://youtu.be/vVokVFHz8uA● Implementación de la codificación Huffman● Se dará un texto plano (.txt) y se debe mostrar
la taza de compresión del algoritmo● En otro archivo de texto plano se debe mostrar
el flujo de bits (0/1) de todo el texto● Plus: mejorar su algoritmo para aumentar la
compresión del archivo
05/12/16 Angel Vázquez-Patiño 29/33
Conceptos y términos importantes
05/12/16 Angel Vázquez-Patiño 30/33
Conceptos y términos importantes● Razón de compresión● Algoritmos de compresión con pérdida y sin
pérdida● Codificación Huffman● Cuándo utilizar un algoritmo de compresión con
o sin pérdida
05/12/16 Angel Vázquez-Patiño 31/33
Vídeos
¿Qué es la teoría de la información?● https://youtu.be/vVokVFHz8uA
Codificación Huffman● https://youtu.be/W6WZT12ruGQ● http://www.slideshare.net/mejiaff/cdigo-huffman● https://youtu.be/8Gf8wutvS1w
05/12/16 Angel Vázquez-Patiño 32/33
Referencia● Sayood, K., 2012. Introduction to data
compression, 4th ed. ed. Morgan Kaufmann, Waltham, MA.
05/12/16 Angel Vázquez-Patiño 33/33
Preguntas