LZSS
Lempel-Ziv-Storer-Szymanski (LZSS) es un método de compresión de datos sin pérdidas creado en 1982 por Storer y Szymanski .
LZSS utiliza una técnica de codificación de diccionario inspirada en LZ77 mientras intenta evitar ciertos cuellos de botella, sin que los recursos exigidos a la CPU se vuelvan enormes (por ejemplo, aumentar el tamaño de la ventana aumenta la complejidad de LZ77 en O (n) mientras que para LZSS la complejidad es O (en (n)) ).
Para lograr este resultado, se han realizado dos mejoras importantes:
- En primer lugar, se ha revisado y mejorado la representación de la información necesaria en el archivo comprimido añadiendo un bit al comienzo de cada código que indica si la secuencia será un carácter aún desconocido o una cadena encontrada previamente. Cuando el carácter nunca se ha encontrado antes, por lo tanto, no es necesario dar coordenadas ficticias, ahorrando varios bytes para cada nuevo carácter.
- La otra mejora se juega en la organización de las cuerdas recuperadas que están organizadas en un árbol en lugar de como una serie de símbolos, lo que podría resultar largo para recorrer. Esto permite que el algoritmo gane velocidad, especialmente para ventanas muy grandes.
Notas y referencias
-
James Andrew Storer, Thomas Gregory Szymanski, Compresión de datos mediante sustitución textual , Journal of the ACM , vol. 29 n ° 4, octubre de 1982, pp 928-951 DOI : 10.1145 / 322344.322346
Bibliografía
- (en) David Salomon, Compresión de datos: la referencia completa , Nueva York / Londres, Springer,2007, 1092 p. ( ISBN 978-1-84628-603-2 , leer en línea )
- Mark Nelson ( trad . Hervé Soulard), Compresión de datos: texto, imágenes, sonidos , DUNOD,1993, 421 p. ( ISBN 2-10-001681-4 )
enlaces externos