CODING ★ L'art de la compression ★

Bidouilles ACPC n°41 - L'art de la compression

Sined nous fait l'honneur d'étaler sa science. En effet, vous pourrez, à partir de ce numéro, suivre ses délires pour tout comprendre , aux algorithmes de compactage. Vous savez, les programmes qui font rentrer dix litres de vin dans une bouteille.

Comme tout bon article, il faudra commencer par un rappel historique de la chose, à savoir...

LA NAISSANCE

La compression a vu le jour au moment des premiers transferts de données via modem et lignes téléphoniques. En effet, il fallait faire le maximum pour gagner du temps, histoire de ne point trop engraisser l'ancêtre des PTT. Ce fut la belle époque ou de nombreux cerveaux vifs et vaillants travaillèrent pour la bonne cause de la compression de données. Nombreuses furent les différentes versions, plus ou moins efficaces qui virent le jour pour des raisons bassement pécuniaires. Le fait est que maintenant, nous disposons d'algorithmes plus que performants et d'un usage simple, si l'ont s'en refere aux capacités du cerveau d'un Einstein moyen. Je vois d'ici la difficulté que je vais rencontrer a tenter de vous expliquer un tant soit peu l'idée du principe Lempel, Ziv, Welch, voir encore Huffmann... (Zouba gabouts).

Qu'est-ce que la compression, ou du moins, 'quel en est le principe ??? Simple, c'est, en clair, le remplacement d'un grand élément par un codage prenant moins de place mais représentant bien l'objet initial. La compression est un peu comme la purée déshydratee, il suffit de lui rajouter de l'eau pour qu'elle reprenne sa consistance initiale (voila que l'informatique a un rapport avec la bouffe maintenant... Reviens Sined, j'ai les mêmes a la maison). En fait, beaucoup de petits malins diront ici qu'il est facile d'affecter a des valeurs que l'ont retrouve souvent, des codes spécifiques qui seront reconnaissables par quelques identificateurs tarabiscotes pour qu'ils ne soient pas

confondus avec des données malvenues... Faites des essais, vous verrez que ce genre de mise en place de formats de zones a identificateurs zigomatiques prennent plus de place qu'elles n'en font gagner. Bref, si des super professionnels de l'informatique, de l'arithmétique, de la logique et des mathématiques binaires se sont grattes le ciboulot a s'en faire peter l'encéphalogramme, cela pendant de longs mois, c'est qu'ils sont arrives suffisamment loin pour qu'on ait juste a utiliser le fruit de leur démoniaque et si sublime entreprise.

Amen a vous, génies du logiciel sans qui l'informatique ne serait qu'alignements vains de bits sans flamme aucune. Bon, je reprends une aspirine et je vous accouche le hehe de mes recherches.

RECHERCHES ET CODAGES D'OCCURRENCES

Comme vous avez dû le comprendre, la compression est basée sur la simple remarque que tout fichier n'est qu'une suite d'octets, agences plus ou moins de la même manière, en suites a peu prés similaires d'octets a 256 près identiques. En clair, sur une zone de 257 octets, il y a de grandes chances qu'il existe au moins et dans le pire des cas deux fois le même octet. A la base, cela n'avance pas beaucoup de compresser ce genre de fichier mais si ces 257 octets forment un texte, le ratio de compression sera plus qu' étonnant. Faites l'essai. Ecrivez une lettre a votre petit(e) ami(e) et regardez dans celle-ci le nombre de répétitions de chaînes identiques, ou encore les différences de fréquence d'apparition de caractères. Si votre langage se transforme en machine, la cohérence voudra que le même phénomène se produise, forçant des répétitions logiques (comme des mots reviennent souvent, des instructions font de même, un micro processeur raconte un peu toujours les mêmes choses). A quoi bon se gratter la tête plus longtemps, sachez d'ores et déjà qu'il existe deux grandes écoles dans la compression: la recherche d'occurrences de chaînes contre la contemplation des répétitions d'octets. L'un dans l'autre, les deux méthodes se valent. A vous de choisir celle qui vous siéra le mieux. Elles se nomment respectivement Lempel et Huffmann. Savoir cela est une bien mince affaire au regard de l'exploitation de cette idée enfantine. C'est ici que les grands cerveaux font des prouesses.

LEMPEL OU LES MOTS QUI REVIENNENT

