Initiation à la recherche (2014-2015)

Le sujet

Cette année le cours d'initiation à la recherche est consacré à la compression de lexiques à l'aide de la réduction d'automates d'états finis acycliques. Nous présentons un algorithme de réduction d'automates acycliques en temps linéaire qui s'appuie sur un tri lexicographique linéaire.

Les documents

Le principal article qui a servi à l'élaboration de ce cours est intitulé "Minimisation of Acyclic Deterministic Automata in Linear Time" de Dominique Revuz dans la revue Theoretical Computer Science 92, (1992), pp. 181-189. J'ai également utilisé un survey de J. Berstel, L. Boasson, O. Carton et I. Fagnot intitulé "Minimization of Automata" daté de janvier 2011.

Présentation du problème

On se donne un lexique (dans le cas présent le lien pointe sur un lexique contenant près de 400.000 formes fléchies du français, i.e. contenant les singuliers, pluriels, conjugaisons, etc.), c'est-à-dire un ensemble de mots \(L\) sur un alphabet \(\Sigma\) ainsi qu'un mot \(w\in \Sigma^*\). On s'intéresse alors au problème de décision suivant:

\(w\) appartient-il ou non à \(L\) ?
L'objectif est de trouver une structure de données adéquate pour représenter ce lexique et pour que la recherche du mot \(w\) se fasse le plus rapidement possible. Une solution élégante et efficace à ce problème consiste à représenter le lexique \(L\) à l'aide d'un automate fini déterministe qui reconnaît les mots du lexique, ce que nous expliciterons plus loin. Le cours a pour but de présenter un algorithme de réduction d'automates qui permet de construire l'automate minimal reconnaissant le lexique en temps linéaire par rapport au nombre d'états de l'automate associé à l'arbre lexicographique du lexique.

Quelques rappels sur les graphes

Un graphe orienté \(G=(X,U)\) est un couple constitué d'un ensemble \(X\) de sommets et d'un ensemble d'arcs \(U\subseteq X \times X\). On représente schématiquement un graphe en dessinant des cercles autour des sommets et en reliant ces cercles par des flèches pour matérialiser les arcs, ainsi l'arc \((x,y)\in U\) est représenté par une flèche qui part de \(x\) (le sommet de départ) et qui aboutit en \(y\) (le sommet d'arrivée). L'arc \((x,y)\) est dit incident à \(x\) ainsi qu'à \(y\), on peut préciser vers l'extérieur en \(x\) et vers l'intérieur en \(y\). Quand l'orientation importe peu, on parle d'arêtes plutôt que d'arcs et on les définit à partir de paires de sommets au lieu de couples, on parle alors de graphe non-orienté.
Si l'ensemble des sommets est fini le graphe est dit fini et son cardinal définit l'ordre du graphe. Pour tout couple \((x,y)\in U\), les sommets \(x\) et \(y\) sont dits adjacents. Un arc de type \((x,x)\) est appelé une boucle. Un chemin est une suite d'arcs consécutifs au sens où le sommet d'arrivée d'un arc est celui de départ de l'arc suivant dans la suite. Un chemin dont le sommet d'arrivée est celui de départ est appelé circuit (Quand on ne tient pas compte de l'orientation des flèches, on parle respectivement de chaîne et de cycle). Un graphe qui contient un cycle est dit cyclique, acyclique dans le cas contraire.

Si \(G=(X,U)\) est un graphe, et \(V\subseteq U\) est une partie des arcs de \(G\), le graphe \((X,V)\) est appelé graphe partiel de \(G\). Si on considère une partie \(Y\subseteq X\), et la partie \(V\subseteq U\) qui ne contient plus que les arcs incidents aux sommets \(x\) et \(y\) tels que \((x,y)\in V\), il s'agit du sous-graphe de \(G\) induit par \(V\). Un graphe est dit connexe si pour toute paire de sommets \(x\) et \(y\), il existe une chaîne qui les relie et fortement connexe s'il existe un chemin reliant \(x\) à \(y\) et un chemin reliant \(y\) à \(x\). Quand un graphe n'est pas connexe, on peut considérer ses composantes connexes qui sont les plus grands sous-ensembles de sommets possibles tels que les sous-graphes induits soient connexes.

