Les algorithmes de compression - Partie 1 - La théorie

Tutoriel réalisé par Faiseur

Niveau: [ Intermédiaire ]

INTRODUCTION

Ce tutoriel est articulé en trois parties:

Partie 1: Un peu de théorie sur les algorithmes de compression.

Partie 2: Nous allons passer en revue quatre librairies gratuites de compression en voyant comment s'en servir dans nos programmes en assembleur.

Partie 3: Un complément pour comprendre comment coder un programme qui extrait une ressource compressée, la décompresse en mémoire puis l'utilise.

HISTORIQUE

Cette première partie va survoler la théorie des algorithmes de compression. Vous pouvez tout à fait sauter cette étape et vous attaquer à la pratique. Auquel cas rendez-vous dans la deuxième partie de ce tutoriel.

Je reprend ici un article de Cvb que j'ai commenté par quelques ajouts, corrigé en orthographe et remodelé pour en faire une synthèse plus courte du sujet.

LES PLUS CONNUS SE RESSEMBLENT

Ce tableau récapitulatif montre les systèmes de codage utilisés par deux applications parmi les plus connues, 7-Zip et Rar:

Pourquoi pas un comparatif entre ZIP et RAR ? ZIP et RAR utilisent les mêmes algorithmes à peu de choses près. De plus 7-zip permet de créer des fichiers ZIP, tout comme Winrar.

Nous pouvons déjà constater deux choses:

- Ces applications utilisent plusieurs systèmes de codage

- Il s'agit (sauf pour un cas) des mêmes systèmes de codage

C'est pourquoi il sera instructif de survoler un explicatif des algorithmes communs - ils ne sont pas si nombreux - à toutes ces applications de compression.

LES SYSTEMES DE CODAGE

Les algorithmes ZIP et RAR utilisent des systèmes de codage crées par de chercheurs et mathématiciens. Nous allons passer en revue l'historique, la théorie, l'’application et une conclusion succincte des quatre systèmes de codage suivant : LZ77, LZMA, BWI, HUFFMAN. Il s'agit des systèmes utilisés dans les applications de compression les plus connues.

SYSTEME DE CODAGE HUFFMAN

Fichier ZIP : Oui

Fichier RAR : Non

Historique:

L’'algorithme de Huffmann a été décrit pour la première fois en 1952. Il crée des codes de longueurs variables en fonction des probabilités fournies par le modèle, ou la connaissance de la séquence complète. La méthode de compression Huffman consiste à diminuer au maximum le nombre de bits utilisés pour coder un fragment d’'information.

L’'algorithme de Huffman se base sur la fréquence d'’apparition d’'un fragment pour le coder : plus un fragment est fréquent, moins on utilisera de bits pour le coder. Prenons l’'exemple d’'un fichier texte : le fragment d'’information sera un caractère ou une suite de caractères. Nous pourrions remarquer que les voyelles sont beaucoup plus fréquentes dans notre fichier texte que les consonnes.

Pour pouvoir compresser puis décompresser l'’information on va donc devoir utiliser une table de fréquences et deux choix s’'offrent à nous : calculer une table et l'’intégrer au fichier ou utiliser une table générique intégrée dans la fonction de compression.

Choix 1 : La compression est meilleure. Elle nécessite le calcul d’'une table de fréquences mais le fichier sera plus important également du fait de la présence de cette table dans le fichier

Choix 2 : La compression sera plus rapide puisqu'elle n’'aura pas à calculer les fréquences. Par contre l’'efficacité de la compression sera moindre.

En résumé: Le gain obtenu par la première méthode (ratio de compression + taille de la table) peut être supérieur à celui de la deuxième (ratio de compression).

Conclusion :

Cet algorithme est gratuit, simple et efficace. Grâce à cela il est beaucoup utilisé aujourd’hui. C’est un avantage non négligeable pour une entreprise d’'avoir accès à du code libre. Il est utilisé pour le JPEG et MPEG en particulier. Malgré son ancienneté cette méthode est toujours remise au goût du jour et offre des performances appréciables. En effet, beaucoup de recherches en algorithmique ont permis d'améliorer les fonctionnalités de la méthode Huffman de base, par exemple les arbres binaires, les arbres équilibrés, etc.

SYSTEME DE CODAGE LZ77

Fichier ZIP : Oui

Fichier RAR : Oui

Historique des algorithmes LZ :

