Lempel-Ziv-Stac ( LZS , o compresión Stac o Stacker compresión [1] ) es una compresión de datos sin pérdidas algoritmo que utiliza una combinación de la LZ77 algoritmo de compresión de ventana deslizante y se fija la codificación de Huffman . Originalmente fue desarrollado por Stac Electronics para la compresión de cinta, y posteriormente se adaptó para la compresión de disco duro y se vendió como el software de compresión de disco Stacker . Más tarde se especificó como un algoritmo de compresión para varios protocolos de red. LZS se especifica en la pila de Cisco IOS .
Estándares
La compresión LZS está estandarizada como estándar INCITS (anteriormente ANSI). [2]
La compresión LZS se especifica para varios protocolos de Internet:
- RFC 1967 - Protocolo de compresión PPP LZS-DCP (LZS-DCP)
- RFC 1974 - Protocolo de compresión PPP Stac LZS
- RFC 2395 - Compresión de carga útil IP mediante LZS
- RFC 3943 - Compresión del protocolo de seguridad de la capa de transporte (TLS) mediante Lempel-Ziv-Stac (LZS)
Algoritmo
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 al diccionario. Si no se encuentra ninguna coincidencia, el siguiente byte de datos se codifica como un byte "literal". El flujo de datos comprimidos termina con un marcador de finalización.
Formato de datos comprimidos
Los datos se codifican en una secuencia de tokens de ancho de bits variable.
Byte literal
Un byte literal se codifica como un bit '0' seguido de los 8 bits del byte.
Referencia de desplazamiento / longitud
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 final, 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 se refiere al byte más reciente en el búfer de historial, inmediatamente antes del siguiente byte de datos a procesar. Un desplazamiento se codifica como:
- Si el desplazamiento es menor que 128: un bit '1' seguido de un valor de desplazamiento de 7 bits.
- Si el desplazamiento es mayor o igual a 128: un bit '0' seguido de un valor de desplazamiento de 11 bits.
Una longitud se codifica como:
Largo | Codificación de bits |
---|---|
2 | 00 |
3 | 01 |
4 | 10 |
5 | 1100 |
6 | 1101 |
7 | 1110 |
8 hasta 22 | 1111 xxxx, donde xxxx es la longitud - 8 |
23 hasta 37 | 1111 1111 xxxx, donde xxxx es la longitud - 23 |
longitud> 37 | (1111 repetidas N veces) xxxx, donde N es el resultado entero de (longitud + 7) / 15 y |
Marcador de fin
Un marcador de finalización se codifica como el token de 9 bits 110000000. Después del marcador de finalización, se añaden de 0 a 7 bits "0" adicionales según sea necesario, para rellenar el flujo hasta el siguiente límite de bytes.
Patentes
La spin-off de Stac Electronics, Hifn, ha sido titular de 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-1994, Stac Electronics demandó con éxito a Microsoft por infracción de las patentes LZS en el programa de compresión de disco DoubleSpace incluido con MS-DOS 6.0 . [5]
Ver también
Referencias
- ^ "Comprensión de la compresión de datos" . Cisco . Consultado el 7 de mayo de 2021 .
- ^ INCITS / ANSI X3.241-1994 - Método de compresión de datos - Codificación adaptable con ventana deslizante para el intercambio de información
- ^ Amigo, Robert C. "Declaración de Hifn sobre derechos de propiedad intelectual reclamada en draft-friend-tls-lzs-compresión, RFC1967, RFC1974, RFC2118, RFC2395 y RFC3078" . Consultado el 21 de julio de 2010 .
- ^ Amigo, Robert. "Declaración de Hifn sobre derechos de propiedad intelectual reclamados en algoritmos de compresión LZS y MPPC" . Consultado el 21 de julio de 2010 .
- ^ Queja por infracción de patente y demanda de juicio con jurado Archivado el 9 de mayo de 2007 en la Wayback Machine por Stac Electronics v Microsoft Corporation