LZSS

Lempel-Ziv-Storer-Szymanski (LZSS) est une méthode de compression de données sans perte créée en 1982 par Storer et Szymanski[1].

LZSS utilise une technique de codage à dictionnaire inspirée de LZ77 tout en tentant d'éviter certains goulots d'étranglement, sans que les ressources demandées au CPU deviennent énormes (par exemple, augmenter la taille de la fenêtre augmente la complexité de LZ77 en O(n) alors que pour LZSS la complexité est de O(ln(n))).

Pour arriver à ce résultat, deux améliorations majeures ont été apportées :

• Tout d'abord la représentation des informations nécessaires dans le fichier compressé a été revue et améliorée en ajoutant un bit au début de chaque code indiquant si la suite sera un caractère encore inconnu ou une chaîne précédemment rencontrée. Lorsque le caractère n'a encore jamais été rencontré, il n'y a donc plus besoin de donner des coordonnées factices, économisant plusieurs octets à chaque nouveau caractère.
• L'autre amélioration se joue sur l'organisation des chaînes récupérées qui sont organisées dans un arbre plutôt que comme une suite de symboles, ce qui pouvait s'avérer long à parcourir. Cela permet à l'algorithme de gagner en vitesse, notamment pour les très grandes fenêtres.

Notes et références

1. James Andrew Storer, Thomas Gregory Szymanski, Data compression via textual substitution, Journal of the ACM, vol. 29 n°4, octobre 1982, pp 928-951 DOI 10.1145/322344.322346

Bibliographie

• (en) David Salomon, Data Compression : The Complete Reference, New York/London, Springer, 2007, 1092 p. (ISBN 978-1-84628-603-2, lire en ligne)
• Mark Nelson (trad. Hervé Soulard), La Compression de données : texte, images, sons, DUNOD, 1993, 421 p. (ISBN 2-10-001681-4)

Liens externes

• Implémentation en C par Haruhiko Okumura, 1989