jueves, 7 de abril de 2011

7.- Compresión de datos

1.- Fundamentos 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. Al acto de compresión de datos se denomina compresión, y al contrario descompresión.

El espacio que ocupa una información codificada (datos, señal digital, etc.) sin compresión es el cociente entre la frecuencia de muestreo y la resolución. Por tanto, cuantos más bits se empleen mayor será el tamaño del archivo. No obstante, la resolución viene impuesta por el sistema digital con que se trabaja y no se puede alterar el número de bits a voluntad; por ello, se utiliza la compresión, para transmitir la misma cantidad de información que ocuparía una gran resolución en un número inferior de bits.

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.

La compresión de datos se basa fundamentalmente en buscar repeticiones en series de datos para después almacenar solo el dato junto al número de veces que se repite. Así, por ejemplo, si en un fichero aparece una secuencia como "AAAAAA", ocupando 6 bytes se podría almacenar simplemente "6A" que ocupa solo 2 bytes, en algoritmo RLE.


2.- Algoritmos de compresión
2.1Compresión con pérdida de información 

Se denomina algoritmo de compresión con pérdida a cualquier procedimiento de codificación que tenga como objetivo representar cierta cantidad de información utilizando una menor cantidad de la misma, siendo imposible una reconstrucción exacta de los datos originales.
La compresión con pérdida sólo es útil cuando la reconstrucción exacta no es indispensable para que la información tenga sentido. La información reconstruida es solo una aproximación de la información original. Suele restringirse a información analógica que ha sido digitalizada (imágenes, audio, video, 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.
Existen dos técnicas comunes de compresión con pérdida:
  • Por códecs de transformación: los datos originales son transformados de tal forma que se simplifican (sin posibilidad de regreso a los datos originales). Creando un nuevo conjunto de datos proclives a altas razones de compresión sin pérdida.
  • Por 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. Nuevamente, el error es proclive a altas razones de compresión sin pérdida.
En algunos casos se utilizan ambas, aplicando la transformación al resultado de la codificación predictiva.


2.2 Compresión sin pérdida de información

Se denomina algoritmo de compresión sin pérdida a cualquier procedimiento de codificación que tenga como objetivo representar cierta cantidad de información utilizando una menor cantidad de la misma, siendo posible una reconstrucción exacta de los datos originales.

La compresión sin perdidas es una técnica que consiste en la garantía de generar un duplicado exacto del flujo de datos de entrada después de un ciclo de compresión / expansió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 caracter. Su forma más simple usa una tabla estática de probabilidades, en el inicio generar un árbol de Huffman tenía costos significantes por tanto no siempre era generado, en su lugar se analizaban bloques representativos de datos, dando una tabla de frecuencia característica. Entonces los árboles de Huffman se generaban y los programas tenían acceso a este modelo estático. Pero utilizar un modelo estático tiene sus limitaciones. Si un flujo de entrada no concuerda bien con la previamente estadística acumulada, la relación de compresión se degradaría, posiblemente hasta el punto de que el flujo de datos saliente fuese tan largo como el entrante. Por tanto la siguiente mejora obvia fue construir una tabla estática a cada flujo de entrada único.

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 simbolos 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
Algunos algoritmos de compresión sin perdidas son los algoritmos Lempel-Ziv que incluyen: LZ77 LZ78 LZ-W.

Este sistema de compresión se usa en compresores de archivo (RAR, Gzip, Bzip, zip, 7z, ARJ, LHA) y de disco, también en imágenes (PNG, RLE) y en algún formato de audio (FLAC, Monkey's Audio), en video es menos común, pueden ser usados para su captura y edición, pero no comercializada para reproducción domestica.

2.3 RLE

La compresión RLE o Run-length encoding es una forma muy simple de compresión de datos en la que secuencias de datos con el mismo valor consecutivas son almacenadas como un único valor más su recuento. Esto es más útil en datos que contienen muchas de estas "secuencias"; por ejemplo, gráficos sencillos con áreas de color plano, como iconos y logotipos.
Por ejemplo, considera una pantalla que contiene texto en negro sobre un fondo blanco. Habría muchas secuencias de este tipo con píxeles blancos en los márgenes vacíos, y otras secuencias de píxeles negros en la zona del texto. Supongamos una única línea (o scanline), con N representando las zonas en negro y B las de blanco:
BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBBBBBBBNBBBBBBBBBBBBBB

Si aplicamos la codificación run-length a está línea, obtendríamos lo siguiente:
12B1N12B3N24B1N14B

Interpretado esto como 12 bes, 1 ene, 12 bes, 3 enes, etc. El código run-length representa el original de 67 caracteres en tan sólo 16. Esta codificación traducida a binario, cuyo principio es el mismo, se utiliza para el almacenamiento de imágenes. Incluso ficheros de datos binarios pueden ser comprimidos utilizando este método. El primer byte contiene un número que representa el número de veces que el carácter está repetido. El segundo byte contiene al propio carácter. En otros casos se codifican en un solo byte: 1 bit (0 o 1) y 7 bits para especificar el número de caracteres consecutivos.

Sin embargo, sistemas de compresión más modernos a menudo usan el algoritmo de deflación u otros algoritmos basados en el LZ77, el cual tiene la ventaja de utilizar secuencias de cadenas de caracteres.
Algunos formatos que utilizan esta codificación incluyen Packbits, PCX e ILBM.
La codificación run-length realiza una compresión de datos sin pérdidas y es muy utilizado en imágenes de 8 bits indexadas (en un principio fue utilizado para imágenes en blanco y negro). No funciona tan bien en imágenes donde varía constantemente el color de los pixels como fotografías, aunque JPEG lo utiliza de forma efectiva en los coeficientes que quedan después de transformar y cuantificar bloques de imágenes. 


2.4 WBS

Es una estructura exhaustiva, jerárquica y descendente formada por los entregables a realizar en un proyecto. La EDT es una herramienta muy común y crítica en la gestión de proyectos.
El propósito de una EDT es documentar el alcance del proyecto. Su forma jerárquica permite una fácil identificación de los elementos finales. Siendo un elemento exhaustivo en cuanto al alcance del proyecto, la EDT sirve como la base para la planificación del proyecto. Todo trabajo a ser hecho en el proyecto debe poder rastrear su origen en una o más entradas de la EDT.

Referencias:
http://es.wikipedia.org/wiki/Algoritmo_de_compresi%C3%B3n_sin_p%C3%A9rdida
 http://es.wikipedia.org/wiki/Algoritmo_de_compresi%C3%B3n_con_p%C3%A9rdida
http://es.wikipedia.org/wiki/RLE
 http://es.wikipedia.org/wiki/Estructura_de_descomposici%C3%B3n_del_trabajo

No hay comentarios:

Publicar un comentario