LZSS

El algoritmo de compresión lz77 (de Abraham Lempel, Jacob Ziv y 1977) pertenece a la familia de compresores sin pérdida, también llamados compresores de texto, a los cuales se les llama así porque no omiten información del archivo al comprimirlo, al contrario que los compresores que utilizan algoritmos del tipo lossy, que omiten algo de información pero que disminuyen considerablemente el tamaño del archivo original, el cual es el caso de los archivos MP3, MPG, jpeg, etc.

Características

Los compresores basados en algoritmos sin pérdida se utilizan cuando la información a comprimir es crítica y no se puede perder información, por ejemplo en los archivos ejecutables, tablas de bases de datos, o cualquier tipo de información que no admita pérdida.

El modelo lz77 es muy usado porque es fácil de implementar y es bastante eficiente.

En 1977 Abraham Lempel y Jacob Ziv presentaron su modelo de compresión basado en diccionario, para compresión de texto –compresión de texto se refiere a compresión sin pérdida para cualquier tipo de datos–. Hasta la fecha todos los algoritmos de compresión desarrollados eran básicamente compresores estáticos. El nuevo modelo fue llamado lz77 (por razones obvias). La salida consistía siempre en desplazamientos o corrimientos y tamaños del texto visto anteriormente. También se incluía en la salida el siguiente byte después de una coincidencia, porque el contexto (últimos bytes vistos) de este byte es la frase, y si no era parte de la frase (la coincidencia), luego tal vez no se había comprimido, así que, ¿Para que desperdiciar tiempo tratando de encontrar una coincidencia (o espacio) para él?

En 1982 James Storer y Thomas Szymanski basados en el trabajo de Lempel y Ziv, presentaron su modelo, el lzss. La diferencia principal es en la salida, lz77 siempre daba un para desplazamiento/tamaño, aún si la coincidencia era de un solo byte (en cuyo caso usaban más de ocho bits para representar un byte) de manera que el LZSS usa otro truco para mejorarlo: usa banderas ( flags), que ocupan un solo bit y nos informan de lo que viene luego: una literal o un par desplazamiento/tamaño y este algoritmo es el que actualmente usamos, pero el lzss es comúnmente llamado lz77, así que lo llamaremos lz77 de este punto en adelante, pero es importante recordar que también puede ser llamado LZSS. LZSS también puede usar árboles binarios o árboles de sufijos para hacer búsquedas más eficientes.

La teoría es muy simple e intuitiva. Cuando se halla una coincidencia (también llamada frase o conjunto de bytes que ya han sido vistos en el archivo de entrada) en lugar de escribir dichos bytes se escribe el desplazamiento o tamaño de la repetición: dónde está y su longitud.

Éste es un modelo basado en diccionario, porque se mantiene un diccionario (que en este caso se conoce como “Ventana Corrediza”) y se hace referencia a ella con pares desplazamiento/tamaño. Esta versión de lz77, usa una ventana corrediza, la cual tiene un tamaño máximo, de manera que la ventana no puede ser el archivo completo, en su lugar, la ventana corrediza mantiene los últimos bytes “vistos”.

Other Languages
català: LZSS
français: LZSS
日本語: LZSS
polski: LZSS
中文: LZSS