Le but de ce projet est de mettre en œuvre un algorithme de compression/décompression. La méthode qui vous est proposée permet d'atteindre des taux de compression très élevés (moins de 2 bits/caractère) tout en conservant une vitesse de compression et de décompression raisonnable (environ 2 fois plus lent que zip, écart qui est masqué par la différence entre vitesse de transmission et vitesse de calcul des ordinateurs courants.
La section « Survol » présente le sujet dans ses grandes lignes, chaque phase est détaillée plus bas. Dans un premier temps occupez-vous des parties 1 et 2. Pas de panique ! posez les choses proprement sur le papier pour commencer. ET POSEZ DES QUESTIONS.
L'algorithme proposé applique trois tranformations au texte à comprimer. Chacune de ces transformations est inversible. La décompression consiste donc simplement à enchaîner les tranformations inverses dans l'ordre inverse.
Seule la troisième transformation effectue réellement une compression. Les deux premières la rendent particulièrement efficace.
L'efficacité de la compression provient du fait que la première phase de tri regroupe toutes les lettres qui sont dans un même contexte. Or dans un texte normal, le contexte est un excellent prédicteur. Ainsi, une zone du texte trié correspondant à une suite de contextes similaires ne comportera qu'un très petit nombre de lettres différentes et, donc, plusieurs suites de lettres identiques. La deuxième phase ne produira donc que des petits entiers pour cette zone, avec plusieurs séquences de zéro. De fait, sur des textes typiques, on a 60% de zéro, 20% de un, 10% de deux, etc. (la distribution décroît exponentiellement).
Soit t = t0t1... tn le bloc de texte à comprimer.
On supposera pour simplifier que tn est un caractère spécial (par exemple le
'\0') qui n'apparaît pas dans le début
t0...
tn-1 du texte. Le
contexte d'une lettre ti du bloc est la chaîne Ci =
ti-1ti-2... t0.
La première phase de l'algorithme commence par trier les Ci, c'est-à-dire par calculer la permutation σ de {0,...,n} telle que Cσ(0), Cσ(1),..., Cσ(n) soient triés par ordre lexicographique croissant. Elle produit ensuite la permutation de t correspondante s = tσ(0), tσ(1),..., tσ(n).
|
|
Cette permutation est inversible. En effet, supposons connu s = s0s1... sn ; on va montrer comment calculer simultanément l'inverse σ-1 de σ et donc t de proche en proche.
Pour le cas de base, notons qu'on a σ-1(0) = 0 puisque C0 est la chaîne vide. Si on a calculé σ(i) = j alors on a immédiatement ti = sj.
Par définition, σ(i+1) est le nombre de contextes Ck précédant Ci+1 dans l'ordre lexicographique. Comme Ci+1=tiCi, un tel Ck est soit le contexte vide C0, soit l'un des T(ti) contextes Ck commençant par un tk-1< ti = sj, soit l'un des T'j contextes Ck tels que tk-1= ti = sj et Ck-1 < Ci. D'où σ(i+1) = 1 + T(sj) + T'j.Comme Ck-1 < Ci équivaut à σ(k-1)< j = σ(i), T'j est tout simplement le nombre d'occurrences de sj dans s0... sj-1.
On peut donc précalculer tous les
T'j avec une simple
boucle for qui compte le nombre d'occurrences de chaque lettre
de l'alphabet dans s. En outre, le résultat de cette
boucle permet aussi de calculer les T(a) de proche en proche en parcourant les lettres
dans l'ordre alphabétique (et en excluant
tn).
Sur notre exemple (où tn
est d), on trouve
| j | sj | T'j | T(sj) |
| 0 | a | 0 | 0 |
| 1 | b | 0 | 3 |
| 2 | d | _ | _ |
| 3 | c | 0 | 4 |
| 4 | r | 0 | 5 |
| 5 | a | 1 | 0 |
| 6 | a | 2 | 0 |
C'est la phase la plus coûteuse en temps de calcul et en mémoire. On n'a pas besoin de vraiment créer les Ci ; on se contente de représenter chaque Ci par son indice i (c'est-à-dire qu'on représente directement s).
L'algorithme le plus efficace pour cette phase critique est une variante de Quicksort due à Bentley et Sedgewick. En effet, la comparaison de chaînes n'est pas une opération en temps constant et donc une application naïve de Quicksort est en fait en O(n2log n) ! Pour éviter cette dégradation, Bentley et Sedgewick proposent de ne comparer qu'un caractère à la fois mais en modifiant la procédure de partition de manière à répartir le contenu du sous-tableau à trier en trois zones, contenant les indices des contextes dont le premier caractère est respectivement inférieur, égal, ou supérieur au caractère pivot. Comme tous les contextes de la zone médiane commencent par le pivot, on peut les trier récursivement suivant leur deuxième caractère et ainsi de suite. Plus généralement, pour trier un sous-tableau suivant le ke caractère, on le tri-partitionne selon le ke caractère et on trie récursivement le sous-tableau du milieu suivant le k+1e caractère et les extrémités selon le ke.
Le texte s comporte beaucoup de caractères identiques se suivant. La deuxième phase va les remplacer systématiquement par zéro. On suppose connu l'alphabet S = a0...ap-1 du texte. Pour tout j≤ n, soit t(j) le plus grand indice k< j tel que sk = sj, s'il existe. La suite r produite par la deuxième transformation est définie formellement par
| rj = |
|
|
On calcule aisément la deuxième transformation en calculant simultanément pour chaque j la permutation Sj de l'alphabet où les lettres sont rangées dans l'ordre inverse de leur apparition dans s0... sj-1. Ainsi on a, pour s = bbbaaacbbb, r = 1001002200 :
| j | sj | rj | Sj |
| 0 | b | 1 | abc |
| 1 | b | 0 | bac |
| 2 | b | 0 | bac |
| 3 | a | 1 | bac |
| 4 | a | 0 | abc |
| 5 | a | 0 | abc |
| 6 | c | 2 | abc |
| 7 | b | 2 | cab |
| 8 | b | 0 | bca |
| 9 | b | 0 | bca |
Comprimer la suite r, composée principalement de zéro et de petits entiers, est maintenant chose assez simple. Il vous est proposé de comprimer l'information résultant des phases 1 et 2 en deux temps : d'abord coder les suites de zéro et les petits entiers, ensuite traduire en hexadécimal.
La compression des suites de zéro peut se faire aisément en remplaçant chaque suite par sa longueur, codée en binaire à l'aide de deux symboles spéciaux α et β. On choisira une représentation binaire de la longueur l par b0... bn où b0,b1,...,bn est l'unique séquence de 1 et de 2 (et pas de 0 et de 1) telle que l = ∑i=0n bi· 2i.
Dans cette représentation, la suite 000000000 de longueur 9 s'écrira αβα si α désigne 1 et β désigne 2.
Un entier n peut être codé en deux parties s1 et s2 séparées par un 0. La première partie, s1, est une séquence de 1 dont la longueur est le nombre de bits du code binaire de n. La deuxième partie, s2, est ledit code binaire dont le début est implicite.
On peut en effet remarquer qu'un code binaire commence forcément par un 1 (l'entier 0 ne sera jamais codé), il n'est donc pas nécessaire faire apparaître ce premier 1 dans l'écriture binaire qui suit le 0 séparant s1 et s2.
Par exemple, l'entier 9 s'écrit 1001 en binaire. Le nombre de bits est 4 donc s1 = 1111 et s2 = 001 puisque le premier 1 est implicite. L'entier 9 sera ainsi codé 11110001. De même l'entier 1 sera codé 10.
Il reste à coder les deux symboles spéciaux α et β. Facile ! puisque tous les codes des entiers commencent par 1, on peut choisir 00 pour α et 01 pour β...
On écrit alors la séquence obtenue en hexadécimal.
Au final, la séquence de 14 entiers (sur 14 caractères)
1 00000 2
00 2 00 5 9 s'écrira
10010011000111000111100111110001 ce qui, en
hexadécimal, s'exprime
931C79F1 à l'aide de 8 caractères.
Il vous est demandé de concevoir et réaliser un programme qui compresse et décompresse des fichiers en utilisant l'algorithme décrit dans la section précédente.
Noter que l'interface de ce programme peut être tout à fait rudimentaire : un programme qui se contente de lire et d'écrire sur ses flux standard est parfaitement acceptable.
Il vous sera nécessaire de concevoir un format pour les fichiers compressés. Ceux-ci devront en effet contenir, en plus de la suite de codes binaires, tout un ensemble de paramètres généraux tels que la longueur du fichier, la taille des blocs de codage, l'alphabet utilisé, etc.
Vous devrez documenter précisément vos choix de représentation dans votre rapport.
Il est inutile de se préoccuper de l'optimisation du tri.Ce sujet est issu d'un projet de G. Gonthier.