En 1977 Jacob Ziv et Abraham Lempel fournissent une technique de compression différente de l’'algorithme de Huffman, capable de donner de meilleurs taux de compression. Ils mettent ainsi en place l’algorithme LZ77. Puis vient LZSS, version améliorée de LZ77 par Storer et Szymanski puisque la recherche des séquences dans le dictionnaire est réduite logarithmiquement. Enfin vient l’'algorithme LZ78, plus connu sous le nom LZW, amélioration faite par Terry Welch en 1984 de LZSS de par le fait que les séquences sont rangées dans une arborescence. Il porte le nom de ses 3 inventeurs : Lempel, Ziv et Welch.

Théorie :

Le principe est fondé sur le fait qu'’une séquence de caractères peut apparaître plusieurs fois dans un fichier. L'’algorithme de compression LZ consiste à émettre à la place des séquences, les adresses de ces séquences d’'un dictionnaire généré à la volée. C’est un algorithme de compression nettement plus performant en moyenne que les algorithmes statistiques puisqu'’il permet d’'obtenir des gains plus élevés sur la majorité des fichiers. L’algorithme LZ se distingue des méthodes statistiques pour plusieurs raisons:

• Le fichier compressé ne stocke pas le dictionnaire, ce dernier est automatiquement généré lors de la décompression. Il n'’existe donc pas de table d’entête.
• Contrairement aux méthodes statistiques qui utilisent la probabilité de présence sur un ensemble de taille fixe de symboles, l’'algorithme LZ représente un algorithme d'’apprentissage, puisque les séquences répétitives de symboles sont dans un premier temps détectées puis compressées seulement lors de leurs prochaines occurrences. Le taux de compression est dépendant de la taille du fichier. Plus la taille est importante, et plus le taux de compression l’'est aussi.

Il permet le compactage à la volée, puisqu'’il n’'y a pas à lire le fichier au préalable, il compresse les séquences de symboles au fur et à mesure.

Application :

Prenons l'exemple de la chaîne suivante:

/WED/WE/WEE/WEB

Sachant qu'un caractère = 8 bits (1 octet) il faut donc 15*8 bits = 120 bits pour stocker cette chaîne en mémoire sans méthode de compression.

Compactons-la avec Lempel-Ziv.

L'algorithme nous sort le résultat suivant: /WED <256> E <260> <261> <257> B

Notons les points pertinents suivants:

- Après /WED on dépasse la valeur 255 : il faut donc utiliser 9 bits pour coder les valeurs supérieures

- Dans le résultat trouvé il ne faut plus que 4*9 + 6*8 = 84 bits pour stocker cette chaîne

Expliqué autrement:

- '/WED' est copié à l'identique (4*8 bits)

- '/W' est remplacé par la valeur 256 (9 bits)

- 'E' est copié à l'identique (8bits)

- '/WE' est remplacé par la valeur 260 (9 bits)

- 'E/' est remplacé par la valeur 261 (9 bits)

- 'WE' est remplacé par la valeur 257 (9 bits)

- 'B' est copié à l'identique (8 bits)

Variante de l’'algorithme

Il existe des variantes des compressions LZ :

• LZP : Algorithme qui se base sur la répétition de phrases entières.
• LHA, LZS, LZX, LZH : Algorithmes quasiment identiques, encore dérivés du LZ77. Il n’est employé que pour l’utilitaire Lharc, très répandu au Japon, mais de moins en moins utiliser dans le Monde.

Conclusion :

L'’algorithme LZ est aujourd’hui considéré comme la méthode de compression la plus efficace et une des plus connues. Elle est relativement rapide ; ce qui a rendu l'’utilisation de la compression possible sur les disques durs de façon transparente. Cette méthode est aussi utilisée dans le format .gif, mais encore dans les compresseurs tels que ZIP, ARJ.

La compression par dictionnaire de type LZ (TIFF,GIFF par LZ et PNG pour GIF) est très rapide mais ne compresse que peu les images de 2 à 24 bits. Elle était peu utilisée car elle était brevetée par la société Unisys j'usqu’en juillet 2004 (8 Juillet 2004) où le brevet a expiré. Par conséquent, cette dernière ne peut plus à présent réclamer des droits sur l'’utilisation du format gif par exemple car celui ci reposait sur l’'algorithme LZ.

SYSTEME DE CODAGE LZMA

Fichier ZIP : Oui

Fichier RAR : Non

Historique :

LZMA, pour Lempel-Ziv-Markov chain-Algorithm, est un algorithme de compression de données créé en 2001.

Théorie :

