> Algorithmie
PrograZine issue #9 - http://www.citeweb.net/discase/9/COMPRESS.htm Edito Sommaire Contribution Contacts


Introduction générale à la compression de données
par MB - m_b@infonie.fr
Tous Tous Tous





     Salut tout le monde. Je vais commencer par vous présenter brièvement les différentes méthodes de compression, domaine qui peut paraître (et il y a de quoi) pour certain un peu mystérieux.
>1. Présentation.

     Tout le but de la compression, vous vous en doutez, est de réduire la taille d'un fichier. Plusieurs méthodes s'offrent alors à nous. Je ne parlerais ici que des méthodes dites non destructives : aucune donnée n'est perdue. En effet, des méthodes destructives existent (comme par exemple le GIF) mais elles ne sont utilisées que dans de rares domaines comme le son ou le graphisme et ne nous intéressent donc pas vraiment pour l'instant.
>2. Le Run Length Encoding.

     L'une des méthodes les plus simples, et basiques, est le Run Length Encoding (RLE). Le principe est très simple, lorsque plusieurs caractères identiques se suivent dans un fichier, plutôt que de tous les écrire, on en écrit un puis on indique le nombre de fois qu'il doit être répété. On obtient donc par exemple :
Avant compression : 	05 05 05 12 12 11 15 15 15 15
Arès compression :   	05 03 12 02 11 01 15 04
l

     On obtient donc une réduction de la taille du fichier. Plusieurs variantes existent, et ceci n'est pas (je crois) la description officielle du RLE, mais c'est le principe qui est important.
l Ce qu'on remarque, c'est que cette méthode n'est valable que lorsqu'un grand nombre d'octets identiques se suivent, sinon, elle a pour effet d'augmenter la taille du fichier, ce qui n'était pas le but recherché ! En effet, si on a la suite d'octets :
Avant compression :	10 10 15 06 80 90 15 12
Après compression :	10 02 15 01 06 01 80 01 90 01 15 01 12 01
l
On voit tout de suite que ce n'est pas rentable ! C'est pourquoi cette technique n'est appliquée que (ou presque) dans le graphisme. C 'est dans cette discipline que les conditions sont remplies pour avoir un bon tau de compression. En effet, dans une image, c'est très souvent que des octets identiques se suivent. Le format BMP et PCX sont basés sur cette technique, avec chacun ses propres variantes.
>3. Méthodes avancées.

     Pour avoir une bonne compression sur tout les types de fichiers : texte, exécutable, données diverses, on utilise d'autres méthodes. Elles ont toutes le même principe, mais utilisent des techniques différentes. Ce principe est de coder les caractères les plus utilisés dans le fichier sur un minimum de bits, et les plus utilisés sur plus de bits. En effet, on ne parle plus maintenant de bytes (octets) mais de bits. C'est toute la nuance. Si on considère un fichier texte, pour simplifier la compréhension, tous les caractères sont codés suivant la norme ASCII, donc de 0 à 255 :
   le ' a ' = 97
   le ' b ' = 98
   etc. ...
l

     Chaque caractère est donc codé sur huit bits. Si on peut coder les caractères les plus utilisés dans le fichier sur moins de 8 bits, on gagnerait de la place, d'autant plus que le codage utilisé sera petit. On utilise donc ce que l'on appelle un dictionnaire qui sera placé au début du fichier compressé et qui donnera le codage utilisé pour chaques caractères, afin de pouvoir décompresser le fichier. Evidemment, ce dictionnaire varie d'un fichier compressé à un autre et dépend aussi de la technique de compression.
