Obligement - L'Amiga au maximum

Dimanche 19 novembre 2017 - 20:34  

Translate

En De Nl Nl
Es Pt It Nl


Rubriques

 · Accueil
 · A Propos
 · Articles
 · Galeries
 · Glossaire
 · Hit Parade
 · Liens
 · Liste jeux Amiga
 · Quizz
 · Téléchargements
 · Trucs et astuces


Articles

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

 · Articles in english
 · Articles in other languages


Twitter

Suivez-nous sur Twitter




Liens

 · Sites de téléchargements
 · Associations
 · Pages Personnelles
 · Moteurs de recherche
 · Pages de liens
 · Constructeurs matériels
 · Matériel
 · Autres sites de matériel
 · Réparateurs
 · Revendeurs
 · Presse et médias
 · Programmation
 · Développeurs logiciels
 · Logiciels
 · Développeurs de jeux
 · Jeux
 · Autres sites de jeux
 · Scène démo
 · Divers
 · Informatique générale


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


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


Partenaires

Annuaire Amiga

Amedia Computer

Relec

Hit Parade


Contact

David Brunet

Courriel

 


Dossier : Le compactage de données sur Amiga
(Article écrit par Xavier Leclercq et extrait d'A-News (Amiga News) - juin 1990)


Introduction : raisons d'être de la compression et avantages apportés

Combien de fois n'avez-vous pas eu la désagréable surprise de constater que votre disquette est pleine ("full") ? Pour vous guérir de cette frustration ne pourrait-on pas, tout en gardant le même nombre de données, en réduire la taille ? La solution c'est la compression (ou compactage) de données. Ce compactage (en anglais "crunching") doit obéir à quelques règles pour être utilisable :
  • Le temps de décompactage doit être le plus court possible de telle sorte que le temps de chargement du nouveau programme ajouté au temps de décompactage ne dépasse pas le temps pris par le chargement de l'ancien programme (ce n'est pas toujours vrai).
  • Le chiffre de valeur, c'est-à-dire le rapport entre la longueur des données comprimées et la longueur des données initiales, doit être inférieur à 1.
Mais pourquoi s'amuser à compacter des fichiers ? Outre le fait déjà cité du gain de place sur disquette et le gain de temps parfois réalisé au chargement, on peut citer :
  • Le cri de soulagement du porte-monnaie lors de transmissions de données sur les réseaux.
  • Un moyen efficace de "coder" des données importantes que vous voulez cacher à d'autres...
Il existe de nombreuses méthodes de compression de données : suppression des répétitions, compression diatomique, par demi-octet, méthode dite de "Huffman", etc. Toutes ne sont pas d'efficacité égale car elles dépendent de la nature des informations composant ces fichiers de données. Tel algorithme utilisé pour réduire la taille d'un fichier de données graphique ne sera pas utilisable pour réduire la taille d'un fichier de textes. La plupart des traitements de texte permettent une sauvegarde en ASCII et si cette dernière n'est pas utilisée le fichier sera alors compacté selon une méthode qui tiendra compte par exemple de la fréquence de certaines lettres dans la langue utilisée...

Sans doute avez-vous déjà constaté que pour deux images de même résolution graphique les longueurs des fichiers sauvés seront différents. Pourquoi ? Parce que le format utilisé est ici le format IFF ("Interchange File Format"). Ce format utilise une méthode de compression qui lui est particulier pour réduire la taille des fichiers de données graphique. Cette méthode développée par la société Electronic Arts est la première que nous examinerons ensemble, c'est une méthode de suppression des répétitions.

Compression par suppression des répétitions

Prenons pour exemple une image réalisée en 320x200 en monochrome. La première ligne de cette image "étant vide de points", c'est-à-dire notée comme étant une succession de zéros dans l'unique "bitplane" qui forme cette image à l'écran. Pour cette ligne, il y a 320 successions de bits à zéro. Donc 40 octets dont la valeur est zéro se suivent en mémoire. Cette séquence de répétitions du nombre 0 peut-être remplacée par un compteur dont la valeur est 40 suivie de la valeur de remplissage qui est ici 0. Au lieu d'avoir 40 informations, il n'y en a plus que deux mais évidemment si les valeurs qui suivent sont par exemple 24 et 32, la valeur 24 ne peut être réduite car elle ne se répète pas.

