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

Voir le sujet précédent Voir le sujet suivant Aller en bas

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

Message  faiseur le Mer 9 Juin - 17:56

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.





Dernière édition par faiseur le Mer 21 Juil - 12:28, édité 4 fois

faiseur
Admin

Messages: 390
Date d'inscription: 02/05/2010

Voir le profil de l'utilisateur http://aliasoftware.com/

Revenir en haut Aller en bas

Re: Les algorithmes de compression - partie 1 - La théorie

Message  Grincheux le Mer 9 Juin - 19:17

Très intéressant, à quand une bibliothèque "Maison" pour compresser les données ?
La théorie c'est bien, mais le concret c'est mieux.
L'approche est très intéressante.
Quels sont les algos les plus efficaces quand on compresse un fichier déjà compressé comme JPEG ou MPEG ?
Quels sont les algos qui sont le moins destructifs ?
Différence entre JPEG et JPEG2000 ?
Le futur...
Un fichier compressé puis crypté, grossit-il beaucoup ? Faut-il crypter puis compresser pour gagner en place ?
Le format SFX.
Quelle différence entre un fichier BMP zippé et un fichier JPEG ? La taille doit être sensiblement la même, par contre on doit moins perdre en qualité d'image ?
Faut-il compresser les données quand le disque est compressé ?
Les images ISO sont elles compressées ?

C'est facile de poser des questions, tu as fait un bon travail, on a encore faim.
J'ai beaucoup d'idées là dessus, car la semaine dernière j'ai téléchargé des bibliothèques de compression comme
ZLib, UnRar, Lha, GZip, BZip et Zip.

Je comptais utiliser ton tuto sur l'intégration des bibliothèques C dans un programme assembleur pour tester ces différentes bibliothèques.

Grincheux

Messages: 299
Date d'inscription: 17/05/2010
Age: 54
Localisation: Mathenay (39), France

Voir le profil de l'utilisateur http://phrio.biz

Revenir en haut Aller en bas

Re: Les algorithmes de compression - partie 1 - La théorie

Message  faiseur le Mer 9 Juin - 21:24

Grincheux a écrit:
Quels sont les algos les plus efficaces quand on compresse un fichier déjà compressé comme JPEG ou MPEG ?

Je dirai: aucun ! Compresser un fichier préalablement compressé par un bon algorithme ne sert à rien ou presque, voir augmente la taille du fichier.

Quels sont les algos qui sont le moins destructifs ?

Question mal posée, ma réponse: les algorithmes non destructifs Smile

Différence entre JPEG et JPEG2000 ?

http://fr.wikipedia.org/wiki/JPEG_2000


Le futur...
Un fichier compressé puis crypté, grossit-il beaucoup ?

On peut distinguer grossièrement deux cas de figure:

1. Lorsqu'on crypte avec un algorithme XOR qui, pour simplifier, permute simplement les valeurs (donc n'ajoute rien mais modifie les valeurs existantes), il n'y a pas d'ajout, le fichier reste de même taille.

2. Les algorithmes de cryptage plus sécurisés (AES 256, etc) peuvent augmenter la taille du fichier résultant, mais rien de dramatique.

Important: par contre le sens à adopter pour optimiser le tout est: compression puis cryptage. Un fichier crypté avec AES 256 par exemple sera en effet plus difficile à compresser, l'algorithme de compression aura de la peine à trouver des redondances dans le fichier car un des principes d'un bon cryptage est de les éviter.



Faut-il crypter puis compresser pour gagner en place ?

Il est très préférable de faire l'inverse, voir au-dessus la raison.


Quelle différence entre un fichier BMP zippé et un fichier JPEG ? La taille doit être sensiblement la même, par contre on doit moins perdre en qualité d'image ?

C'est une excellente question que j'aurai souhaité traiter dans la 3ème partie, disons avec un petit complément. J'ai distingué deux cas de figure dans mes tests:

1. Un gros fichier bitmap (plusieurs Mo):

Dans ce cas de figure il est préférable d'utiliser de la compression Jpeg. La compression non destructive n'arrivera pas au même résultat.

2. Un petit fichier bitmap (quelques centaines de ko ou moins):

Dans ce cas de figure il est préférable d'utiliser une compression non destructive. J'ai en effet constaté que la réduction est alors plus importante qu'avec une compression Jpeg standard. La différence est faible mais elle existe.


Faut-il compresser les données quand le disque est compressé ?

Compresser sur un algorithme de compression n'est pas intéressant sauf si le premier algorithme de compression a un ratio faible, ce qui peut être le cas pour des algorithmes qui compressent des données du disque dur (en effet, dans ce cas de figure la rapidité de compression est un facteur bien plus déterminant que le ratio de compression, il faut que l'accès disque reste transparent). Il apparaît que ce type de compression très rapide est peut-être celui utilisé par la compression de Windows NT (j'en parle dans la 2ème partie du tutoriel).


Les images ISO sont elles compressées ?

Le format ISO est un format d'image qui n'est, sauf erreur de ma part, aucunement compressé.


C'est facile de poser des questions, tu as fait un bon travail, on a encore faim.
J'ai beaucoup d'idées là dessus, car la semaine dernière j'ai téléchargé des bibliothèques de compression comme
ZLib, UnRar, Lha, GZip, BZip et Zip.

Je comptais utiliser ton tuto sur l'intégration des bibliothèques C dans un programme assembleur pour tester ces différentes bibliothèques.

Justement la 2ème partie de ce tutoriel va traiter de l'utilisation pratique de plusieurs librairies de compression. Par rapport à ce que l'on trouve comme aide sur le net en assembleur (autrement dit quasiment rien) la 2ème partie servira déjà comme une petite référence. Si tu peux faire des tests d'applications sur des librairies que je n'aurai pas mis dans la 2ème partie du tutoriel (à venir très bientôt) ce serait un plus appréciable. De quoi compléter encore la 2ème partie. L'Union fait la force.

faiseur
Admin

Messages: 390
Date d'inscription: 02/05/2010

Voir le profil de l'utilisateur http://aliasoftware.com/

Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum