Soutenance mémoire
Mots et langages
Un alphabet est un ensemble fini et non vide de symboles. La taille d’un alphabet Σ est le nombre de symboles qu’il contient, noté ∣Σ∣. Un mot est une séquence possiblement vide de symboles appartenant à un alphabet Σ. On représente par ε le mot vide. L’étoile de Kleene est la clôture réflexive et transitive d’un langage, noté Σ∗ pour l’alphabet Σ. Σ∗ est l’ensemble de tout les mots définissable à partir de l’alphabet Σ. On note u1 ⋅ u2 la concaténation de deux mots u1 et u2. La taille d’un mot u est le nombre de symboles qui le compose, noté ∣u∣. Les mots sont liés entre eux par une relation d’ordre totale <ord , telle que u <ord v ssi ∣u∣ < ∣v∣ ou u = v et u précède v dans l’ordre lexicographique. L’ensemble des positions pos(u) de ce mot est composé d’entiers i, compris entre 1 et ∣u∣, tel que u(i) correspond à la i-ième lettre de ce mot. Les mots ou symboles pourront parfois être présentés entre apostrophes, comme “a”, afin de les distinguer clairement de la phrase dans laquelle ils apparaissent. Les préfixes d’un mot u sont l’ensemble des quotients à gauche de u par l’opération de concaténation. Les suffixes quand à eux sont l’ensemble des quotients à droite d’un mot. En d’autres termes, nous pouvons définir deux fonctions prefixe(u) et suffixe(u) associant à un mot de Σ∗ un ensemble de mots des Σ∗ respectivement préfixes et suffixes de u par : prefixe(u) = {v ∣ v′∈ Σ∗, u = v ⋅ v′} suffixe(u) = {v′∣ v ∈ Σ∗, u = v ⋅ v′}
Equivalence et minimisation
Deux automates A et A′ sont dit équivalents s’ils reconnaissent un même langage, L(A) = L(A′). Cette notion d’équivalence peut être facilement étendue aux états q et p d’un même automate A si les langages reconnus à partir de ces états sont égaux, L(Aq) = L(Ap). S’il existe la possibilité de définir pour chaque langage régulier un unique automate le représentant, tester l’équivalence de deux automates revient à vérifier que leurs représentants partagent une même définition modulo le changement de noms des états. Une manière d’identifier un représentant unique est de passer un automate dans sa version minimale déterministe. La minimisation d’un automate se fait par la minimisation du nombres d’états qui le compose. Pour tout automate déterministe, nous pouvons nous ramener à son représentant minimal en suivant l’algorithme d’Hopcroft (1971) en O(n log(n)) connu aussi sous le nom d’algorithme des parties que nous ne détaillerons pas ici. Nous pouvons remarquer que cet algorithme ne s’applique pas aux automates non déterministes, déterminisme pouvant être obtenu en temps exponentiel dans la taille de l’automate. Le principal point qui nous intéresse ici est de montrer qu’en minimisant le nombre d’états, l’automate minimal obtenu est unique et peut être utilisé comme représentant canonique pour décider de l’équivalence mais aussi comme base nécessaire à un apprentissage.
Arbres d’arité bornée
Les arbres sont des structures de données récursives permettant d’ajouter aux mots une structure plus riche. Nous nous limiterons aux arbres finis, ordonnés et étiquetés. Nous pouvons distinguer deux principales familles d’arbres, les arbres d’arité bornée, où le nombre d’enfants de chaque noeud de l’arbre est fixé, et les arbres d’arité non bornée, ne limitant pas ce nombre. Malgré le fait que les arbres d’arité non bornée soient plus fréquents dans la pratique, la littérature porte le plus souvent sur le modèle d’arité bornée permettant de simplifier la manipulation des arbres et leur représentation à travers des automates comme nous allons le présenter maintenant.
Comment définir les automates ?
La recherche de bonnes notions d’automates pour les arbres d’arité non bornée peut se révéler complexe (comme le chapitre 8 du livre de Comon et al. (2007b) peut l’illustrer). Tout particulièrement, avoir de bonnes intuitions sur la notion de déterminisme de ces machines peut rapidement poser problème (Martens et Niehren, 2007). Pour manipuler ces arbres d’arité non bornée, deux types de solutions s’offrent à nous. La première, que nous verrons dans cette section, consiste à passer par l’encodage des arbres d’arité non bornée dans des arbres binaires. Les automates standards peuvent alors être appliqués. La deuxième solution, qui sera développée dans la section 1.4, passe par la linéarisation des arbres en mots imbriqués, séquences de balises ouvrantes et fermantes représentant les noeuds d’un arbre et leurs contenus. L’intérêt de passer par des codages en arbres binaires est de pouvoir appliquer les résultats déjà existants dans la littérature, pour les automates (et transducteurs) ascendants et descendants déterministes, sur les arbres d’arité bornée. Les codages choisis dépendent principalement des automates et transducteurs que nous souhaitons appliquer par la suite. Pour identifier les approches possibles, il est intéressant de ce concentrer sur la manière par laquelle il nous est possible de parcourir un arbre. Comme nous avons pu le voir précédemment, deux parcours s’offrent à nous, le parcours ascendant et le parcours descendant. Les informations associées à un noeud lors de l’exécution d’automates étant différentes selon l’ordre de parcours, il est nécessaire d’avoir à dispositions des encodages tenant compte de ces spécificités. Nous présentons ici le codage curryfié, adapté à un parcours ascendant, et le codage frère-fils, qui lui est destiné à un parcours descendant.
Codage binaire curryfié (ascendant)
L’idée du codage curryfié lui même nous vient du lambda-calcul (Curry et Feys, 1958), mais n’avait pas été adapté aux arbres avant les travaux de Carme et al. (2004a). Dans le domaine des langages fonctionnels, la curryfication correspond à la décomposition d’une fonction à plusieurs paramètres en une succession d’applications de fonctions à un seul paramètre. Une fonction f(a, b, c) sera remplacée par sa version curryfiée f′ tel que f(a, b, c) = ((f′(a))b)c. A la place d’une fonction possédant un nombre non fixée de paramètres, nous avons une succession de fonctions à un seul argument. La curryfication est étendue aux arbres, considérant chaque noeud comme une fonction, l’ensemble de ses fils étant ses paramètres, eux même des fonctions. Ainsi, à l’aide d’un opérateur @, nommé opérateur d’extension, f(a, b, c) donne l’arbre binaire f@a@b@c dans sa version infixée. L’opérateur @ est prioritaire à gauche, l’arbre représenté par l’exemple précédent est donc l’arbre @(@(@(f, a), b), c) dans sa version préfixée.
Linéarisation d’arbres d’arité non-bornée
Les documents xml stockés dans des fichiers, ou échangés sur flux, sont clairement des mots imbriqués, pouvant être obtenus par la linéarisation d’un arbre contenant des valeurs textuelles. Un exemple de mot imbriqué et de séquences d’arbres d’arité non-bornée qu’il représente sont données en figure 1.7. Toute séquence d’arbres d’arité non-bornée sur (T uΣ)∗ peut être linéarisée dans un mot imbriqué sur l’alphabet Σˆ. Les lettres internes (non associées à une ouverture ou fermeture) ne sont pas nécessaires ici, les valeurs de données textuelles étant ignorées. Un exemple est donné en Figure 1.8. La linéarisation s’obtient en parcourant l’arbre en profondeur. Cela peut se faire récursivement, en concaténant la balise ouvrante de la racine à la linéarisation successive des fils, et à la balise de fermeture de la racine.
Simplification des règles
En manipulant le formalisme de transduction choisi, nous montrons dans cette partie les différentes propriétés qui lui sont associées, et le rapport entres les différents modèles de transducteurs de mots existants. Les tms permettent la production d’une partie de la sortie lors de l’application des règles initiales et finales. Ce choix syntaxique découle directement de la sémantique de ces machines : le fait qu’une partie de la sortie peut être commune à toute sortie, et donc ne nécessite pas de lire le mot de l’entrée motive la présence d’une production initiale. Cependant rien ne nous empêche de nous ramener à un transducteur sans initialisation ou init-libre en utilisant comme état initial qi /∈ Q remplaçant chaque paire (q, w) ∈ init par une εtransition qi ε/wÐÐ→ q. L’ensemble des initialisations est maintenant un singleton init = {(qi, ε)}. Le fait de terminer la lecture d’un mot est aussi une information pouvant permettre la production d’une sortie supplémentaire. De la même manière,nous pouvons créer un modèle sans finalisation ou fin-libre en remplaçant l’ensemble des finalisations par un singleton fin = {(qf , ε)} tel que qf ∈/ Q. Cet état est atteignable uniquement par l’ensemble des ε-transitions {qε/wÐÐ→ qf ∣(q, w) ∈ fin}. Les ε-transitions permettent, comme vu précédemment, de produire de la sortie sans avoir besoin de lire l’entrée. Sans ces règles, la taille de la sortie serait bornée par une expression dépendant de la taille de l’entrée et de la taille des règles. La présence de boucles productives composées d’ ε-transitions, i.e. qε/wÐÐ→∗q ∈ rul avec w ≠ ε permet la génération de mots possiblement infinis. Cette génération ne peut être représentée sans l’aide d’ε-transitions. Un transducteur est dit ε-libre si il n’existe pas d’ ε-transitions. La déterminisation d’un transducteur nécessite de pouvoir passer dans un modèle ε-libre, ce qui est rendu impossible par l’existence de telles boucles.
|
Table des matières
Introduction
1 Automates
1.1 Mots
1.1.1 Mots et langages
1.1.2 Grammaires
1.1.3 Automates
1.2 Arbres d’arité bornée
1.2.1 Définition
1.2.2 Automates d’arbres
1.3 Arbres d’arité non-bornée
1.3.1 Definition
1.3.2 Comment définir les automates ?
1.3.3 Codage binaire curryfié (ascendant)
1.3.4 Codage binaire frère-fils (descendant)
1.4 Mots imbriqués
1.4.1 Définition
1.4.2 Linéarisation d’arbres d’arité non-bornée
1.4.3 Automates de mots imbriqués
1.4.4 Automate descendant
2 Transducteurs
2.1 Transducteurs de mots
2.1.1 Transducteurs rationnels
2.1.2 Transducteurs déterministes
2.1.3 Transducteurs déterministes avec anticipation
2.2 Transducteur d’arbres d’arité bornée
2.2.1 Transducteur descendants
2.2.2 Transducteur ascendant
2.2.3 Transducteur avec anticipation
2.2.4 Macro-transducteurs descendants
2.3 Transducteurs d’arbres en mots
2.3.1 Transducteurs descendants
2.3.2 Transducteurs ascendants
2.4 Transducteurs d’arbres d’arité non bornée
2.4.1 Transducteurs de mots imbriqués en mots
2.4.2 Transducteurs de mots imbriqués en mots imbriqués
3 Transformations XML
3.1 XSLT
3.1.1 XSLT en Pratique
3.2 Transducteurs et xslt
3.2.1 dST2W
3.2.2 Macro-Transducteurs et xpath
4 Équivalence de transducteurs séquentiels d’arbres en mots
4.1 Relation avec l’équivalence de morphismes sur CFGs
4.1.1 Exécution d’un dNW2W
4.1.2 Arbre syntaxique étendu
4.2 Relation entre dB2W et dT2W
5 Normalisation et minimisation des transducteurs descendants d’arbres en mots
5.1 dST2W travailleur
5.2 Caractérisation sémantique
5.2.1 Approche naïve
5.2.2 Décompositions et résiduels
5.2.3 Transducteur canonique
5.3 Minimisation
5.3.1 Minimisation des edST2Ws
5.3.2 Minimisation de dST2Ws arbitraires
5.4 Normalisation
5.4.1 Réduction de langages
5.4.2 Faire traverser un mot dans un langage
5.4.3 Déplacement de gauche à droite
5.4.4 Algorithme de normalisation
5.4.5 Bornes exponentielles
6 Apprentissage de transducteurs descendants d’arbres en mots
6.1 Théorème de Myhill-Nerode
6.2 Consistence des dST2Ws
6.3 Modèle d’apprentissage
6.4 Algorithme d’apprentissage
6.5 Décompositions, résiduels et équivalence
6.6 Echantillon caractéristique
7 Conclusion
7.1 Perspectives
Bibliographie
Télécharger le rapport complet
