Lempel – Ziv – Storer – Szymanski ( LZSS ) es un algoritmo de compresión de datos sin pérdidas , un derivado de LZ77 , que fue creado en 1982 por James A. Storer y Thomas Szymanski . LZSS se describió en el artículo "Compresión de datos mediante sustitución textual" publicado en Journal of the ACM (1982, págs. 928–951). [1]
LZSS es una técnica de codificación de diccionario . Intenta reemplazar una cadena de símbolos con una referencia a una ubicación de diccionario de la misma cadena.
La principal diferencia entre LZ77 y LZSS es que en LZ77 la referencia del diccionario podría ser más larga que la cadena que estaba reemplazando. En LZSS, estas referencias se omiten si la longitud es menor que el punto de "equilibrio". Además, LZSS usa banderas de un bit para indicar si el siguiente fragmento de datos es un literal (byte) o una referencia a un par de desplazamiento / longitud.
Ejemplo
Aquí está el comienzo de Green Eggs and Ham del Dr. Seuss , con números de caracteres al comienzo de las líneas para mayor comodidad. Green Eggs and Ham es un ejemplo óptimo para ilustrar la compresión LZSS porque el libro en sí solo contiene 50 palabras únicas, a pesar de tener un número de palabras de 170. [2] Por lo tanto, las palabras se repiten, pero no en sucesión.
0: soy Sam 9: 10: Sam soy 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 y el jamón?112:113: No me gustan, Sam-lo-soy.143: No me gustan los huevos verdes y el 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 líneas nuevas de un byte, este texto comprimido con LZSS se convierte en 94 bytes de longitud:
0: soy Sam 9:10: (5,3) (0,4)dieciséis:17: Eso (4,4) -¡Yo-soy! (19,16) No me gusta45: t (21,14)49: ¿Tienes (58,5) huevos verdes y jamón?78: (49,14) ellos, (24,9). (112,15) (92,18).
Nota: esto no incluye los 12 bytes de banderas que indican si el siguiente fragmento de texto es un puntero o un literal. Al agregarlo, el texto se convierte en 106 bytes de longitud, que aún es más corto que los 177 bytes originales.
Implementaciones
Muchos archivadores populares como PKZip , ARJ , RAR , ZOO , LHarc utilizan LZSS en lugar de LZ77 como algoritmo de compresión principal; la codificación de caracteres literales y de pares de longitud-distancia varía, siendo la opción más común la codificación de 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] de Apple Mac OS X utiliza LZSS como uno de los métodos de compresión de código del kernel. [7]
Ver también
- LZ77
- Lempel – Ziv – Welch (LZW)
Referencias
- ↑ Storer, James A .; Szymanski, Thomas G. (octubre de 1982). "Compresión de datos mediante sustitución textual". Revista de la ACM . 29 (4): 928–951. doi : 10.1145 / 322344.322346 .
- ^ "10 historias detrás de las historias del Dr. Seuss" . CNN . 23 de enero de 2009 . Consultado el 26 de enero de 2009 .
- ^ Espejo de Simtel.net. Implementación de Haruhiko Okumura de 1989. Archivado el 3 de febrero de 1999.
- ^ Haruhiko Okumura. Historia de la compresión de datos en Japón. Archivado el 10 de enero de 2016.
- ^ Hargreaves, Shawn , et al. Allegro código fuente: lzss.c . Consultado el 13 de julio de 2016.
- ^ Korth, Martin. "GBATEK: Funciones de descompresión de BIOS GBA" . Archivado desde el original el 23 de marzo de 2013 . Consultado el 2 de enero de 2014 .. Consultado el 3 de agosto de 2008.
- ^ "herramientas_kext / compresión.c" . GitHub . Código abierto de Apple . Consultado el 28 de diciembre de 2019 .