Algoritmo de compresión sin pérdida

Imagen compuesta que muestra la diferencia entre JPG y PNG. La parte izquierda de la imagen es JPEG, la parte derecha es PNG. El software presentado es K3B que se ejecuta en KDE.

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 decir, la compresión sin pérdidas engloba a aquellas técnicas que garanticen generar un duplicado exacto del flujo de datos de entrada después de un ciclo de compresión / expansión. Por esta razón es utilizada para comprimir archivos que contienen datos que no pueden ser degradados o perdidos, como pueden ser documentos de texto, imágenes y sonido.

Características

Se fundamenta en conceptos de la teoría de la información, como la redundancia y entropía de los datos (ver compresión de datos) y es generalmente implementada usando uno o dos tipos de modelos diferentes: el estático y aquel basado en diccionario.

El modelo estático lee y codifica utilizando la probabilidad de aparición de cada carácter. Su forma más simple usa una tabla estática de probabilidades. Generar un árbol de Huffman completo de los datos tiene un coste computacional significativo; por tanto, no siempre se genera, sino que en su lugar se analizan bloques representativos de datos, dando lugar a una tabla de frecuencia característica. A partir de ésta, se genera un árbol de Huffman que se generaliza al resto de datos, dando lugar a un modelo estático. Pero utilizar un modelo estático tiene sus limitaciones. Si un flujo de entrada no concuerda bien con la estadística previamente 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 (o incluso más). Por tanto la siguiente mejora obvia fue construir una tabla que se construya conforme se recibe el flujo de entrada.

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 LZW y Markov LZMA .

Este sistema de compresión se usa en compresor de archivo (por ejemplo gzip y bzip2) y en archivadores de archivos que usan compresión (por ejemplo RAR, zip, 7z, ARJ, LHA, rzip y lrzip) y de disco (por ejemplo DriveSpace o Disk Cleanup); 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.