Les Automates d'états finis et la compression de données


DUMOULIN Nicolas - GELY Patrick



D'après l'article "Data Compression Using Antidictionaries" publié en 2000 par M. Crochemore, F. Mignosi, A. Restivo et S. Salmei





Remonter en haut de la page !

1. Introduction à la compression

Remonter en haut de la page !


La compression de texte a pour but de réduire le nombre de symboles nécessaires à leur représentation. Dans les applications, la compression de texte est utilisée pour économiser de l'espace de stockage et le temps de transmission. La méthode ne doit pas entraîner de perte d'informations (pas comme la norme JPEG) : une méthode consisterait à éliminer les accents dans un texte écrit en français, cela ne gênerait pas la compréhension mais elle ne serait pas intéressante pour des raisons d'esthétisme.

Il existe de nombreux algorithmes de ce genre.

Principe simple : cet algorithme élimine les répétitions successives de caractères.

Exemple : AAAAAAABBBFF à @7A@3B@2F

Plus utilisé pour la compression des images.

Principe : réduire le nombre de bits utilisés pour le codage des caractères fréquents dans un texte et augmenter ce nombre pour des caractères plus rares.

Exemple :


Bien adapté à la compression de texte.


Un sujet ayant lu un nombre de caractères successifs d'un texte doit deviner le caractère suivant. Il est éventuellement corrigé si la prédiction se révèle fausse, et il recommence alors. Dans cette expérience, toutes les redondances sont donc prises en compte, le sujet humain utilise toutes ses connaissances et intuitions, formelles et sémantiques, pour faire sa prédiction.

Cette technique repose sur le fait que la langue françaises (par exemple) ne contient que des mots français.


Remonter en haut de la page !

2. Utilisation d'un antidictionnaire

Remonter en haut de la page !

Un antidictionnaire d'un langage est un dictionnaire de mots qui n'appartiennent pas au langage. C'est cet antidictionnaire qui va permettre de déterminer les caractères redondant dans le texte à compresser.

Par exemple, en français le facteur w=qe  n'appartient pas au langage français, de même que il n'existe pas de lettre u de l'alphabet français telle que w=qae appartienne au langage français. On pourra donc supprimer la lettre u à chaque fois qu'elle apparaîtra dans ce contexte.

Par la suite, nous nous intéresserons à l'alphabet binaire {0,1}. Prenons un texte w appartenant cet l'alphabet, et soit AD l'antidictionnaire pour w. En lisant le texte w de gauche à droite, si à un certain moment, le préfixe courant v du texte admet comme suffixe un mot u' tel que u = u'x Î AD avec x Î {0,1}, c'est-à-dire u est interdit, alors on est sûr que la lettre qui suit v dans le texte ne peut pas être x, et que par conséquent ce ne peut être que l'autre lettre. Du fait que l'on peut prédire ce caractère il devient redondant.

Nous allons ainsi pouvoir éliminer tous les caractères pouvant être prédit.

En pratique les antidictionnaires ne peuvent pas être à priori donnés, ils doivent en fait être construits en fonction du texte qu'on est en train d'étudier ou en fonction d'une famille de texte auquel le texte qu'on étudie appartient. Ils doivent être également le plus pertinent et le plus léger possible. Pour cela il existe des algorithmes, un peu compliqués et que nous n'expliquerons donc pas ici.

L'idée est en fait de construire l'ensemble des facteurs de w noté F(w). Par exemple si w = 01001010 alors F(w) = { e, 0, 1, 00, 01, 10, 001, 010, 100, 101, ...}. Il faut ensuite prendre une partie du complémentaire de cet ensemble pour construire l'antidictionnaire. C'est la façon de déterminer cette partie qui reste délicate. Par exemple, pour w {11, 000, 10101} peut être un antidictionnaire intéressant.


Remonter en haut de la page !

3. Algorithme de compression

Remonter en haut de la page !

Voici l'algorithme qui permet de compresser un mot w à l'aide de son antidictionnaire AD :

v ßeg ße;

pour a ß première à la dernière lettre de w faire
     si pour chaque suffixe u' de v, u'.0 et u'.1 Ï AD alors
        g ß g.a ;
     finsi
     v ß v.a ;
finpour

retourner (|v|,g ) ;

 

Pour mieux comprendre, faisons le tourner sur un exemple :

Soit w = 01001010 et AD = {000, 10101, 11}

v

g (w)

 

e

e

 

v1 = 0

0

 

v2 = 01

01

u = 11 Î  AD

v3 = 010

01

 

v4 = 0100

010

u = 000 Î  AD

v5 = 01001

010

u = 11 Î  AD

v6 = 010010

010

 

v7 = 0100101

0101

u = 11 Î  AD

v8 = 01001010

0101

u = 10101 Î  AD

v9 = 010010100

0101

u = 000 Î  AD

v10 = 0100101001

0101

u = 11 Î  AD



g n'est pas injective. En effet, g (010010100) = g (01001010001) = 0101. Ainsi en plus de g , l'algorithme doit également retourner la longueur original du mot.

 

