COMPRESSION - analyse des projets zip & rar

Les données, quelque soit la nature des fichiers, occupent une place, un espace sur les volumes de stockage tels que disques durs,  parfois non négligeable. Les volumes de stockage n’étant pas extensible sans moyen financier supplémentaire, la compression peut être une solution pour résoudre les problèmes de stockage. Le ZIP et le RAR sont des formats de fichier permettant la compression de données sans pertes; sans aucune pertes des données.

Quels sont les systèmes mise en oeuvre pour compresser, décompresser par ces différentes applications ZIP et RAR? Voici une présentation de ces deux systemes de compressions:


Fichier ZIP :

Le format ZIP a été inventé par Phil Katz pour le logiciel PKZIP. Katz décida de créer son propre format PKZIP utilisant l'extension de fichier .zip et l'algorithme deflate. Le format JAR (Java Archive) est identique au format ZIP. On peut renommer les fichiers .jar en .zip.

Fichier RAR:

Le format RAR est un format de fichier propriétaire permettant la compression de données. Ce format a été inventé par Eugene Roshal. Il a également publié un code source permettant de décompresser les archives RAR sous une licence qui en permet la libre distribution et modification (la version libre ne peut toutefois pas décompresser les archives RAR de version 3). Cette licence interdit d'utiliser ce code source pour construire un codeur compatible. La méthode de codage est dite propriétaire. L'un des avantages du format RAR est son efficacité à produire des découpes de fichiers. D'autres formats de compression comme le format ouvert 7-zip le permettent également. Un autre avantage du format RAR est sa capacité de chiffrement des données ; celui-ci est toutefois possible par d'autres formats, tel 7-zip.
Quels sont  les systèmes de codage utilisés par les applications ZIP et WINRAR?

Algorithmes employées par 7-zip : Pre-prossessing +LZMA+LZ77+BWT

Algorithmes employées par Winrar : Pre-prossessing+LZ77+Huffman

Le tableaux ci-dessous explique les différences entre les deux applications et donc les avantages et inconvénients de chacun et l’intérêt à prendre l’un ou l’autre.

Recovery Record : Permet de récupérer les fichiers endommagés

Cryptographie : Crypte les données. Essentiel parfois

Verrouillages d’archives : Permet de mettre un mot de passe au fichier archive pour l’ouvrir

Les algorithmes ZIP et RAR utilisent des systèmes de codage, crées par des chercheurs, et mathématiciens. Ci-dessous, un bref historique, et explications des quatre systèmes suivant: LZ77, LZMA, BWI, HUFFMAN

 

Algorithme LZ77

Historique des algorithmes LZ77 :

En 1977 Jacob Ziv et Abraham Lempel fournissent une technique de compression différente de l’algorithme de Huffman, et 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 LZ77 de compression 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 LZ77 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 LZ77 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 :

La chaîne /WED/WE/WEE/WEB.
Compactons-la avec la technique Lempel-Ziv :

Il faut 15*8 = 120 bits pour stocker cette chaîne en mémoire  
(1 caractère = 8 bits = 1octet)



L'algorithme sort : '/WEDEB'. Ici, il ne faut plus que 4*9 + 6*8 = 84 bits. (après /WED, on dépasse 255 : il faut utiliser 9 bits). Remarque : Pour un taux de compression "normal", il est recommandé d'utiliser une fenêtre de plusieurs milliers de caractères, pour un tampon de pré-lecture d'une centaine de caractères.


Variante de l’algorithme

Il existe des variantes des compressions LZ77 :

  • 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 LZ77 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 LZ77 est très rapide mais ne compresse que peu les images de 2 à 24 bits. Néanmoins, elle était peu utilisée car elle était brevetée par la société Unisys jusqu’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 LZ77.


Algorithme LZMA

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).

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.

 

Algorithme BWT

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 est actuellement l'un des formats offrant le plus grand 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). Toutes les lettres sont décalées vers la droite. Une fois terminé cette opération, on trie par ordre alphabétique.  