Le graphe de la figure 1 est un graphe orienté qui n'est pas connexe, mais contient deux composantes connexes \(\{e,g\}\) et \(\{a,b,c,d,f\}\). Il contient deux boucles \((e,e)\) et \((b,b)\) et d'autres cycles comme \((a,f,c,b,a)\) par exemple (qui n'est pas un circuit). La séquence \((a,f,c,d)\) constitue un chemin, la séquence \((b,c,d,c,b)\) un circuit de ce graphe. Les sommets \(c\) et \(a\) sont reliés par la chaîne \((c,b,a)\) qui n'est pas un chemin puisqu'il n'existe pas d'arc \((b,a)\).

Un graphe est dit étiqueté si on lui adjoint une fonction \(\nu:U\rightarrow E\) où \(E\) est un ensemble dont les éléments sont appelés des étiquettes, généralement un alphabet ou un ensemble de mots sur un alphabet et on surmonte les flèches des étiquettes correspondantes.

Automates

Considérons un alphabet fini \(\Sigma\). On appelle mot défini sur \(\Sigma\) toute suite finie de symboles de \(\Sigma\) et on omet de séparer les symboles de la suite comme on le fait pour un mot d'une langue naturelle. La suite vide définit un mot particulier appelé mot vide et noté \(\epsilon\). La fermeture de Kleene d'alphabet fini \(\Sigma\) est l'ensemble des mots définis sur \(\Sigma\) et on note cet ensemble \(\Sigma^*\). Par exemple, pour l'alphabet binaire \(\Sigma=\{0,1\}\), on a \[\Sigma^*=\{\epsilon,0,1,00,01,11,100,\ldots\}.\] et pour l'alphabet latin \(A=\{a,b,c,\ldots,z\}\), \[\Sigma^*=\{\epsilon,a,b,\ldots,z,aa,ab,\ldots\}.\] qui contient en particulier tous les mots de la langue française

Démontrez que la fermeture de Kleene d'un alphabet fini \(\Sigma\) de cardinal \(n\) est un ensemble dénombrable. Indication : considérez les mots comme des nombres écrits en base \(n\) pour construire une bijection entre \(\Sigma^*\) et \(\bf N\).
On munit l'ensemble \(\Sigma^*\) d'une loi de composition interne notée \(\cdot\) appelée concaténation : si \(u=u_1u_2\ldots u_n\) et \(v=v_1v_2\ldots v_m\) alors \(u.v:=u_1u_2\ldots u_nv_1v_2\ldots v_m\). Par exemple si \(u = \text{bon}\) et \(v = \text{jour}\), \(u.v = \text{bonjour}\). Cette loi n'est manifestement pas commutative, en revanche elle est associative et le mot vide \(\epsilon\) en constitue l'élément neutre ce qui fait de \((\Sigma^*,\cdot)\) un monoïde. À l'instar de la multiplication, on omet souvent de noter le point. Les mots constitués d'une seule lettre constituent une base de \(\Sigma^*\) puisque tout mot se décompose (toujours l'analogie avec la multiplication) de manière unique comme un produit de symboles de l'alphabet \(\Sigma\), ce qui fait de \(\Sigma\) un monoïde libre.

Un automate fini non-déterministe est un quintuplet \((\Sigma,Q,I,T,F)\) où \(\Sigma\) est un alphabet fini, \(Q\) est un ensemble fini d'états, \(I\subseteq Q\) est l'ensemble des états initiaux, \(T\subseteq Q\) est l'ensemble des états terminaux et \(F\subseteq Q\times\Sigma\times Q\) est l'ensemble des transitions de l'automate.

Un chemin dans le graphe associé à un automate détermine une séquence de transitions telles que l'état d'arrivée d'une transition est l'état de départ de la transition suivante. Ce chemin est appelé un calcul que l'on peut résumer par un triplet \((p,w,q)\in Q\times\Sigma^*\times S\) ou encore \(p\stackrel{w}{\rightarrow} q\) où \(w\in\Sigma^*\) est la concaténation des étiquettes des transitions successives dont la première a pour état de départ \(p\) et la dernière a pour état d'arrivée \(q\).

La représentation d'un automate est celle d'un graphe étiqueté dont les sommets sont les états de l'automate et où chaque transition \((p,a,q)\) de l'automate détermine un arc \((p,q)\) d'étiquette \(a\). On distingue les états initiaux par une flèche entrante et les états terminaux par une flèche sortante ou plus souvent par un double cerclage. L'automate ci-dessous a pour ensemble d'états \(Q=\{1,2,3\}\), deux états initiaux \(I=\{1,2\}\) et un état terminal \(T=\{3\}\).

La notion de déterminisme est liée aux chemins du graphe associé, une séquence d'étiquettes ne détermine pas nécessairement un unique chemin dans le graphe. C'est le cas pour les deux transitions \((1,a,1)\) et \((1,a,2)\) de l'automate ci-dessus. En remplaçant l'ensemble des transitions par une fonction, on obtient une version déterministe :
Un automate fini déterministe est un quintuplet \((\Sigma,Q,q_0,T,\delta)\) où \(\Sigma\) est un alphabet fini, \(Q\) est un ensemble fini d'états, \(q_0\in Q\) est l'état initial, \(T\subseteq Q\) est le sous-ensemble des états terminaux et \(\delta:Q\times \Sigma\rightarrow Q\) est la fonction de transition de l'automate.

Dans ce cas toute transition \((p,a,q)\) est uniquement déterminée par la relation \(q=\delta(p,a)\). L'unicité de l'état d'arrivée pour un état et une étiquette donnés justifie l'écriture \(p.a\) pour désigner l'état \(\delta(p,a)\) et ainsi si on a une autre transition \((q,b,r)\), on note avantageusement \(p.ab\) l'état d'arrivée \(\delta(q,\delta(p,a),b)\). Formellement le monoïde libre \(\Sigma^*\) agit à droite sur l'ensemble des états \(Q\).

Dans l'exemple ci-dessous, l'automate a pour alphabet l'alphabet binaire \(\Sigma=\{0,1\}\), pour ensemble d'états \(Q=\{A,B,C\}\) dont \(A\) est l'état initial et l'ensemble des états terminaux est \(T=\{A,C\}\).

Un mot \(u\in\Sigma^*\) est reconnu par un automate \(A=(\Sigma,Q,q_0,T,\delta)\) si \(q_0.u\in T\). Le sous-ensemble \(L(A):=\{u\in\Sigma^*\mid q_0.u\in T\}\) des mots de \(\Sigma^*\) reconnus par \(A\) est appelé langage reconnu par \(A\). On appelle futur d'un état \(q\) le langage \(L(q):=\{u\in\Sigma^*\mid q.u\in T\}\).

On a donc \(L(A)=L(q_0)\). Très concrètement, pour savoir si un mot \(u\in\Sigma^*\) est reconnu par un automate, il suffit de trouver un chemin d'état initial \(q_0\) étiqueté par \(u\) et dont l'état final est un état terminal dans le graphe. Dans l'exemple ci-dessus, les mots 01001 et 0101101 sont reconnus.

Démontrez que l'automate ci-dessus reconnaît les nombres entiers multiples de 3 quand ils sont écrits en binaire.

Par soucis de simplicité, on s'intéresse plus volontiers aux automates déterministes qu'aux automates non-déterministes, mais ce choix est légitimé par le fait que l'on peut toujours déterminiser un automate non-déterministe, au sens où l'on peut construire un automate déterministe qui reconnaît le même langage. C'est le rôle de l'algorithme des parties qui construit un automate \(A'=(\Sigma,Q',q_0,T',\delta)\), déterministe cette fois, à partir d'un automate non-déterministe \(A=(\Sigma,Q,I,T,F)\).

Le principe de construction de l'automate \(A'\) est simple, son ensemble des états \(Q'\) est l'ensemble \(2^Q\) des parties de l'ensemble \(Q\), l'état initial \(q_0\) est l'ensemble \(I\) des états initiaux de \(A\) et l'ensemble des états terminaux \(T':=\{P\in Q'\mid P\cap T\not=\varnothing\}\) contient toutes les parties qui contiennent un état terminal. La fonction de transition est définie pour toute partie \(P\in 2^Q\) et tout symbole \(a\in\Sigma\) par \[\delta(P,a):=\{q'\in Q\mid \exists q\in Q,\ (q,a,q')\in F\}.\] Cet automate est déterministe et complet par construction.

Pour justifier l'algorithme des parties, démontrez par récurrence sur la longueur des mots \(w\) que pour tout mot \(w\in\Sigma^*\), \(I.w = P\) si et seulement si \(P=\{q\mid \exists i\in I, i\stackrel{w}{\rightarrow} q\}\).

On dit qu'un automate est complet s'il existe une transition pour tout état de départ \(q\) et tout symbole \(a\), autrement dit si la fonction de transition \(\delta\) est définie partout. On complète facilement un automate qui n'est pas complet en lui adjoignant un état non-terminal appelé puit vers lequel on dirige tous les arcs manquants. Un état \(q\) est accessible s'il existe un chemin partant de l'état initial \(q_0\) menant à \(q\), coaccessible s'il existe un chemin partant de \(q\) et menant à l'un des états terminaux. Si on élimine tous les états d'un automate qui ne sont pas accessibles ou qui ne sont pas coaccessibles, on obtient un nouvel automate qui reconnaît le même langage (à prouver en guise d'exercice), il s'agit de l'automate émondé. Plus généralement on dira qu'un automate est émondé si tous ses états sont à la fois accessibles et coaccessibles.

Démontrez que l'automate émondé d'un automate reconnaît le même langage.
Appliquez l'algorithme des parties à l'automate non-déterministe suivant pour le déterminiser, puis émondez cet automate.
Combien d'états contient l'automate finalement obtenu ?
Deux états \(q\) et \(q'\) d'un automate complet sont dits équivalents au sens de Nérode, ce que l'on note \(q∼q'\), s'ils ont même futur, i.e. si et seulement si \(L(q)=L(q')\).
On montre aisément qu'il s'agit d'une relation d'équivalence sur Q. On est bien sûr tenté de ne conserver qu'un seul état par classe d'équivalence (qu'on appelle résiduel) pour simplifier l'automate mais encore faut-il s'assurer que cette relation d'équivalence est compatible avec la fonction de transition. Pour comprendre le problème potentiel de la compatibilité avec la fonction de transition, observons une partie d'un automate construit pour l'occasion :
Les états \(6\) et \(9\) ne sont pas équivalents puisque l'un est terminal, l'autre non. Si les états \(2\) et \(5\) étaient équivalents, on aimerait éliminer l'un d'entre eux, l'état \(2\) par exemple en raccrochant l'arc incident vers l'intérieur à l'état \(5\) mais la transition \((2,a,9)\) qui finissait la reconnaissance d'un mot disparaît au profit de la transition \((5,a,6)\) qui ne termine pas la reconnaissance d'un mot. Le lemme suivant nous montre qu'une telle situation est impossible :
Si \(q∼q'\), alors \(\forall u\in\Sigma^*\), \(q.u∼q'.u\)
Il faut donc montrer que si \(L(q)=L(q')\) alors \(\forall u\in\Sigma^*\), \(L(q.u) = L(q'u)\). Soit \(x\in L(q.u)\), montrons que \(x\in L(q'.u)\), l'autre inclusion sera satisfaite en échangeant les rôles de \(q\) et \(q'\). Si \(x\in L(q.u)\) alors \(ux\in L(q)\) puisque \(L(q.u)=\{x\in\Sigma^*\mid q.ux\in T\}\). Comme \(L(q)=L(q')\) on a \(ux\in L(q')\) ce qui entraîne \(q'.ux\in T\) et finalement \(x\in L(q'u)\).
On appelle automate réduit d'un automate A, l'automate noté A/~ dont l'ensemble des états est le quotient Q/~ de Q pour la relation d'équivalence de Nérode.
Un automate A qui reconnaît un langage \(L\) est dit minimal si tout autre automate qui reconnaît \(L\) contient au moins autant d'états que A.
Notons qu'à ce stade on ne peut parler de l'automate minimal au sens singulier défini, il est en effet possible qu'il existe plusieurs automates minimaux reconnaissant le même langage. Nous allons voir qu'il n'en est rien.

Supposons que l'on dispose de deux automates \(A\) et \(B\) qui reconnaissent un même langage \(L\) et notons \(A'\) et \(B'\) leurs automates réduits respectifs. Que peut-on dire de \(A'\) et \(B'\) ? Sont-ils isomorphes, i.e. existe-t-il une bijection entre les ensembles des états \(Q_{A'}\) et \(Q_{B'}\) qui préserve les transitions de \(A'\) et dont la réciproque préserve également les transitions de \(B'\) ? De manière surprenante, les automates réduits sont égaux et ne dépendent pas de l'automate initial, autrement dit un automate réduit est nécessairement l'automate minimal.

L'automate réduit d'un automate reconnaissant un langage \(L\) défini sur un alphabet \(\Sigma\) est unique.
Soit \(L\) un langage défini sur un alphabet \(\Sigma\). Considérons un mot \(w\in\Sigma^*\) et l'ensemble \(R(w):=\{x\in\Sigma^*\mid wx\in L\}\) des mots qui complètent \(w\) pour obtenir un mot du langage \(L\). Cet ensemble est indépendant de tout automate. Nous allons montrer que cet ensemble est égal à un résiduel.
Il existe un unique automate minimal.

Travail personnel

Vous devrez me renvoyer une archive .tgz à votre nom contenant les sources de vos programmes, les explications et les réponses aux questions pour le vendredi 19 décembre 2014.
Récupérez ce lexique.
  1. Rédigez un résumé du cours en quelques pages.
  2. Ecrivez le programme de réduction naïf d'un automate étudié en cours.
  3. Écrivez un programme qui crée l'arbre lexicographique correspondant au lexique.
  4. Écrivez une fonction de tri lexicographique qui reçoit en entrée une liste de mots et qui utilise l'algorithme de tri par paquet étudié en cours.
  5. Écrivez un programme qui réduit l'automate associé à cet arbre lexicographique en appliquant l'algorithme de Revuz.
  6. Calculez le taux de compression, c'est-à-dire le ratio entre la taille du lexique final et la taille du lexique initial.
Commentez impérativement les fonctions et vos programmes et écrivez un fichier lisezmoi.txt indiquant comment les utiliser.