L'algorithme d'Huffman
L'algorithme de compression de données sans perte de David Huffman a été crée pour réduire le nombre de bits utilisés et ainsi réduire la taille des fichiers lorsqu'ils sont compressés, tout en ne perdant aucune donnée (système de codage utilisé pour la compression de texte, ne pouvant pas se permettre de perdre des caractères).
Le premier codage de caractère utilisé était l'ASCII, adapté au caractères des claviers américains. Tous les caractères sont alors codés sur le même nombre de bits. Pour compresser avec l'algorithme d'Huffman, il faut alors coder les caractères les plus fréquents sur un plus petit nombre de bits. Par exemple, avec la phrase "C'est un texte", on obtient des couples lettre-fréquence: (c;1); (';1); (e;3); (s;1); (t;3); (_;2); (u;1); (n;1); (x;1). On peut ainsi créer un arbre d'Huffman qu'il faut absolument lier au code car il existe de nombreux arbres possibles pour un texte donné. On associe enfin chaque lien, selon leur direction, à 0 ou à 1 et on peut désormais coder la phrase en binaire, c'est-à-dire: 1101 1100 01 1001 00 111 1000 1011 111 00 01 1010 00 01. On retrouve aussi le nombre de caractères de la phrase.
tete a tete
etete a tet
tetete a te
etetete a t
tetetete a
tetetete a
a tetetete
a tetetete
e a tetetet
te a tetete
ete a tetet
tete a tete
Il existe aussi le système de permutation de Burrows-Wheeler, qui permet de réorganiser les données en vue d'une compression. Cela permet de ranger tous les mêmes caractères d'un texte ensemble. Prenons la phrase "tete a tete", on décale ensuite la phrase d'une lettre que l'on va placer au début ou à la fin de la phrase, selon le sens de la permutation. Après avoir permuté toutes les lettres, on classe les chaînes de caractères obtenues par ordre alphabétique puis on relève la première lettre de chaque chaîne. On se retrouve alors avec une suite de caractères qui ont été regroupés ensemble.
Enfin, après avoir effectué la permutation de Burrows-Wheller, on utilise le "Move to Front" à partir de l'ordre obtenu auparavant (ici: 7, etttteeea) commençant par le numéro du texte de départ après les permutations puis le classement alphabétique. En utilisant le dictionnaire, on attribue une valeur allant de 0 à 25 à toutes les lettres de l'alphabet puis on ramène la prochaine lettre que l'on veut coder à l'avant de l'alphabet. Exemple:
a b c d e ... t ... z
0 1 2 3 4 19 25
←←←←←←
e→4
e a b c d... t ... z
0 1 2 3 4 19 25
←←←←←←←←←
t→19
t e a b c d ...... z
0 1 2 3 4 5 25
←←
t→0 t→0 t→0 e→1
e t a b c d ...... z
0 1 2 3 4 5 25
e→0 e→0 a→2
On obtient donc, à la fin, la suite de chiffres suivantes: 4; 19;
0; 0; 0; 1; 0; 0; 2. Ces trois méthodes sont utilisées et associées pour créer des fichiers .zip (B-W puis Move to Front et enfin Huffman). Pour décoder on suit le sens inverse.