Suivez-nous sur X
|
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z,
ALL
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
A propos d'Obligement
|
|
David Brunet
|
|
|
|
Dossier : La compression de données avec l'algorithme LZW
(Article écrit par Emmanuel Hocdet et extrait d'Amiga News Tech - avril 1992)
|
|
La saga des réducteurs d'octets continue, avec cette fois-ci l'algorithme LZW, certainement le plus
utilisé dans les logiciels de compression de données.
L'algorithme dit LZW vient du nom de ses inventeurs : Lempel, Ziv et un peu plus tard Welsh, qui y
apporta des améliorations. Son principe premier est d'essayer de réduire les chaînes de caractères qui se répètent.
Au fur et à mesure de la lecture des données d'un fichier, le repérage des chaînes de caractères fréquemment
rencontrées permet au compresseur de les remplacer par une valeur spécifique. Cette valeur sera ensuite
utilisée par le décompresseur pour reconstituer la suite d'octets ainsi compactée. Malheureusement, quoiqu'il
puisse paraître une fois l'algorithme posé noir sur blanc, la mise en oeuvre d'une telle méthode de compression
est loin d'être simple. Les problèmes surviennent rapidement, et Lempel-Ziv ne seront pas de trop pour nous
aider à parvenir à nos fins.
Première approche
La compression par chaînes de caractères demande une référence constante sur les chaînes déjà rencontrées,
afin de savoir si elles doivent être compactées. Une première méthode consiste à parcourir constamment les
données déjà traitées. Son avantage est qu'il permet de ne prendre aucune place mémoire supplémentaire, mais
c'est bien là le seul avantage : le temps pris est, lui, plutôt considérable. De plus, cette proposition ne
permet pas de stocker un code spécial pour chaque nouvelle chaîne de caractères rencontrée, et est donc
inadaptée à notre cas.
La solution est de stocker ces codes dans une table (qu'on appelle un dictionnaire) qui sera modifiée au
fur et à mesure de la compression. Bien sûr, il est inconcevable que cette table soit présente dans le
fichier des données compactées. Le décompresseur doit donc être capable de recréer la table afin de pouvoir
décoder les données et les restituer mot pour mot (ou plutôt octet pour octet).
Vous vous êtes certainement posé une autre question : comment différencier les données compressées des données non
compressées ? Les chaînes de caractères non compactées ne sont que des suites d'octets, alors gardons simplement
leur propre valeur ASCII (ils auraient pu faire un tabac aux JO !). Le code des chaînes compactées sera, par
suite, une valeur supérieure à 255.
L'utilisation, comme avec le Run-Lenght-Encoding, d'une valeur caractéristique distinguant les données compressées
des non compressées et permettant en plus d'en connaître le nombre, est à proscrire. La solution est de travailler
sur un nombre de bits supérieur à 8. Avec 9 bits, on peut coder 256 chaînes de caractères (valeurs de 256 à 511)
et tout de même garder les 256 octets, étendus à 9 bits. Naturellement, la vitesse de traitement sera d'autant
plus réduite (surtout sur un 68000), mais tous les algorithmes permettant des gains de compressions importants utilisent
ce système. Alors pas de remords, fonçons...
L'algo de Lempel-Ziv
L'algorithme proposé par Lempel-Ziv fonctionne ainsi : la table permettant de stocker les chaînes de caractères est
initialisée. Le premier caractère lu est considéré comme une chaîne de un octet. On lit le caractère suivant.
Si la chaîne composée de l'ancienne et de ce caractère se trouve dans la table, la chaîne devient à son tour l'ancienne
chaîne et on lit de nouveau un caractère, et ainsi de suite jusqu'à ce que la chaîne ne se retrouve pas dans la table.
Le code de l'ancienne chaîne est alors émise. La nouvelle chaîne est rangée dans la table, le dernier caractère lu devient
l'ancienne chaîne, etc. Reportez-vous à l'exemple de codage/décodage avec les trois lettres magiques : A, N et T.
Le décodage correspond à l'opération inverse, à ceci près que le rangement des chaînes dans la table est décalé par
rapport au décodage des chaînes. La table initialisée, le premier code est lu, décodé et émis. On effectue ensuite
une boucle : lecture du nouveau code, émission de la chaîne décodée et rangement dans la table de la chaîne précédente,
avec le premier caractère de la nouvelle chaîne. L'exemple traité fait apparaître un problème lors du décodage (!) :
en effet, lorsqu'une nouvelle chaîne se répète deux fois de suite, le code n'apparaît pas encore dans la table au
moment où l'on veut décoder la seconde. Dans ce cas, la solution est simple : la chaîne à émettre correspond à l'ancienne
chaîne, plus le premier caractère de celle-ci.
Algorithme de compression LZW
Algorithme de décompression LZW
Utilisations
Cet algorithme, bien qu'excellent, est rarement utilisé tel quel. La souplesse de la table permet au programmeur
toute les folies : il est possible d'y inclure des valeurs spécifiques permettant de transmettre des messages du
compresseur au décompresseur. On peut, grâce à ces messages, réaliser un programme utilisant l'algorithme avec des
codes variables (en commençant avec des codes sur 9 bits et en augmentant progressivement cette longueur ; en général,
elle ne dépassent pas 14 bits, car au-delà d'un certain seuil, il est préférable de limiter la longueur des codes,
ou plutôt de revenir à une taille de 9 bits).
Les messages peuvent aussi servir à réinitialiser la table, éliminer le code des chaînes qui ne sont plus répétées...
Lors de cette initialisation, personne ne vous empêche d'y intégrer des chaînes susceptibles de se trouver rapidement
dans les données à traiter. Un autre moyen d'accroître les performances, est d'inclure à l'algorithme d'autres méthodes
de compactage, comme la compression par demi-octet et le Run-Lenght-Encoding. Les messages indiquent alors le type de
compression. Mais attention, en plus d'un accroissement du temps de traitement (il faut regarder de quel type sont les
données afin de choisir l'algorithme le mieux adapté), le programme devient vite compliqué. Ce sont de longues heures
de débogage qui vous attendent. De plus, la compression ne peut plus se faire à la volée : une partie du fichier à
compacter doit toujours être présent.
Il existe aussi d'autres méthodes de compression dérivées de celle de Lempel-Ziv-Welch. Celle utilisée par Nico
François dans l'excellent PowerPacker,
qui depuis la version 3 n'est plus un domaine public, je le rappelle, est
particulièrement judicieuse : au lieu d'émettre des codes de plus en plus grand aux chaînes de caractères compactées,
il propose de faire correspondre ce code à la dernière position de la chaîne par rapport au pointeur sur les données
du fichier en cours de traitement.
Le gros avantage de cette méthode est qu'il n'y a pas de réinitialisation de la table de codage. Lorsque les
données se trouvent trop éloignées du pointeur sur les octets à traiter, elles ne sont plus pris en compte. De plus,
la décompression ne nécessite aucune table, elle n'a besoin que des données précédemment restituées. Par contre,
elle est obligée de stocker, comme pour la suppression des répétitions, le nombre d'octets de la chaîne à restituer
ou à recopier si elle n'était pas compactée.
Des efforts doivent aussi être faits au niveau du format de la table de codage. En effet, de celle-ci dépendra la
vitesse du programme de compression. Il faut réduire à tout prix le temps nécessaire au parcours de la table
permettant de voir si la chaîne émise s'y trouve déjà. Un moyen est de créer autant de tables qu'il y a de chaînes
de longueurs différentes. C'est bien sûr au programmeur de déterminer le nombre maximal de caractères contenus dans
une chaîne. La place mémoire prise par une telle table risque de poser des problèmes si vous ne disposez que de 512 ko,
mais on a rien sans rien. La décompression s'effectue beaucoup plus rapidement (heureusement) puisque la valeur
du code sert de pointeur dans la table et permet de retrouver immédiatement la chaîne correspondante.
Limites
L'intérêt d'un tel algorithme est qu'il reste tout de même simple à programmer. Il réalise une compression en
codant des chaînes de caractères à la volée, ce qui est tout à fait adapté à la transmission de données (modems, télécopie...).
D'autant plus qu'en moyenne, il réduit la taille des programmes de 40%
à 50%. Les gains peuvent aller jusqu'à 70%, voire 80% pour un texte ou un source ASCII. Ne vous étonnez pas si,
pour un fichier, même important, le gain reste très faible, voire négatif : c'est juste que les données ne sont
pas faites pour ce type de compression. Cela arrive souvent pour des images et des sons numérisés, les fichiers
déjà compactés (essayez de compresser une image IFF avec PowerPacker, vous verrez le résultat)... Il faut alors
faire appel à Huffman, ce que nous ferons dès le mois prochain...
|