>3.1. Méthode de Huffman.

     La méthode de base est nommée la méthode de Huffman (du nom du gars qui l'a trouvée je suppose :) ). Cette méthode est toujours très utilisée, notamment dans le format Zip, ainsi que lors de la dernière phase de compression du MP3. Bien sur, une fois encore, en étant légèrement modifiée. Le principe est simple, avec tout de fois des subtilités.
    
    Au départ, on lit entièrement le fichier que l'on veut compresser et on compte le nombre d'occurrence de chaques caractères. On obtient donc une table d'occurrence dont on va se servir pour coder les caractères. On attribuera au caractère le plus utilisé un code binaire très petit, et au caractère le plus utilisé un code plus grand. La longueur de ces codes dépendra du nombre de caractères différents ainsi que du nombre d'occurrence de chacun d'entre eux, mais on se retrouve en général avec le caractère le plus utilisé codé sur 3 ou 4 bits. Ce code augmente pour se retrouver à beaucoup plus pour le caractère le moins utilisé. La longueur maximale du code dépend du nombre de caractères différents. Si on considère un fichier texte, il y en aura au maximum 256. On peut donc se retrouver avec un code maximum de 256 bits, mais ceci est très rare. On se rend donc compte que des caractères sont compressés, et d'autres au contraire sont " expansés ". Mais puisque les caractères dont le code est le plus long sont très peu utilisés, on gagne de la place. Cette méthode est très efficace lorsque des caractères similaires apparaissent souvent dans un fichier. C'est le cas dans un fichier texte : les lettres 'E' ou 'A' sont beaucoup plus utilisées que les lettres 'W' ou 'Z'. C'est donc un domaine de prédilection pour cette méthode. Par contre, elle n'est que très peu efficace pour les exécutables où aucun caractère ne se démarque plus qu'un autre.
>3.2 La méthode LZW.

     D'autres algorithmiciens (?) se sont donc penchés sur la question. On en a retenue une (entre autre) mise au point par Lempel Ziv et Welch, ce qui est devenu le LZW. Plusieurs variantes existent (LZ, etc.) mais elles utilisent toutes le même principe. Au lieu de regarder un fichier caractère par caractère comme pour Huffman, on le regarde " syllabe par syllabe ". On le regarde par groupe de 2 ou 3 caractères et on en déduit un tableau de codes de la même manière que pour Huffman. On ne code donc plus des caractères mais des syllabes entières.

    Evidemment, cette technique est un peu plus compliquée à comprendre et à implémenter, mais elle est souvent plus rentable. Dans un fichier texte par exemple, on se rend compte que les lettres sont souvent groupées. Par exemple, derrière la lettre 'q', on à de fortes chances de trouver un 'u'. Ce groupe de 2 lettres, normalement codé sur 16 bits pourra se retrouver codé sur 6 ou 8 bits, d'où un excellent gain. De même dans un exécutable, l'instruction 'add' est souvent suivie de 'ax', pareil pour 'sub'. On obtient donc aussi une bonne compression sur les exécutables, point faible de la méthode de Huffman.

    L'intérêt de la méthode LZW est que l'on peut régler le nombre de caractères formants notre " syllabe ". On s'est rendu compte d'une manière plutôt empirique que le meilleur rendement est obtenu pour 3 caractères par syllabes, mais il n'en tient qu'à vous de le modifier selon vos besoins. Le LZW et la méthode que l'on retrouve dans le RAR, dont les résultats sont souvent meilleurs, vous l'aurez remarqué, que le ZIP. Mais il y a une contrepartie : c'est beaucoup plus lent. Le tau et le temps de compression sont donc 2 critères dont il faut tenir compte.
>3.3. L'AFE.

     Un des inconvénients de ces 2 techniques est que l'on ne peut pas faire de compression en temps réel (c'est possible avec le RLE, mais ses résultats ne sont pas assez satisfaisants). En effet, avec Huffman ou le LZW, il est impératif de lire le fichier entièrement avant de commencer à le compresser. On a donc trouvé une autre méthode, l'AFE (Adapting Frequencies Encoding).

    C'est en fait le même principe que la méthode de Huffman, mais le dictionnaire varie au fur et à mesure de la compression. En effet, on commence avec un dictionnaire basé sur le code ASCII, et lorsqu'un caractère doit être compressé, sa place remonte dans la table d'occurrence. Son code diminue donc, de la même manière que pour Huffman. On lit le caractère suivant, et de même sa place dans la table d'occurrence remonte et son code diminue. Plus long est le débit d'information et meilleure est donc la compression. Mais cette méthode est tout de même assez compliquée à implémenter, notamment pour la décompression qui doit procéder de la même manière. On commence avec un dictionnaire suivant la table ASCII et on modifie ce dictionnaire au fur et à mesure de la décompression.
>3.4. La méthode Teuhola-Raïta.

     Cette méthode utilise la même constatation que la méthode LZW, mais l'exploite d'une autre manière. C'est en fait une méthode avec prédiction. En effet, puisque des lettres sont souvent groupées, si on reprend notre exemple, un " q " sera quasi certainement suivi d'un " u ". Donc si dans le fichier que l'on veut compressé on rencontre un " q " suivi d'un " u ", on ne marquera pas ce " u ". C'est en gros ce principe qui est appliqué. On compresse un peu suivant la méthode LZW : on repère dans un dictionnaire les syllabes, et lorsque l'on compresse, si on repère une lettre débutant une des syllabes repérées, on écrit cette lettre, mais pas les autres qui forment le reste de la syllabes
    En effet, ce n'est pas la peine car on est sûr que si l'on rencontre cette lettre, elle sera suivit des autres qui formeront la syllabes. Evidemment, il arrive qu'une lettre débute plusieurs syllabes différentes. Dans ce cas, on écrit les premières lettres jusqu'à ce qu'il n'y ai plus de confusion possible entre les différentes syllabes.

    Cette méthode n'est pas du tout évidente à implémenter et même à comprendre ! C'est pourquoi elle est très peu employée. De plus, le tau de compression dépend énormément du nombre de lettres formant une syllabe. Les meilleurs résultats sont obtenus au alentours de 3,4 ou 5, cela dépend du fichier et du contenu de ce fichier. La compression est donc un peu trop aléatoire.
>4. Conclusion.

     Il existe bien sûr d'autres méthodes, souvent spécifiques à un domaine, comme le MP3 pour la musique, le JPEG pour le graphisme ou le MPEG pour la vidéo. Mais les méthodes abordées plus haut sont vraiment basiques et couvrent tous ou presque tous les domaines de l'informatique. Ceci n'est bien sûr qu'une brève description générale afin de vous expliquer un peu la compression de données, sujet toujours d'actualité, notamment avec Internet où le téléchargement reste un problème.

    Ce descriptif n'est bien sûr pas exhaustif et je n'ai pas la prétention d'affirmer que toutes ces informations sont exemptes d'erreurs. En ce sens, je ne pourrais pas être tenu responsable de pertes de données suite à la lecture de cet article, etc., etc.

     Si vous avez la moindre question à propos de cet article, un point que vous n'auriez pas compris ou si vous voulez en savoir plus, ou plus vraisemblablement pour me signaler des erreurs, n'hésitez pas à écrire. De même, si vous trouvez cet article très instructif, laissez un petit message, ça fait toujours plaisir !
Cet article est la propriété de MB. La copie et la diffusion sont libres sauf dans un but lucratif sans accord explicite de l'auteur.