La compression de données est utilisée pour augmenter les capacités de stockage en mémoire ou les vitesses de transmission. La compression est composée d'un encodage et d'un décodage. Un schéma de compression peut être mis en série avec d'autres codages comme les codages correcteurs d'erreurs, les codages cryptographiques, (voir le programme de la Majeure Mathématiques et Informatique), ou les codages de canal. Nous allons étudier une méthode de compression de texte dite codage de Huffman statique. Il existe de nombreux algorithmes de compression de textes. Vous pourrez consulter, par la commande Unix man, des informations sur les commandes de compression pack, compact, compress, zip, gzip etc ... Une méthode améliorant le codage de Huffman statique est le codage de Huffman dynamique.
On considère un texte T à coder. On prendra par exemple T=aabcaab. On lit tout d'abord le texte une fois de gauche à droite, de façon à receuillir les lettres apparaissant dans le texte avec leurs occurences appelées poids. On obtient ici : a:4 b:2 c:1 et l'alphabet du texte est a,b,c.
On construit un arbre binaire pondéré A(T) (chaque noeud a un fils gauche
et un fils droit éventuellement vides, et chaque
noeud a un poids entier),dont
les feuilles représentent les lettres de l'alphabet du
texte, pondérées par leurs occurences.
L'arbre est obtenu par l'algorithme suivant : on part d'un ensemble
de noeuds isolés correspondant aux lettres. On donne le
même père aux deux lettres de plus faible poids.
On élimine les deux noeuds correspondant à ces lettres
de la liste des noeuds à traiter et on les remplace par leur
père affecté d'un poids égal à la somme
des poids des fils. On recommence avec le nouvel ensemble
de noeuds jusqu'à ce qu'il n'y ait plus qu'un noeud qui
devient la racine de A(T).
Sur l'exemple l'arbre A(T) est :
A chaque lettre de l'alphabet est associé son codage binaire dans l'arbre qui est la suite de 0 et de 1 indiquant le chemin de la racine à la feuille représentant la lettre (1 pour fils droit, 0 pour fils gauche). Le codage du texte est la suite C des codages des lettres du texte. Sur l'exemple : C = 1101001101 et le codage de chaque lettre est obtenu par la correspondance :
| a | 1 |
| b | 01 |
| c | 00 |
Le décodage doit permettre de retrouver exactement le texte initial à condition que le texte codé n'ait pas été altéré. Si on appelle hauteur pondérée la somme pour toutes les feuilles f des quantités p(f)l(f), où p(f) est le poids de la feuille, et l(f) la longueur du chemin menant de la racine de l'arbre à la feuille, on peut montrer que A(T) est un arbre pondéré de hauteur pondérée minimale (pour un poids de feuilles donné). La taille du texte codé est cette hauteur pondérée.
Dans la pratique, pour obtenir vraiment une compression, on est amené à travailler sur les bits pour reconstituer des octets consituant le texte codé. Dans ce TP, on fera seulement une simulation du codage. Le texte à coder et le texte codé seront stockés dans un tableau de caractères. Le texte codé sera considéré comme une suite de caractères 0 et 1. Le stockage de l'arbre pourra se faire dans un tableau du type suivant :
| filsG | filsD | poids | bool | ||
|---|---|---|---|---|---|
| 1 | a | - | - | 4 | faux |
| 2 | b | - | - | 2 | faux |
| 3 | c | - | - | 1 | faux |
| 4 | 3 | 2 | 3 | faux | |
| 5 | 4 | 1 | 7 | vrai |
Quel le taux de compression sur un texte que vous avez testé ?
Malgré la double lecture du texte, le codage et le décodage
sont linéaires en fonction de la taille du texte.
Le temps de construction de l'arbre A(T) est négligeable
sur des textes longs. Il est en O(n^2), où n est
le nombre de feuilles. Il existe une méthode
pour le construire en O(nlog(n)). Voyez-vous comment ?
Quel que soit l'algorithme de compression de texte
que l'on utilise, les performances dependent du texte
que l'on comprime. En particulier, il existe toujours au moins
un texte qui n'est pas compressé strictement ?
Voyez-vous pourquoi ?