Il faudrait donc trouver un moyen pour déterminer s'il y a compactage ou non. Par exemple une valeur strictement supérieure à 128 pourrait indiquer qu'il y a compactage et une valeur inférieure à 128 qu'il n'y a pas compactage. De plus, cette valeur serait également un compteur pour connaître le nombre d'octet compacté ou non.

Exemple, la séquence 164/000/001/004 : 164 étant supérieur à 128, le compteur est ici 93 (257-164) et la valeur de remplissage est 0, puis comme 1 est inférieur à 128, il y a une fois la valeur 4. Les informations décompactées sont 93 fois 0 puis le nombre 4. Le nombre minimum du compteur d'informations compactées doit être égal à 1, ce qui fait deux valeurs de remplissage (0 et 1). C'est pour cette raison qu'il faut soustraire le compteur à 257 et non à 256.

C'est en gros la méthode de compactage ByteRun1 (CmpByteRun1) employée pour certains fichiers IFF compactés. Le fichier IFF peut être compacté suivant différentes méthodes ou bien ne pas être compacté du tout. C'est l'attribut "Compress" (14e attribut, ou "byte" du BMHD (BitMapHeader)) qui donne cette information.

Pour illustrer ce qui a été dit sur la méthode de suppression des répétitions, je vous propose un petit programme en assembleur permettant de décompacter un fichier IFF. L'image est décompactée et la table des couleurs est construite (32 couleurs par défaut).

Cette routine peut être utilisée pour programmer des intros par exemple. Il n'y a alors plus besoin de passer par un utilitaire pour créer des fichiers ".RAW" (fichier brut de données). Si par défaut vous ne connaissez pas la taille et la résolution de l'image (pour être insérée dans la liste Copper) vous pouvez rechercher ces informations dans le fichier IFF (20me attribut : Width.w, Height.w, Depth.w, etc.).

Compactage de données sur Amiga
Compactage de données sur Amiga

Huffman

Nous allons maintenant aborder ensemble une technique statistique de compression de données. C'est un mathématicien qui a laissé son nom à cette méthode : Huffman. C'est une méthode bien connue mais malheureusement une des plus difficiles à mettre en oeuvre. Pour bien comprendre la suite des évènements concentrons-nous sur quelques notions de base.

