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éé en 1982 par James Storer et Thomas Szymanski.

LZSS utilise une technique de codage à dictionnaire inspirée de LZ77 tout en tentant d'éviter certains de ses goulots d'étranglement l'empêchant d'améliorer son efficacité sans que les ressources demandés 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 majeurs ont étés apportés:

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

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)