Il utilise une compression avec dictionnaire assez similaire au LZ77 et offre un fort taux de compression et une taille variable de dictionnaire de compression (jusqu'à 4 Go). (Voir aussi LZW)

Application :

Ses principales caractéristiques sont :

• Taux de compression élevé.
• Taille du dictionnaire variable (jusqu'à 4 Go).
• Vitesse de compression : environ 1 Mo/s sur un processeur à 2 GHz.
• Vitesse de décompression : environ 10-20 Mo/s sur un processeur à 2 GHz.
• Faible demande de mémoire pour la décompression (selon la taille du dictionnaire).
• Petite taille du code de décompression : environ 5 Ko.
• Support du multi-threading et de l'hyper-threading du P4 (plusieurs opérations).

Conclusion:

Il est utilisé dans les formats 7z du programme 7-zip et par Stuffit, Stuffit étant une famille de logiciel permettant de compresser et décompresser des archives sur les Macs.

SYSTEME DE CODAGE BWT

Fichier ZIP oui

Fichier RAR : Non

Historique:

La transformée de Burrows-Wheeler, couramment appelée BWT (pour Burrows-Wheeler Transform) est une technique de compression de données. Elle fut inventée par Michael Burrows et David Wheeler. Cette technique fut rendue publique en 1994, suite à de précédents travaux de Wheeler en 1983. Il ne s'agit pas à proprement parler d'un algorithme de compression, car aucune réduction de taille n'est effectuée, au contraire (voir ci-dessous), mais bien d'une méthode de réorganisation des données : les probabilités pour que des caractères identiques initialement éloignés les uns des autres se retrouvent côte à côte sont alors augmentées. Cette technique n'est pas très utilisée, mais l'on peut cependant remarquer qu'elle est présente dans le format bzip2 qui offre un très bon quotient de compression.

Théorie:

Comme nous l'avons dit, la transformée de Burrows-Wheeler ne compresse pas les données, elle se contente de les réorganiser de manière à obtenir un plus petit taux de compression.

Tout d'abord, la chaîne de caractères à coder doit être copiée dans un tableau carré en décalant la chaîne d'un caractère vers la droite à chaque nouvelle ligne. Ces lignes sont ensuite classées par ordre alphabétique. Nous savons que, grâce au décalage, chaque dernière lettre de chaque ligne précède la première lettre de la même ligne, sauf pour la ligne originale dont on notera la position. De plus, comme les lignes sont rangées par ordre alphabétique, on peut retrouver la première colonne du tableau grâce à la dernière colonne.

Application :

Prenons un exemple. Supposons que la chaîne à coder soit « TEXTE ». On réalise tout d'abord le tableau de 5 lignes (nombre de lettre). Il s'agit du tableau de chaîne situé à gauche. A chaque nouvelle position une lettre est décalée vers la droite.

Une fois terminé cette opération on trie le résultat par ordre alphabétique, ce qui nous donne le tableau de chaîne situé à droite.

Le texte codé qui est choisis est la dernière colonne, soit de haut en bas: « TTXEE ». Pour la décompression il est nécessaire de garder en mémoire la position de la chaîne originale, ici la position 4. Nous y ajoutons le chiffre 4, le résultat final est donc: « 4TTXEE ».

Conclusion :

Cette transformation n'apporte aucun gain de compression immédiat, au contraire, car il est nécessaire de transmettre des informations supplémentaires pour le décodage (ici le chiffre 4). Cependant, Burrows et Wheeler recommandent ensuite d'utiliser un algorithme de type MTF. Ainsi, la chaîne possédant de nombreuses répétitions de caractères (ici TT, EE) contiendra beaucoup de 0. Ceci assure avec un algorithme de type codage de Huffman un quotient de compression élevé.

SYNTHESE

• LZ : L’algorithme LZ est aujourd’hui considéré comme la méthode de compression la plus efficace et une des plus connues. Avantage : rapide.
• LZMA : Taux de compression élevé, vitesse de compression très rapide, utilise les nouvelles technologies (multithreading par exemple)
• BWT : Ce n’est pas un algorithme de compression à proprement parler. C’est une méthode pour organiser qui fonctionnera avec un algorithme ; Huffman par exemple.
• Huffman : Cet algorithme a la chance d’'être rapide en plus d’'être gratuit. Les créateurs du format JPEG l’'utilisent.

Pour ceux que ce genre de chose interesse, le site : http://www.maximumcompression.com/

On y retrouve un peu de théorie, mais surtout une base comparative de presque tous les logiciels de compressions du marché testés dans différents types d'utilisations. Attention, à prendre avec des pincettes car l'auteur ne met pas toujours à jour les différentes librairies utilisées.

On peut par exemple noter que:

1. Très bizarrement Zlib n'est pas ajouté dans la base comparative...

2. ApLib est utilisé dans sa très vieille version datant de...au mieux 2004 mais je pense encore plus ancienne (v043b, correspondant à l'exemple fournit dans Masm32). En utilisant la dernière version (2009) on gagne plusieurs koctets pour des fichiers de taille moyenne. Le ratio est donc un peu meilleur que celui affiché dans les tests.