Obligement - L'Amiga au maximum

Jeudi 06 août 2020 - 21:16  

Translate

En De Nl Nl
Es Pt It Nl


Rubriques

 · Actualité (récente)
 · Actualité (archive)
 · Comparatifs
 · Dossiers
 · Entrevues
 · Matériel (tests)
 · Matériel (bidouilles)
 · Points de vue
 · En pratique
 · Programmation
 · Reportages
 · Quizz
 · Tests de jeux
 · Tests de logiciels
 · Tests de compilations
 · Trucs et astuces
 · Articles divers

 · Articles in english


Twitter

Suivez-nous sur Twitter




Liste des jeux Amiga

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


Trucs et astuces

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


Glossaire

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


Galeries

 · Menu des galeries

 · BD d'Amiga Spécial
 · Caricatures Dudai
 · Caricatures Jet d'ail
 · Diagrammes de Jay Miner
 · Images insolites
 · Fin de jeux (de A à E)
 · Fin de Jeux (de F à O)
 · Fin de jeux (de P à Z)
 · Galerie de Mike Dafunk
 · Logos d'Obligement
 · Pubs pour matériels
 · Systèmes d'exploitation
 · Trombinoscope Alchimie 7
 · Vidéos


Téléchargement

 · Documents
 · Jeux
 · Logiciels
 · Magazines
 · Divers


Liens

 · Sites de téléchargements
 · Associations
 · Pages Personnelles
 · Matériel
 · Réparateurs
 · Revendeurs
 · Presse et médias
 · Programmation
 · Logiciels
 · Jeux
 · Scène démo
 · Divers


Partenaires

Annuaire Amiga

Amedia Computer

Relec

Hit Parade


A Propos

A propos d'Obligement

A Propos


Contact

David Brunet

Courriel

 


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.

compression des données

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

compression des données

Algorithme de décompression LZW

compression des données

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.

compression des données

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...


[Retour en haut] / [Retour aux articles]