Pour la décompression, il est nécessaire de garder en mémoire la position de la chaîne originale, ici 4. Le texte codé est donc la dernière colonne, soit : « 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. 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 contiendra beaucoup de 0. Ceci assure avec un algorithme de type codage de Huffman un quotient de compression élevé.

Algorithme de Huffman

Historique:


L’algorithme de Huffmann a été décrit pour la première fois en 1952. L’algorithme 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. Prenons l’exemple d’un fichier de texte : Le fragment d’information sera un caractère ou une suite de caractères. 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. On peut 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.


Théorie:

Le code de Huffman est le code irréductible optimal. Il s’appuie sur trois principes :

P = probabilités
N = Fréquence

  • Si pj > pi alors ni = nj,
  • Les deux mots les moins probables ont des longueurs égales.


Ces derniers sont écrits avec les mêmes n max-1 premiers caractères. En utilisant itérativement cette procédure, on construit les mots-codes Mi des messages mi.


Exemple:

On considère la source S = {m1, m2, …, m8} munie de la loi de probabilité : p1 = 0,4 ;        p2 = 0,18 ; p3 = p4 = 0,1 ; p5 = 0,07 ; p6 = 0,06 ; p7 = 0,05 ; p8 = 0,04. On place ces probabilités par ordre décroissant dans la colonne pi(0) du tableau ci-dessous. On remarque que dans la colonne pi(0) les probabilités des messages m7 et m8 sont les plus faibles. On les somme alors puis on réordonne, toujours par ordre décroissant, les probabilités afin de créer la colonne pi. De manière générale, on somme les deux probabilités les plus faibles de la colonne pi(k), puis on réordonne les probabilités par ordre décroissant afin d’obtenir la colonne pi(k+1). Finalement on a donc le tableau suivant.

On attribue les bits ‘0’ et ‘1’ aux deux derniers éléments de chaque colonne :




Pour chaque message mi, on parcourt le tableau de gauche à droite et on détecte dans chaque colonne On propose par exemple de déterminer le mot code M6 du message m6. On détecte donc toutes les transformations incluant m6 (représentées en bleu), les bits qu’elles rencontrent (représentées en vert) :


Le mot-code M6 est alors obtenu par simple lecture de droite à gauche des bits contenus dans les rectangles verts : ‘0’ – ‘1’ – ‘0’ – ‘1’. En procédant de même pour chacun des messages, on obtient :


La longueur moyenne des mots-codes vaut donc :



On peut comparer cette grandeur avec l’entropie H de la source :



L’efficacité h du code de Huffman pour cet exemple est donc de  2,61 / 2,552 = 97,8 %.
À titre de comparaison, il faut 3 bits pour coder en binaire naturel 8 messages différents 23 = 8). Pour cet exemple, l’efficacité du code binaire naturel est donc de seulement 3 / 2,552 = 85 %.

Application :

Soit un texte possédant 100 lettres, dans lesquelles il y a 44 fois la lettre 'e', 21 fois la lettre 'a', 14 fois la lettre 'c', et 7 fois les lettres 'b' 'd' et 'f'.

Construction de l’arbre de Huffman :

Afin de coder les caractères, nous allons construire un arbre binaire. On rappelle, qu'un arbre est constitué d'une racine, d'un ou plusieurs nœuds, et de feuilles. On appelle racine le père de tous les nœuds (la racine est aussi un nœud). Un nœud représente une 'branche' de l'arbre. Une feuille est un nœud qui n'a pas de fils. Nous allons voir que la valeur binaire d'un caractère codé par Huffman n'est en fait que le chemin allant de la racine à la feuille codant ce caractère. Ainsi, lors de la lecture d'une valeur binaire par Huffman, un '0' signifie aller au nœud fils gauche", et un '1' signifie "aller au nœud fils droite".


Voilà le tableau résumant la compression :



Conclusion:

Cet algorithme est simple et efficace. Grâce à ça 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.

Conclusion

  • LZ77 : L’algorithme LZ77 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.