Lempel–Ziv–Storer–Szymanski

Lempel–Ziv–Storer–Szymanski ( LZSS ) es un algoritmo de compresión de datos sin pérdidas , derivado de LZ77 , creado en 1982 por James A. Storer y Thomas Szymanski . LZSS se describió en el artículo "Data compression via textual substitution" publicado en el Journal of the ACM (1982, pp. 928–951). ^{[ 1 ]} 

LZSS es una técnica de codificación por diccionario . Intenta reemplazar una cadena de símbolos con una referencia a la ubicación de esa misma cadena en un diccionario.

La principal diferencia entre LZ77 y LZSS radica en que, en LZ77, la referencia al diccionario puede ser más larga que la cadena que reemplaza. En LZSS, dichas referencias se omiten si la longitud es menor que el punto de equilibrio. Además, LZSS utiliza indicadores de un bit para señalar si el siguiente bloque de datos es un literal (byte) o una referencia a un par desplazamiento/longitud.

Aquí comienza « Huevos verdes con jamón» del Dr. Seuss , con números de caracteres al inicio de cada línea para mayor comodidad. «Huevos verdes con jamón» es un buen ejemplo para ilustrar la compresión LZSS, ya que el libro en sí solo contiene 50 palabras únicas, a pesar de tener un total de 170 palabras. ^{[ 2 ]} Por lo tanto, las palabras se repiten, pero no de forma consecutiva.

 0: Soy Sam 9: 10: Sam soy yo 19: 20: ¡Ese Sam-yo-soy! 35: ¡Ese Sam-yo-soy! 50: No me gusta 64: ¡Ese Sam-yo-soy! 79: 80: ¿Te gustan los huevos verdes con jamón? 112: 113: No me gustan, Sam-yo-soy. 143: No me gustan los huevos verdes con jamón. 

Este texto ocupa 177 bytes sin comprimir. Suponiendo un punto de equilibrio de 2 bytes (y, por lo tanto, pares de puntero/desplazamiento de 2 bytes) y un salto de línea de un byte, este texto comprimido con LZSS se convierte en un texto de 95 bytes:

0: Soy Sam 9: 10: (5,3) (0,4) 16: 17: ¡Ese(4,4)-yo-soy!(19,15) 32: No me gusta 46: t(21,14) 50: ¿Te gustan los huevos verdes con jamón? (58,5) 79: (49,14) ellos,(24,9).(112,15)(92,18). 

Nota: esto no incluye los 11 bytes de indicadores que señalan si el siguiente fragmento de texto es un puntero o un literal. Al agregarlos, el texto pasa a tener 106 bytes de longitud, lo cual sigue siendo más corto que los 177 bytes originales.

Muchos archivadores populares como ARJ , RAR , ZOO y LHarc utilizan LZSS en lugar de LZ77 como algoritmo de compresión principal; la codificación de caracteres literales y de pares longitud-distancia varía, siendo la opción más común la codificación Huffman . La mayoría de las implementaciones provienen de un código de dominio público de 1989 de Haruhiko Okumura . ^{[ 3 ] [ 4 ]} La versión 4 de la biblioteca Allegro puede codificar y decodificar un formato LZSS, ^{[ 5 ]} pero la función se eliminó de la versión 5. La BIOS de Game Boy Advance puede decodificar un formato LZSS ligeramente modificado. ^{[ 6 ]} macOS de Apple utiliza LZSS como uno de los métodos de compresión para el código del kernel. ^{[ 7 ]}

• Lempel-Ziv-Welch (LZW)