LZSS

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 ne 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és 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[modifier | modifier le code]

  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[modifier | modifier le code]

  • (en) David Salomon, Data Compression: The Complete Reference, 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)

Lien externe[modifier | modifier le code]