| Avant tout, la première chose à faire est de construire l'antidictionnaire du texte. |
|
On rappelle que l'antidictionnaire d'un fichier est l'ensemble des mots élémentaires (donc binaires) qui n'appartiennent pas à ce fichier. Pour créer cet antidictionnaire la première étape consiste à récupérer tous les facteurs composant le mot binaire à compresser (nous considérons le fichier à compresser comme un mot binaire). C'est une étape assez longue car le nombre de facteur augmente très rapidement avec la taille du fichier. Tous ces facteurs sont stockés en mémoire dans un arbre. La structure élémentaire de cette arbre est la structure Noeud. Chacun de ces noeuds contient deux autres pointeurs sur des noeuds fils. Ces deux pointeurs correspondent aux transitions par `0` et par `1`. Algorithme de construction des facteurs :
Build_Fact(mot_binaire, longueur_mot)
debut
i <- Nouveau_Noeud
Q <- {i}
level(i) <- 0
p <- i
tant que pas à la fin du mot_binaire
a <- prochain bit du mot_binaire
p <- Next(p, a, longueur_mot)
fin tant que
return l'arbre i
fin
Next(Noeud p, bit a, longueur_mot)
debut
si la transition de 'p' en lisant un 'a' est definie : on retourne ce noeud transition
sinon si (level(p) = longueur_mot) : on retourne Next(f(p), a , longueur_mot)
sinon
q <- Nouveau_Noeud
Q = Q U {q}
level(q) <- level(p)+1
transition de 'p' en lisant 'a' <- q
si (p = i) f(q) <- i
sinon f(q) <- Next(f(p), a, k)
retourne q
finsinon
fin
Deuxième étape :A ce stade on se retrouve avec un arbre binaire contenant tous les facteurs du mot que l'on veut compresser. Pour récupérer les mots qui n'appartiennent pas à ce dictionnaire il suffit de parcourir l'arbre en profondeur et chaque fois qu'une transition ne mène nulle part (que ce soit par un `0` ou par un `1`) on rajoute le bit correspondant à cette transition. On est alors sure que cette nouvelle expression ne peut pas être présente dans le texte du départ. On mémorise toutes ces nouvelles expressions dans un second arbre. Le premier arbre des facteurs ne servira plus à partir de maintenant ; il est donc effacé après cette étape. Troisième étape : Maintenant nous avons un arbre binaire contenant des mots qui n'appartiennent pas au texte de départ. Cette nouvelle étape va consister à minimiser cet arbre, c'est à dire à supprimer de l'arbre des mots qui y seraient implicitement déjà car inclus dans d'autres. Par exemple, si les mots '010001100' et '1100' se trouvent dans l'arbre alors on peut supprimer le mot '010001100'. Remarque : Dans l'algorithme, et par conséquent dans le code, cette troisième étape est réalisée en mème temps que la deuxième. Cela pour profiter du parcours en largeur, et éviter ainsi d'avoir à en effectuer un second. Nous sommes maintenant en possession d'un arbre représentant l'antidictionnaire de notre texte. Nous allons voir maintenant comment compresser le mot original à l'aide de cet antidictionnaire. |
COMP(antidictionnaire, mot_a_compresser)
debut
v <- Epsilon
gamma <- Epsilon
prec <- 0
faire
a <- lire_bit(w)
v <- v.a
si (prec=0) alors gamma <- gamma.a
si (il existe un suffixe u' de v tel que u'x appartient a AD, avec x='0' ou '1')
alors prec <- 1
sinon prec <- 0
tant que ( a != derniere lettre de w)
retourne (|w|, gamma)
fin
Remarque :Il ne s'agit pas exactement de l'algorithme présenté dans le document "Text Compression Using Antidictionaries" car nous avons introduit la variable 'prec'. En effet, l'algorithme nous permet de savoir si on peut deviner LE BIT SUIVANT ; si on peut le deviner, c'est LE BIT SUIVANT (et non pas le bit actuel) qui ne sera pas écrit. 'prec' est donc une variable de mémorisation pour l'itération suivante dans une boucle. |
|
Les quatres premiers octets constituent un entier correspondant à la taille en octet du fichier source. Cette taille est transmise car elle est nécéssaire ensuite pour le module décompression. Ensuite, il faut écrire tous les mots de l'antidictionnaire qui ont été utilisés, puisqu'ils sont nécéssaire pour décompresser le fichier. Cette liste de mots est représentée par :
Ce principe s'applique autant de fois qu'il y a de mots à écrire. Ensuite il faut un séparateur pour indiquer la fin de l'entête, et donc le début du code compressé. Ce séparateur se matérialise par deux octets ayant tous les bits à `0`. Remarque : L'octet de poids fort se situe à droite sur Unix et à gauche sur Linux. C'est pourquoi un fichier compressé sous Unix ne pourra être décompressé sous Linux, et vice-versa. Pour que l'application puisse compresser un fichier sur un système et le décompresser sur un autre, il aurait suffit d'adopter un format plus pointilleux, et d'en tenir compte à la lecture du fichier compressé. |