L'idée première de Lempel est que des suites identiques ont des chances de se reproduire souvent dans un programme. En ce sens, il imagina de stocker chaque mot rencontre dans un dictionnaire et d'en noter le point d'entrée. Les données compressées ne seraient ainsi non pas des chaînes mais un symbole représentant celles-ci. Cette méthode n'est pas très au point car elle signifie que le compresseur ainsi que le décompresseur doivent disposer du même dictionnaire qui serait de taille relativement importante. De plus, il faudrait disposer de différents dictionnaires selon les types de fichiers a traiter. Dieu que le problème est complique lorsqu'on nage dedans (Krom, passe-moi une bouée). C'est ici que le génie frappa. Il se dit : « Comme il n'est pas possible de savoir quel dictionnaire utiliser et qu'il n'est de plus pas raisonnable d'en stocker autant qu'il en .faudrait, pourquoi ne pas en générer un pour chaque opération? » C'est ce qu'il mit au point. A chaque compression, un dictionnaire est crée au fur et a mesure de la lecture des données. De ce fait, le dictionnaire colle parfaitement a l'objet a encoder (puisqu'il est fait a partir de celui-ci). Je suis franchement désole du nombre de répétitions du mot dictionnaire. Jusqu'ici, le procède est simple. Encore faut-il trouver la bonne méthode de création.

Ce principe est assez étrange mais au demeurant fort efficace. Avant tout, voyons de quoi no us avons besoin pour travailler :

1 - Un tableau virtuel de 4096 chaînes dont les 256 premières sont les codes ASCII des 256 premiers caractères (0 a 255). Le code 256 signifie fin des données et 257 ordonne la remise a zéro du dictionnaire. La prochaine entrée et première du dictionnaire sera donc 258. Lorsqu'on dit virtuel, cela signifie qu'il n'est pas nécessaire de garder le tableau en mémoire dans sa totalité. En effet, les 258 premières entrées n'ont pas besoin d'y figurer, par exemple. De plus, toutes les chaînes peuvent être codées pour ne pas tenir en mémoire dans leur intégralité. Comme nous le verrons, chaque entrée implantée dans le dictionnaire est relative a une précédente, existant déjà; ce qui permet son codage sous la forme d'un caractère suivi d'un pointeur sur l'entrée a laquelle elle se refere.

2 - Toute écriture dans le fichier compresse se fera sous un nombre de bits étrange mais efficace. En l'occurrence, les premières seront sur neuf bits (normal, puisqu'il faut pouvoir intégrer la valeur 256). Tant que la taille du dictionnaire n'excède pas 512 entrées (de 0 a 511), seuls neuf bits sont encore suffisants mais a la cinq cent treizième, il faudra ne plus envoyer 9 bits sur le flux de sortie mais 10, jusqu'a 1024 entrées, ou il faudra passer en 11 bits jusqu'a 2048, ou nous serons en 12 bits, ceci indepassablement. Lorsque le dictionnaire sera rempli, il sera temps de juger, selon les rations de compression, s'il vaut la peine de reprendre un nouveau dictionnaire ou bien si la première partie du fichier était significative.

Voici maintenant l'algorithme :

100 Rem La compression selon Lempel.
110 Lus$=premier caractère.
120 Tant que le fichier n'est pas vide.
130 Latent=caractère suivant.
140 Temp$=Lus$+Latent$
150 Si Temp$ existe dans le dictionnaire alors
160 Lus$=Temp$
170 Sinon
180 Ecris l'adresse de Lus$
190 Ajoute Temp$ au dictionnaire
200 Lus$=Latent$
210 Fin du Si
220 Fin du Tant que

Com me vous le voyez, la compression n'est pas franchement voyante. On peut même dire que cet algorithme a quelque chose de prenant au niveau du chou. Avec un programme comme celui-la, pas la peine de mettre de protection. Il est complètement incompressibilité tout seul. Passons, avant de reprendre nos esprits, a la partie du programme chargée de gérer les chaînes. Pour ceux qui connaissent les Hash-codes, ce sera du tout cuit. Pour les autres, nous prierons très fort. Il faut dire que la compression est une des disciplines informatiques les plus élevées, avancées, performantes et développes. Que dire de ce genre de travail si ce n'est qu'il faut se plier a elle, sans quoi vous ne passerez pas.

LA COMPRESSION PAS PRESSEE

J'espère que vous n'étés pas a la bourre car ce genre d'article va nous prendre plus d'un mois. Je vous travaille un petit programme en attendant la decompression et le listing dans deux mois. Essayez tout de même d'imaginer l'algorithme de decompression. Ici, nous développons les petits génies.

Sans bouillir, Sined, ACPC n°41, nov-dec 91, p44-45

Page précédente : Bidouilles ACPC n°40 - Gestion d'erreurs des routines disques

CPCrulez[Content Management System] v8.7-desktop/cache
Page créée en 095 millisecondes et consultée 1060 fois

L'Amstrad CPC est une machine 8 bits à base d'un Z80 à 4MHz. Le premier de la gamme fut le CPC 464 en 1984, équipé d'un lecteur de cassettes intégré il se plaçait en concurrent  du Commodore C64 beaucoup plus compliqué à utiliser et plus cher. Ce fut un réel succès et sorti cette même années le CPC 664 équipé d'un lecteur de disquettes trois pouces intégré. Sa vie fut de courte durée puisqu'en 1985 il fut remplacé par le CPC 6128 qui était plus compact, plus soigné et surtout qui avait 128Ko de RAM au lieu de 64Ko.