Lempel–Ziv–Stac ( LZS , o compresión Stac o compresión Stacker [1] ) es un algoritmo de compresión de datos sin pérdida que utiliza una combinación del algoritmo de compresión de ventana deslizante LZ77 y la codificación Huffman fija . Fue desarrollado originalmente por Stac Electronics para la compresión de cintas y posteriormente adaptado para la compresión de discos duros y vendido como el software de compresión de discos Stacker . Más tarde se especificó como un algoritmo de compresión para varios protocolos de red. LZS se especifica en la pila Cisco IOS .
La compresión LZS está estandarizada como un estándar INCITS (anteriormente ANSI). [2]
La compresión LZS se especifica para varios protocolos de Internet:
La compresión y descompresión LZS utiliza un algoritmo de tipo LZ77 . Utiliza los últimos 2 KB de datos sin comprimir como un diccionario de ventana deslizante.
Un compresor LZS busca coincidencias entre los datos que se van a comprimir y los últimos 2 KB de datos. Si encuentra una coincidencia, codifica una referencia de desplazamiento/longitud en el diccionario. Si no encuentra ninguna coincidencia, el siguiente byte de datos se codifica como un byte "literal". El flujo de datos comprimidos finaliza con un marcador de fin.
Los datos se codifican en un flujo de tokens de ancho de bits variable.
Un byte literal se codifica como un bit '0' seguido de los 8 bits del byte.
Una referencia de desplazamiento/longitud se codifica como un bit "1" seguido del desplazamiento codificado, seguido de la longitud codificada. Una codificación excepcional es un marcador de fin, que se describe a continuación.
Un desplazamiento puede tener un valor mínimo de 1 y un valor máximo de 2047. Un valor de 1 hace referencia al byte más reciente en el búfer de historial, inmediatamente anterior al siguiente byte de datos que se procesará. Un desplazamiento se codifica como:
Una longitud se codifica como:
Un marcador final se codifica como el token de 9 bits 110000000. Después del marcador final, se agregan de 0 a 7 bits '0' adicionales según sea necesario, para completar el flujo hasta el siguiente límite de byte.
Hifn, una empresa derivada de Stac Electronics, posee varias patentes para la compresión LZS. [3] [4] Estas patentes caducaron debido a la falta de pago de las tasas y los intentos de restablecerlas en 2007 fracasaron.
En 1993-94, Stac Electronics demandó con éxito a Microsoft por infracción de las patentes LZS en el programa de compresión de discos DoubleSpace incluido en MS-DOS 6.0 . [5]