La compression de fichier

Lorsque des textes se retrouvent dans un dossier compressé (.zip; .rar; etc) c'est qu'il est compressé... mais qu'est ce qu'une compression ?

Le codage des caractères

Le texte d'origine est en cade ASCII sur un octet (8bits), il permet de coder les caractères américains. Tous les caractères sont codés sur le même nombre de bit. Pour compresser sans perdre d'information il faut coder les caractères sur un nombre de bit différent : plus la lettre est fréquente plus le nombre de bit nécessaire pour la coder sera petit.

Par exemple dans la phrase : "C'est un texte"; le e et le t apparaissent 3 fois, il est judicieux de les coder avec moins de bit suivant un arbre binaire. D'abord on fait des couples de lettre et leur fréquence puis on réalise l'arbre ( attention les racines sont en haut et les feuilles en bas.

Voici un exemple d'arbre binaire :

Avec cet arbre, le codage du "e" est 110 au lieu d'un octet !

Cependant, il faut enregistrer le code et l'arbre car il existe de nombreux arbres possibles pour un texte donné. On appelle cet algorithme un algorithme de Huffman.

Permutation circulaire de Burrows Wheeler

Une permutation circulaire consiste à déplacer la première lettre du texte à la fin.

tete_a_tete

ete_a_tetet

te_a_tetete

e_a_tetetet

_a_tetetete

a_tetetete_

_tetetete_a

tetetete_a_

etetete_a_t

tetete_a_te

etete_a_tet

Nous avons effectué toutes les permutations circulaires, il faut maintenant les classer par ordre alphabétique et relever la dernière lettre:

Après avoir réaliser toutes les permutations circulaires et avoir classé par ordre alphabétique, on relève la dernière lettre et la position du texte de départ (7eme ici). Souvent les lettres semblables se retrouvent associées comme ici

Le "move to front"

On suppose qu'après les modifications apportées avec Burrows Wheeler nous avons :

7,etttteeea

On associe chaque lettre avec son numéro dans l'ordre alphabétique avec a=0, b=1, ..., z=25.          Si une lettre est codée, elle devient première de l'alphabet et ainsi il ne faut que un 0 pour coder la prochaine lettre (si c'est la même). Ainsi avec notre code nous avons

e->4          t->19   t->0   t->0   t->0          e->1   e->0   e->0          a->2

Ce qui fait 4,19,0,0,0,1,0,0,2 après le move to front. On remarque que beaucoup de lettres seront codées avec un nombre de bit très petit ce qui permet une compression de fichier plus efficace.

Les 3 méthodes que nous avons vu sont associées pour créer des fichiers .zip ! On les utilise dans ces ordres :

Burrows Wheeler

Move to front

Huffman

Pour décoder on suit le chemin inverse.