Algoritmo de compresión sin pérdida

De Wikipedia, la enciclopedia libre
(Redirigido desde «Compresión (informática)»)
Saltar a: navegación, búsqueda

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 u ocupando un espacio menor, siendo posible una reconstrucción exacta de los datos originales.

Es utilizada para comprimir archivos o información que contienen datos que no pueden ser degradados o perdidos, como pueden ser documentos de texto, imágenes y sonido.

La compresión sin pérdidas 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 carácter. 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, sino que 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 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.

Algunos algoritmos de compresión sin pérdidas son los algoritmos Lempel-Ziv, que incluyen LZ77, LZ78 y LZ-W.

Este sistema de compresión se usa en compresores de archivo (RAR, gzip, bzip2, 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 vídeo es menos común; pueden ser usados para su captura y edición, pero no comercializados para reproducción doméstica.

Existen distintos métodos de compresión sin pérdidas. Por ejemplo está la compresión RLE o run-length encoding (utilizada para los archivos BMP), la cual toma secuencias de datos (datos de elementos consecutivos con valores idénticos) y los almacena en un valor único más su recuento. Es el más adecuado para gráficos sencillos, donde hay largas tiradas de idénticos elementos de datos.

Véase también[editar]

Enlaces externos[editar]