L'algorithme de décompression fonctionne comme suit : il reconstruit le mot w en devinant la lettre suivant le préfixe v de w déjà décompressé. Si il existe un mot u = u'x, x Î  {0,1}, dans l'antidictionnaire AD tel que u' est un suffixe de v alors la lettre résultante est y tel que y¹ x. Et ainsi de suite pour les autres lettres du mot.

Voici l'algorithme qui permet de décompresser un mot g à l'aide de son antidictionnaire AD, et de sa longueur n :

v ß e  ;

tant que |v| < n
     si pour chaque suffixe u' de v et x Î {0,1}, u'x Î AD alors
          v ß v.Ø x ;
     sinon
          b ß prochaine lettre de g  ;
          v ß v.b
     finsi
fintantque

retourner (v) ;


Remonter en haut de la page !

4. Utilisation d'un automate compresseur

Remonter en haut de la page !

Dans le cas ou l'antidictionnaire choisi est un ensemble fini, la propriété nécessaire pour l'algorithme de compression présentée précédemment, peut être vérifiée grâce à un automate d'états finis reconnaissant les mots du langage n'ayant aucun facteurs dans l'antidictionnaire.

Pour ce faire on construit tout d'abord un automate d'états finis reconnaissant uniquement les mots de l'antidictionnaire. A partir de cet automate on peut construire un automate reconnaissant les mots du langage n'ayant aucun facteur dans l'antidictionnaire.

L'algorithme permettant de passer d'un automate reconnaissant les mots de l'antidictionnaire à un automate reconnaissant les mots évitant les facteurs d'un antidictionnaire est donné ci dessous :


Entrée : automate T=(Q, A, i, T, ')

Pour chaque a Î A
       Si '(i, a) existe alors
               (i, a) : = '(i,a) ;
              f( (i,a)) :=i ;
       Sinon
               (i,a) :=i ;
       Finsi
Finpour
Pour chaque état p Î Q \{i} en 'width-first search ' et chaque a Î A
       Si '(p,a) existe alors
               (p,a) := '(p,a)
              f( (p,a)) := (f(p) ,a)
       Sinon si p Ï T
                      (p,a) := (f(p),a) ;
                  sinon
                      (p,a)= (f(p),a) ;
                  finsi
       Finsi
Finpour

Renvoyer (Q, A, i, Q\T, ) ;


Etape1

 

 Cet automate reconnaît les mots de l'antidictionnaire.

Etape 2

 

Automate reconnaissant les mots du langage en évitant les facteurs de l'antidictionnaire.

Nous voyons ici que cet automate peut nous amener à des états poubelles. Ces états poubelles représentent en fait les états qu'on veut éviter. Dans l'étape suivante on les supprime donc.

Etape 3

  

C'est sur ce dernier automate que l'algorithme de compression va être appliqué.

  

Sur l'automate présenté précédemment on procède comme suit afin de réaliser la compression :

1er étape : On trace l'unique chemin représentant le mot w qu'on cherche à compresser.

2e étape : Les lettres de w représentent un arc allant de qi à qj. Si cet arc est l'unique arc sortant de l'état qi, alors la lettre est redondante on la supprime donc.

En résumé à chaque fois que sur le chemin représentant le mot w on rencontre un seul arc sortant de l'état qu'on est en train d'étudier on supprime la lettre correspondante. Dans les autres cas on conserve la lettre (le déroulement de l'algorithme est présenté dans le tableau 1) .

 

 

Les traits les plus gros représente l'unique chemin qui permet de trouver le mot étudié . Les traits en pointillés sont des arcs de transitions normaux nous les avons mis en pointillé dans un souci de clarté . Les traits et états en gris représentent des états ou des transitions poubelles , ils ne sont pas pris en compte dans l'algorithme .

Déroulement de l'algorithme :

On passe les états un à un jusqu'à l'état q7 (on suppose que l'on connaît la longueur du mot à compresser, l'état q7 représente ici en fait la fin du mot qu'on compresse )

Etat étudié

Lettre du mot

Nombres d'arcs sortant

Lettre effacée ?

Mot obtenu

q0

0

2

NON

0

q1

1

2

NON

01

q4

0

1

OUI

01

q5

0

2

NON

010

q2

1

1

OUI

010

q4

0

1

OUI

010

q5

1

2

NON

0101

q6

0

1

OUI

0101

q7

FIN

FIN

FIN

0101

(Tableau 1 : Déroulement de l'algorithme )

Mot en entrée w=01001010 Mot compressé en sortie : w'=0101



Remonter en haut de la page !

5. Conclusion

Remonter en haut de la page !

Cet algorithme est intéressant et performant et sans perte, donc tout à fait adapté à la compression de texte. Tous les aspects de cette technique de compression n'ont pas été abordés, notamment l'algorithme de construction de l'antidictionnaire.

Le sujet de départ ne portait pas directement sur l'article de M.Crochemore et ses collaborateurs, mais nos recherches sur le sujet n'ont fait qu'aboutir sur cet article, ou sur d'autres articles sur la compression en général mais sans parler des automates.

Pour plus d'informations et de détails, vous pouvez vous reporter à l'article en question :

http://www-igm.univ-mlv.fr/~mac/