 |
Samedi 20 avril 2024 - 05:09 |
| Translate |
|
| Rubriques |
| Réseaux sociaux |
|
| Liste des jeux Amiga |
|
| Trucs et astuces |
|
| Glossaire |
|
| Galeries |
|
| Téléchargement |
|
| Liens |
|
| Partenaires |
|
| A Propos |
|
| Contact |
|
|
|
On pourrait croire que l'avancée technologique (intégration), à laquelle s'ajoute la baisse du prix des circuits mémoire, dévaloriserait l'intérêt de la compression de données. Or, si tant d'énergies cérébrales sont encore aujourd'hui employées afin de réduire le volume d'une masse de données, c'est qu'il existe de nombreuses raisons à cela. Au contraire, plus la technologie avance et plus la compression de données est au premier plan de l'actualité. Certaines branches de l'industrie ne pourraient plus s'en passer.
Tout d'abord, bien entendu, on peut citer le domaine des télécommunications par le fait qu'il y a moins de données à transmettre. Le calcul est simple pour une réduction de 50% du volume à transmettre, le prix de la communication sera réduit dans les mêmes proportions. Les constructeurs de modems ont d'ailleurs très vite compris comment ils pourraient en tirer profit en créant des circuits capables de diviser par 2 (protocole MNP 5 "MicroCom Network Protocol" pour modems V22bis et V32) voire par 4 le flot de données ! (norme CCITT V42bis).
Ceci équivaut à dire qu'un modem crachotant ses données en 2400 bauds a un débit réel 2 à 4 fois supérieur. La compression de données peut donc compenser une mauvaise transmission à plus haute vitesse sur une mauvaise ligne téléphonique. Il reste deux inconvénients : le prix du modem et une plus grande lenteur du débit effectif (à cause du temps de compression/décompression) même si à ce niveau le traitement est réalisé via des puces électroniques.
La simulation d'un débit plus élevé prend donc racine dans la compression de données. Pour comprendre le propos, tout en parlant d'actualité, prenons le cas du CDTV. Le débit de données pour afficher des images vidéo plein écran est trop faible pour envisager de les animer. Mais grâce à des circuits spéciaux de compression/décompression de données, on augmente le débit réel des données de manière spectaculaire (entre l'interface du lecteur de CD et l'Amiga). Conséquences : des images en mouvement peuvent être affichées...
La méthode de compression dont je vais maintenant détailler le principe est d'une utilisation banale sur Amiga. Elle est en effet la base de l'utilitaire PowerPacker et de très nombreux autres logiciels de même type. Trois auteurs se sont cassé la tête pour découvrir ce procédé génial : M. Lempel, M. Ziv et M. Welsh. L'histoire a oublié le troisième pour finalement retenir le nom de compression Lempel-Ziv (comme dirait Caliméro "ce n'est pas juste...").
La création de chaîne
Nous allons d'abord jouer pour "du beurre" (un peu de patience). Soit les informations suivantes : {z|z|x|z|x|x|z|x|z|z|x|z|x|x}
Si je veux transmettre à M. Welsh le contenu de mon exemple pédagogique, je peux utiliser plusieurs méthodes. Un procédé consisterait à lire les données séquentiellement de gauche à droite et de lui dicter les informations au fur et à mesure que je les rencontre. Mais comme je suis pour la loi du moindre effort, je vais retenir ce que je lui envoie dans une table en évitant à tout prix de me répéter. Pour ce faire, je construis pour chaque nouvelle entrée dans le tableau principal, une nouvelle chaîne qui est la somme des nouveaux et anciens codes. A chaque fois que je rencontre une chaîne de codes qui n'existe pas dans la table, je la rajoute et je dicte son code.
Si je rencontre une chaîne qui est déjà dans la table, je ne dicte pas le numéro d'entrée de cette chaîne mais je la rajoute mentalement à l'ancienne pour de futures recherches et je prends le code suivant. Bien entendu ce protocole est connu de M. Welsh et nous verrons plus loin comment il décode l'information que je lui donne. Pour clarifier la situation voici le résultat obtenu :
L'opération n°0 : la lecture donne "z" qui ne se trouve pas dans la table qui a été initialisée à vide au départ. Je dicte alors 0 qui correspond à la chaîne "z", l'équivalent du nouveau sous-tableau n°0.
L'opération n°1 consiste en la lecture du code "z". Or "z" se trouve déjà dans le sous-tableau n°0. Je passe donc au code "x". Je suis en présence de la chaîne "zx" qui n'existe pas dans la table, je dicte 1 et je stocke la chaîne "zx" dans le sous-tableau n°1.
Voyons un peu plus loin l'opération 11 qui consiste à lire le code "z". La chaîne que je recherche dans un des sous-tableaux est "zxz" qui existe dans le sous-tableau n°3. Je prends le code suivant "x". La chaîne formée est alors "zxzx" qui ne se retrouve dans aucun sous-tableau. Je place cette chaîne dans le nouveau sous-tableau 4 et je dicte le nombre 4. Enfin, le dernier code lu en opération n°13 est "x" qui n'est jamais présent comme premier caractère dans un sous-tableau. Je prends note de ce nouveau sous-tableau n°5 et je dicte la valeur 5.
Simple, me direz-vous. Mais il n'y a aucun gain car pour reconstruire le message de 14 octets différents, M. Welsh doit connaître la totalité de la table qui avec ses cinq sous-tableaux, prend 14 octets...
Bien vu : nous avons en effet joué pour du beurre.
La compression des chaînes
Mais une observation des résultats nous amène à constater que pour chaque nouvelle chaîne placée dans un sous-tableau, cette chaîne, excepté le dernier caractère, est déjà présente dans un autre sous-tableau. Le code dicté 4 correspond à la chaîne "zxzx" qui, si l'on retire le dernier caractère devient "zxz" et se retrouve bien dans le sous-tableau n°3. Donc, chaque sous-tableau peut être exprimé par deux caractères : le numéro d'un sous-tableau et le dernier caractère de l'ancienne chaîne.
Il y aura problème pour les chaînes d'un caractère. On y remédie simplement en insérant un "header" (en-tête) signifiant "il y a un seul caractère dans ce sous-tableau". L'en-tête prend ici la valeur -128.
Il construit alors le deuxième sous-tableau (n°1) et le garnit à son tour de la nouvelle chaîne qui est la concaténation du sous-tableau n°0 et du nouveau caractère "x" ce qui donne "zx". Et ainsi de suite...
Pour transmettre le message complet de 14 caractères, j'ai dicté 12 codes consécutifs. Il y a donc bien gain et compression. Mais ce n'est pas vraiment encore la bonne solution. Car si jamais il reste des caractères à transmettre et si ces caractères constituent à chaque fois de nouvelles entrées pour la table ("qsd" par exemple), il nous faudra mobiliser deux octets pour chaque nouveau sous-tableau d'un caractère construit !
Le gain sera vite perdu. On pourrait envisager une solution. Si les caractères à transmettre sont limités (pas exemple seulement des lettres alphabétiques), un code négatif indiquera un sous-tableau à chaîne simple, c'est-à-dire à caractère unique, dont la valeur est celle de la valeur absolue du code. Ce qui donne comme codes dictés : {-"z",0,x,1,x,1,z,2,-"x"}
Il faut remarquer que...
1. La table de décodage est construite progressivement. Il n'y a pas besoin pour le récepteur de la connaître à l'avance, contrairement à une compression par la méthode Huffman par exemple. C'est un avantage énorme !
2. Un même fichier peut être divisé en sous-fichier plus petit ce qui donne l'assurance que le numéro de référence du sous-tableau sera toujours inférieur au volume d'un sous-fichier. On peut envisager que notre chaîne d'exemple provient d'un fichier de 1294 octets, lequel a été subdivisé en 11 sous-fichiers (on lit 11 enregistrements en fait du fichier principal) de 128 octets maximum chacun. Le dernier enregistrement a une taille de 14 octets : {z|z|x|z|x|x|z|x|z|z|x|z|x|x}. Dans un cas de malchance maximum, l'enregistrement de 128 octets peut-être formé par 128 octets différents.
Ce qui donnera 128 sous-tableaux différents. Le dernier sous-tableau portant le numéro 127. Or, dans un octet il y a 8 bits qui peuvent représenter 256 combinaisons différentes (arrangements avec répétitions de "p" éléments choisis parmi "n" ==> 2 exp 8 = 256). Résultat des courses : il reste un bit libre à chaque numéro de sous-tableau qui peut alors servir de signe en cas de caractère unique. On peut faire mieux en transmettant "à l'envers" : d'abord le caractère à rajouter au sous-tableau sur un octet (signe compris) puis le numéro du sous-tableau (sur 7 bits) : {-"z",0,x,1,x,1,z,2,x,-"x"} prend 10 octets soit 80 bits ; {-"z",x,0,x,1,z,1,x,2,-"x"} prend 6x8 bits + 4x7 bits = 76 bits.
3. Si la taille du sous-fichier est grande, il y a donc de moins en moins "de chance" qu'un sous-tableau ne contienne pas la chaîne recherchée. Mais plus cette taille augmente et plus il faut d'octets pour stocker le numéro du sous-tableau... Pour un fichier de plus de 66 ko le nombre d'octets pour stocker le numéro de sous-tableau sera de 3 (car $FFFF < 66 ko).
Modification Lempel-Ziv
Attention, c'est ici que l'avion décolle : mais pas de panique, j'ai volontairement expliqué le procédé pas à pas en commentant au maximum.
L'idée au départ est assez géniale : il s'agit d'un décalage entre code lu et code émis. A chaque fois qu'un sous-tableau sera construit, il faudra émettre un code qui correspond à un numéro de sous-tableau déjà connu, c'est-à-dire le contenu du sous-tableau courant à l'exception du dernier caractère.
Le résultat est un sous-tableau déjà construit : "xz" est le contenu du sous-tableau n°4. Le code émis est le numéro du sous-tableau c'est-à-dire 4 (à condition que son contenu ne soit pas un unique caractère (voir plus bas).
Le sous-tableau suivant à construire contient comme premier caractère le dernier caractère qu'il a fallu retrancher pour émettre le dernier code. Exemple : le sous-tableau 8 contient "z" comme premier caractère, c'est-à-dire le caractère qu'il faut retrancher au contenu du sous-tableau n°7 pour émettre les caractères "xz" (c'est-à-dire le code 4 correspondant au sous-tableau n°4).
Une fois que le premier caractère du tableau suivant à construire est trouvé, le caractère suivant est lu. Si la nouvelle chaîne, issue de la concaténation du premier caractère du sous-tableau suivant et du code lu, se retrouve déjà dans un sous-tableau, on recommence l'opération en ajoutant un autre caractère lu à la chaîne.
Exemple : "z" est le premier caractère du sous-tableau n°8, le code lu suivant est "x" qui forme par concaténation la nouvelle chaîne "z"+"x"="zx". Or "zx" est le contenu du sous-tableau n°3 donc on lira un autre caractère, le "z" qui forme à son tour la chaîne "zx"+"z" = "zxz" qui ne se retrouve pas déjà dans un sous-tableau. Cette chaîne "zxz" forme alors le nouveau sous-tableau n°8...
Comme il y a décalage entre code lu et code émis, le numéro du premier sous-tableau est 2.
Un traitement spécial est appliqué au code unique : si l'alphabet ne comportait que deux lettres le "z" et le "x" il suffirait d'envoyer comme code pour les caractères uniques le code correspondant au numéro d'ordre du caractère dans cet alphabet {zx} : {0,0,1,3,4,4,3,5}.
Et en considérant qu'un alphabet complet peut se coder sur 128 caractères différents (en nombres négatifs suivant le code ASCII) : {-122,-122,-120,3,4,4,3,5}.
Pourquoi le nombre -122 ?
Avant la réception du message le programme de décompression doit initialiser une table contenant les valeurs ASCII de l'alphabet. Un code unique ne peut en effet se retrouver dans un sous-tableau construit mais se trouvera dans cette table. Comme il faut absolument faire la différence entre un code émis à valeur unique et un numéro de sous-tableau, ils seront différenciés grâce à leur signe.
Nous avions réussi à réduire le message de 14 octets à 76 bits soit 7,5 octets. Le résultat par décalage est bien supérieur : 8 octets ! Et la foule en délire applaudit cette performance signée Lempel-Ziv (et Welsh).
Comment décompresser ?
Un sous-tableau sera construit par concaténation de la précédente chaîne décodée et le premier caractère de la chaîne courante qui vient d'être décodée.
Exemple : le sous-tableau n°6 = chaîne "xz" (code 4 décodé) + le premier caractère de la chaîne courante qui est "x"="xz"+"x"="xzx" qui est bien le contenu du sous-tableau n°6.
Comme on peut le constater, la décompression est plus aisée à comprendre que le procédé de compression. A première vue aucun problème à signaler... mais en vérité, il y a parfois problème, et la solution en est fort simple.
1C2C forme une sous-chaîne qui est répétée deux fois plus loin dans la chaîne principale 1C2C1C2C qui est elle-même suivie par le 1C (premier caractère de la sous-chaîne répétée).
Exemple :
1C = "b", 2c = "a", 1C2C = "ba"
1C2C...1C2C1C2C1C = "bacabscccbababcc"
La solution est simple, il suffit de prendre la dernière chaîne affichée et de lui rajouter son propre premier caractère :
Conclusion
La méthode Lempel-Ziv est efficace et est beaucoup utilisée sur Amiga. Son avantage est de réaliser le codage à la volée : il n'est pas indispensable de connaître les données avant la compression. Ce qui permet la compression de données en temps réel, et de ne pas stocker une table de codage.
Souvent pour une plus grande efficacité, on utilise la méthode de compression par décalage de chaînes Lempel-Ziv et la méthode probabiliste de Huffman. Cela implique une analyse préalable des données ainsi que la nécessité de stocker une table de codage.
J'entends que l'on me réclame un listing... Ok, en fait pour celui qui a bien assimilé la théorie "rien de plus simple pour comprendre" le listing C qui se trouve sur l'AmigaLibDisk n°51 et qui utilise notre méthode Lempel-Ziv (pensez à votre serviteur qui muni du listing a dû faire la démarche inverse pour démonter le mécanisme)... J'avoue qu'en vérité le listing n'est pas facile à comprendre : attention la méthode est utilisée en exploitant les informations bits à bits et ceci comme un alphabet de deux lettres (le 0 et le 1 à la place des "x" et "z" supra...).
|