Un fichier de données contient un texte en ASCII. Ce fichier est donc garni d'informations, c'est-à-dire de codes ASCII qui sont associés à une lettre de l'alphabet. L'information est donc composée d'un contenu sémantique (la lettre "A" ) et d'un contenu quantitatif (65 en ASCII). Ce contenu quantitatif est une valeur particulière du fichier que l'on appelle "occurrence". Toutes les occurrences de ce fichier forment un ensemble de données que l'on appelle "entité". A chaque occurrence de l'entité on peut associer une lettre de l'alphabet. Il peut y avoir redondance d'occurrences dans l'entité (cela signifie qu'une lettre peut se répéter plusieurs fois dans le fichier).

Après avoir parcouru entièrement le fichier séquentiellement, on peut déterminer la "fréquence" absolue des répétitions de chaque occurrence. La lettre "E", qui est généralement la plus fréquente, peut se répéter 130 fois dans le fichier et donc sa fréquence absolue est de 130. En connaissant le nombre total d'occurrences de l'entité (N octets) nous pouvons maintenant déterminer la "probabilité" de chaque lettre rencontrées. Il suffit de diviser la fréquence absolue par "N" (N étant donc dans la plupart des cas la taille du fichier de données).

Pour notre lettre "E", ayant une fréquence absolue de 130 dans un fichier totalisant 1000 occurrences, sa probabilité qui lui est associée est 0,13. Je vous rappelle que la méthode Huffman de compactage est une méthode statistique. Voilà pourquoi ces préliminaires sont indispensables. Ce qui m'amène à vous dévoiler le principe de base du compacteur Huffman : chaque occurrence sera codée selon la probabilité (la chance) de rencontre de cette occurrence dans le fichier.

Normalement, chaque occurrence de notre fichier texte est codée sur 8 bits, ce qui donne bien un octet, qui associée à son code ASCII représente une lettre de l'alphabet. Huffman nous propose de coder cette occurrence sur une longueur binaire variable. Cette variabilité étant strictement proportionnelle à la probabilité qui est associée à chaque lettre de l'alphabet de notre fichier texte.

L'occurrence 69 (ASCII), qui est associée à la lettre "E", et dont la probabilité est de 0,13 dans notre fichier texte de 1000 octets, qui se code habituellement sur un octet (longueur binaire de 8 bits), se codera selon Huffman sur une longueur binaire inférieure à 8 bits. D'où gain pour cette occurrence et donc compression.

Peut-on savoir à l'avance sur quelle longueur binaire va se coder l'occurrence ? Oui évidemment, sinon je n'aurais pas posé la question... Le nombre de bits (NBBITS) nécessaires au codage d'une occurrence se calcule selon la formule suivante :

NBBITS = ceil (-LOG PROBA)

Avec :
  • PROBA : la probabilité de cette occurrence.
  • LOG : le log en base 2.
  • ceil : une fonction qui rend le nombre le plus proche ou égal à -LOG PROBA.
La lettre "E" prise comme exemple peut se coder sur une longueur binaire de trois bits (3 = ceil (-LOG 0,13) = ceil (2,94)). A titre d'information, le gars qui a pondu cette formule s'appelle Peterson. Si on associe à chaque occurrence un codage de longueur binaire variable, le codage de Huffman est le plus optimum que l'on puisse réaliser. En d'autre mot : il n'y a pas moyen de faire mieux.

Un truc, l'entropie

Je dois aborder une dernière notion avant d'attaquer la pratique de la chose. Il existe en effet un truc pour savoir à l'avance le nombre d'octets moyen qu'il faudra utiliser pour chaque occurrence. Cette notion mathématique, qui n'est pas sans parenté avec la formule de Peterson, est appelée "entropie". La formule est :

ENTROP = - (la somme de tous les (PROBA * log PROBA))

Avec :
  • log : toujours en base 2.
  • PROBA : la probabilité pour chaque occurrence du fichier.
L'entropie est une moyenne de bits qu'il faudra utiliser pour codifier les octets. Attention, cette valeur n'est pas exactement le chiffre que donnera la réalité de la pratique mais l'entropie s'en approchera très fort. "Cela sert à quoi ?" me répliquez-vous immédiatement avec la rapidité d'esprit qui vous caractérise... Simplement, si vous avez le choix entre plusieurs méthodes de compression, à déterminer la plus optimisée. Je vous rappelle que le chiffre de valeur (c'est-à-dire "l'efficacité") du compresseur est directement fonction de la nature des informations à compresser.

L'entropie n'échappe pas à cette règle de la nature des données. L'entropie d'un fichier graphique sera sans doute plus élevée que celle d'un fichier texte. L'entropie vous dévoile à l'avance le volume du fichier qui sera généré par le compresseur, du moins si le fichier est assez volumineux pour rendre négligeable la table qui contiendra le code binaire variable selon l'occurrence. Le calcul de ce volume est simple, il suffit de multiplier l'entropie par "N" (N : le nombre total d'occurrence du fichier). Si l'entropie d'un fichier de 100 koctets est de 6,42, cela signifie que la taille du fichier cible est d'au minimum (minimum pour la raison citée plus haut) de 64,2 koctets.

Résumons

Si le gain que nous pouvons espérer, en connaissant l'entropie du fichier, est convenable (au sens strict si le chiffre de valeur est inférieur à 1) alors nous pouvons envisager la compression. Il faudra d'abord associer à chaque occurrence une probabilité (PROBA) puis créer une table de ces probabilités classées par ordre croissant.

Avec cette table nous allons créer ce que l'on appelle "l'arbre" de Huffman. Nous allons reprendre pour illustrer cette construction le fichier texte. La probabilité de la lettre "E" est de 0,13, la lettre "T" de 0,09, etc. Les lettres sont placées à gauche de l'arbre, classées par ordre croissant de probabilité. En débutant par le bas de la table, une ligne (appelée "branche") est tracée partant de chaque lettre. Les deux branches dont les probabilités sont les plus faibles (et les plus proches) sont reliées entre elles pour former un noeud qui aura désormais une probabilité cumulée (la première PROBA + la deuxième PROBA des deux branches).

A chaque noeud partira une nouvelle branche dont la probabilité cumulée sera reliée à nouveau à la probabilité la plus faible que l'on peut lui associer. Et ainsi de suite jusqu'à enfin obtenir la probabilité de rencontre de toutes les occurrences, c'est-à-dire 1.

Cet arbre construit afin d'obtenir les codes Huffman, de longueur binaire variable et associés à chaque occurrence de l'entité, nous devons attribuer les nombres 0 et 1 aux branches de chaque noeud. On partira du dernier noeud (de probabilité cumulée 1) situé le plus à droite de la table vers les noeuds situés le plus à gauche. A chaque, branche est donc associé 0 ou 1. En relevant la séquence binaire de droite à gauche, le code obtenu est le code Huffman qui sera utilisé pour codifier chaque occurrence.

Deux remarques
  • Le code Huffman obtenu est unique. On ne peut trouver un code 001 s'il existe déjà un code 000 ("E") car les deux premiers bits sont communs.
  • Le code Huffman est de longueur binaire variable : "E" a le code 000 et la lettre "Z" le code Huffman 1111111.
Une table de ces codes Huffman devra se trouver avec les données compressées. Ce décodage sera automatique et presque instantané. Chaque code Huffman étant unique, le fichier sera décodé séquentiellement. Remarquons qu'une lettre qui a une probabilité très faible prendra un grand nombre de bits. A la limite, l'on peut imaginer une occurrence qui n'existe qu'une seule fois dans l'entité...

Pour palier à ce problème de longueurs binaires démesurées (supérieur à 16 bits), il est envisageable de prévoir (comme dans la compression par suppression des répétitions) un "header", c'est-à-dire une valeur particulière qui signalera qu'il y a compression ou pas. Cette manière de procéder est utilisée pour les télécopieuses. On parle de codes Huffman modifiés.

Construire un arbre

Si l'octet initial est de longueur fixe (8 bits), le code Huffman qui lui sera associé est de longueur binaire variable. Cette variabilité est proportionnelle à la probabilité d'apparition de chaque octet (il y a 256 octets différents). Si l'octet 0 se retrouve 500 fois au total d'un fichier dont le volume de données est de 1000 octets la probabilité qui est directement associée à l'octet 0 est 0,5. Sachant cela, il faut alors construire l'arbre de Huffman comme expliqué dans la partie précédente de cet article.

Il nous faut maintenant déterminer la logique la plus simple possible pour trouver ces codes. Une fois l'algorithme trouvé, le reste est une simple affaire de traduction dans un langage évolué ou en assembleur. Nous allons procéder en utilisant une structure et des pointeurs.

Intuitivement, un arbre est une collection d'informations homogènes organisées en niveaux. Chaque information d'un niveau donné peut se ramener à plusieurs informations de niveau inférieur par des branches ne formant pas de boucle. Si une boucle existe on parle alors de "graphe".

Un arbre est composé soit d'un élément appelé racine soit d'un élément vide (NIL) et d'un ensemble fini de taille variable d'arbres appelés "sous-arbres". L'important est que l'on puisse transformer tout arbre en un "arbre binaire". Un arbre binaire est soit vide soit formé d'une racine et de deux sous-arbres : un SAG sous-arbre de gauche et un SAD sous arbre de droite.

Le problème pour construire l'arbre de Huffman peut se résoudre plus facilement en reconstruisant pour chaque noeud une structure binaire.

Première étape : écriture de l'arbre binaire

L'algo tient compte des 26 lettres de l'alphabet de notre arbre de Huffman construit dans la précédente partie. Évidemment pour n'importe quel type de données, il suffit de changer le nombre d'éléments... Le signe "&xx" représente "je pointe sur xx". L'abréviation "NIL" signifie "Je pointe sur un élément vide".

Chaque probabilité cumulée formera une nouvelle structure qui pointera soit vers NIL (vide) soit vers un SAG ou SAD.

Deuxième étape : écriture des codes dans un vecteur d'après la lecture de l'arbre

En fait, cette deuxième étape peut se résumer ainsi : compter le nombre de noeuds pour atteindre la feuille, inverser le code...

J'ai brulé une quantité effrayante de calories pour cogiter ce qui précède, la chose n'est pas aisée surtout, faut-il le souligner, à cause de l'absence totale de documentation. Je vous lance donc la base de l'algo, les fondations, à vous de finir les murs et corriger les éventuelles bogues du raisonnement.

L'auteur de PowerPeak, Nico François, en réponse à une lettre à propos de laquelle je lui demandais de l'aide, m'a répondu qu'il n'avait jamais utilisé Huffman et qu'il était toujours à la recherche d'un algo valable à ce sujet... Conclusion : bon courage...

Compactage de données sur Amiga
La structure "Pointeur Actuel"

Compactage de données sur Amiga
Écriture des codes dans un vecteur


[Retour en haut] / [Retour aux articles]