6 Une combinaison des approches automatique et explicite
Après avoir présenté dans les chapitres précédents les différentes approches de transformation explicite, et après avoir proposé une méthode de transformation automatique, nous proposons maintenant un système de transformation permettant de répondre aux inconvénients et limitations des méthodes précédentes.
Le système de transformation que nous présentons dans ce chapitre combine la transformation automatique et les déclarations explicites.
6.1 Rappel des objectifs
Dans les chapitres 3 et 5 nous avons identifié les limites des approches explicite et automatique pour la conversion de documents. Nous rappelons maintenant les trois catégories d'applications identifiées au chapitre 2 en synthétisant les problèmes non résolus et en montrant le besoin d'une approche qui combine les techniques explicite et automatique.
Conversion de documents non structurés
La méthode explicite nécessite une déclaration extensive de la transformation des documents non structurés. Cette solution peut être envisagée dans certaines applications très spécifiques, mais ne peut pas être adaptée au cas général car les formats de documents non structurés sont très diversifiés.
Par ailleurs, les documents source n'ayant pas de structure générique définie, la méthode de transformation automatique proposée dans le chapitre 5 ne peut être utilisée telle quelle pour ces transformations.
Pour résoudre ce problème, nous proposons dans la section 6.5 une application de conversion de documents qui se fonde sur la structure spécifique de l'instance pour engendrer un arbre de types spécifique au document cible. Les informations de formatage des documents doivent être préalablement traduites au format XML afin de disposer d'une syntaxe unique quel que soit le format d'origine du document. Nous disposons ainsi d'une structure spécifique au document source qui est utilisée par l'algorithme de transformation automatique.
Le résultat mène à des solutions très peu pertinentes principalement à cause du mode de génération automatique de l'arbre de types source.
Ainsi dans le cas de cette application, il est nécessaire de compléter la technique de transformation automatique par des informations supplémentaires données par l'utilisateur qui mettent en relation les éléments du document source avec les types de la structure cible.
Transformations de documents structurés au cours de l'édition
C'est la classe de transformations pour laquelle la méthode automatique donne les résultats les plus pertinents. Ces transformations portant sur un nombre réduit d'éléments, les structures génériques mises en jeu sont de taille réduite et le nombre de correspondances potentielles entre les arbres de types source et cible est plus faible. De plus, lors de transformations effectuées « sur place », les types communs aux arbres source et cible limitent l'ambiguïté induite par la comparaison.
Cependant, les transformations effectuées ne sont pas toujours satisfaisantes, c'est en particulier le cas lorsqu'un élément « peu structuré » doit être transformé dans un type dont la structure est plus profonde, par exemple lors de la transformation d'une liste d'éléments (qui ne comporte qu'un niveau d'éléments) en tableau (qui est une structure à deux niveaux : lignes et colonnes). Il peut alors exister plusieurs relations de massif entre les structures source et cible.
Il serait souhaitable de pouvoir spécifier par un ensemble de règles quelle relation sera privilégiée lors de la comparaison des structures.
Conversions de documents entre structures génériques
La méthode de transformation automatique est peu performante pour la transformation de l'intégralité d'un document : la taille de l'arbre de types représentant la structure du document source peut s'avérer importante. Ce facteur fait croître le nombre de relations de massif possibles entre les structures génériques source et cible. En conséquence, la probabilité de trouver la transformation pertinente avec l'algorithme de transformation automatique est faible.
L'approche explicite semble plus adaptée à ce type de transformation, cependant elle nécessite des déclarations à la mesure de la taille des structures mises en jeu qui peuvent se révéler importantes.
Là encore, une approche mixte paraît souhaitable : utiliser l'algorithme de transformation automatique et permettre à l'utilisateur de corriger de manière interactive les imperfections de cette méthode. En mémorisant ces corrections, on peut espérer obtenir une transformation pertinente de l'ensemble des documents source appartenant à une même structure générique.
6.2 Principe de la méthode proposée
La méthode de transformation que nous présentons dans ce chapitre est fondée sur les transformations automatiques décrites dans le chapitre précédent. Son originalité par rapport aux méthodes de transformation explicites présentées dans le chapitre 3 réside dans l'importance prépondérante accordée à la part automatique de la transformation. Dans le système de transformation explicite d'Amaya présenté dans la section 3.4, nous avons introduit une part d'automatisme pour adapter localement les éléments dont la transformation n'est pas exprimée. Ces adaptations consistent principalement à créer ou supprimer un niveau de structure quand celui-ci est imposé ou interdit par le contexte dans lequel doit être inséré l'élément.
Le système de transformation que nous proposons ici est fondamentalement différent : la transformation n'est pas conduite par les expressions de transformations mais par l'algorithme présenté dans le chapitre précédent. Les déclarations ne font que modifier localement le comportement de l'algorithme pour diriger la comparaison sur une relation différente de la relation qu'il aurait trouvée par défaut.
Cette approche différente implique bien sûr une algorithmique adaptée qui sera présentée dans la section 6.4 mais également une méthode de spécification particulière. Les expressions de transformation associent un ensemble d'éléments de la structure du document source avec un noeud de l'arbre de types cible. Un ensemble de telles associations est appelé pré-couplage, il est défini dans la section 6.3.
La méthode de transformation présentée dans ce chapitre est fortement dépendante de la transformation automatique. Il est donc nécessaire de proposer une méthode de spécification intégrée au processus de transformation automatique. Nous développons ce point dans la section 6.5. Nous terminons ce chapitre sur les perspectives d'utilisation de cette technique de transformation dans des applications documentaires et donnons un exemple de structuration de documents XML pour l'éditeur Thot.
6.3 Pré-couplage
Un pré-couplage est un ensemble d'associations entre les noeuds des arbres de types source et cible utilisés pour la transformation. Le but d'un pré-couplage est de diriger l'algorithme de transformation automatique sur une relation de massif qui mette en relation les noeuds pré-couplés.
Dans cette section nous définissons précisément la notion de pré-couplage et proposons un langage permettant de spécifier des pré-couples.
6.3.1 Définitions
Pré-couple
Une relation liant un noeud d'un arbre de types source avec un noeud d'un arbre de types cible est appelée pré-couple.
La relation associant un élément avec le noeud représentant son type dans l'arbre canonique n'étant pas bijective. Un pré-couple a la propriété de spécifier le type cible d'un ensemble d'éléments de l'instance source.
Un noeud x de l'arbre de types source et un noeud x' de l'arbre de type cible sont pré-couplés si et seulement si il existe une relation de pré-couple p entre x et x' ; x = q(p) est alors appelé origine du pré-couple et x'= r(p) est appelé cible du pré-couple.
Pré-couplage
Un ensemble de pré-couples P = {p1, ..., pn) est un pré-couplage si et seulement si " (i, j) Î [1,n]´[1,n], q(pi) ¹ q(pj). Les noeuds origine des pré-couples composant un pré-couplage sont tous différents.
Un pré-couplage Pg d'un arbre de types A dans un arbre de types A' définit une fonction de pré-couplage notée g associant à chaque noeud origine de l'arbre de type source le noeud cible correspondant dans l'arbre de types cible. L'ensemble des noeuds origine d'un pré-couplage (le domaine de g) est noté Q(Pg).
6.3.2 Expression d'un pré-couplage
Pour permettre la ré-utilisation des pré-couples définis pour une transformation, ceux-ci doivent être mémorisés.
Pour permettre la ré-utilisation des pré-couples définis pour une transformation, ceux-ci doivent être mémorisés.Il doivent également pouvoir être exprimés quels que soient les arbres de types considérés. C'est dans ce but que nous proposons un langage d'expression de pré-couplages. Ce langage est basé sur la syntaxe XML. Cette syntaxe permet de décrire facilement les structures de documents (dans section 3.3.3.7 nous avons vu comment XSL se sert de XML pour décrire des fragments de structures de documents, avec les templates).
Nous décrivons la syntaxe de ce langage en l'illustrant à l'aide de la transformation d'un élément exercice en paragraphe présentée dans le chapitre précédent. Le couplage calculé par l'algorithme automatique est représenté dans la figure 48, en particulier le noeud énoncé de l'arbre source et couplé avec un noeud liste et le noeud solution est couplé avec un noeud groupe.
|
|
Figure 48 - Couplage calculé par l'algorithme de comparaison automatique
Supposons maintenant que l'on veuille que l'énoncé et la solution soient transformés en groupes, il faut alors pré-coupler le type énoncé et le type solution avec le type groupe. Le pré-couplage est représenté par les flèches rouges sur la figure 49.
|
|
Figure 49 - Pré-couples entre les arbre de type exercice et paragraphe.
Un pré-couplage est décrit par une structure d'éléments XML node. Cette structure est une projection de l'arbre de types source ne conservant que les noeuds appartenant aux branches comprenant un noeud de Q(P). Dans l'exemple cette structure comprend les noeuds exercice, énoncé et solution.
Les éléments correspondant aux noeuds source des pré-couples ont un ensemble d'éléments destnode parmi leurs fils qui définit le noeud cible du pré-couplage. Cet ensemble d'éléments est composé des noeuds ancêtres successifs compris entre la racine de l'arbre de types cible et le noeud cible du pré-couple. Ces noeuds sont présentés en bleu dans la figure 49.
La figure 50 présente l'expression du pré-couplage. Un élément XML precouples contient les éléments node décrivant les noeuds pré-couplés de l'arbre de type source. Cet élément porte impérativement un attribut target-type donnant le nom du type racine de l'arbre cible. L'élément precouples est composé d'un ou plusieurs éléments de type node correspondant aux racines des arborescences des types source. Chaque élément node porte impérativement un attribut type contenant le nom du type représenté par le noeud. S'il représente un noeud origine d'un pré-couple, un élément node contient une séquence d'éléments targetnode identifiant le noeud cible en donnant la descendance des éléments depuis la racine de l'arbre de types cible jusqu'au noeud cible du pré-couple. Les éléments node peuvent également contenir d'autre éléments node représentant leurs fils dans l'arbre de types source, permettant ainsi de définir des pré-couplages impliquant des descendants de noeuds pré-couplés.
<precouples targettype="paragraphe"> <node type="exercice"> <node type="énoncé"> <targetnode type="paragraphe"/> <targetnode type="titré"/> <targetnode type="corps"/> <targetnode type="paragraphe"/> <targetnode type="groupe"/> </node> <node type="solution"> <targetnode type="paragraphe"/> <targetnode type="titré"/> <targetnode type="corps"/> <targetnode type="paragraphe"/> <targetnode type="groupe"/> </node> </node> </precouples>
Figure 50 - Déclaration d'un pré-couplage
La syntaxe du langage présenté ici reprend l'idée de XSL qui consiste à décrire les structures de documents en utilisant le marquage. Mais à la différence de ce langage de transformation, nous décrivons ici des arbres de types et non des structures d'éléments car la localisation des types pré-couplés est relative aux arbres de types alors que les transformations XSL se fondent sur la structure des documents. De plus, nous n'associons pas à ces structures des règles de génération, mais l'identification d'un noeud dans l'arbre de types cible, pour cela, une séquence d'éléments est suffisante.
Les pré-couples pouvant être spécifiés de façon interactive, les expressions de ce langage doivent pouvoir être construites à partir des arbres de types. Contrairement aux patterns du langage XSL, la syntaxe XML présentée ici permet de représenter directement un arbre de types.
Notons que l'arbre de types source n'est pas représenté intégralement dans l'expression d'un pré-couplage, seules les branches contenant des noeuds origines d'un pré-couple sont nécessaires. Ainsi dans l'exemple précédent, le noeud titre n'est pas représenté dans l'expression du pré-couplage.
La syntaxe du langage des expressions de pré-couplage :
<!ELEMENT precouples (node+) >
<!ATTRLIST precouples
target-type CDATA #REQUIRED >
<!ELEMENT node ((targetnode)*, (node)*) >
<!ATTRLIST node
type CDATA #REQUIRED >
<!ELEMENT targetnode EMPTY >
<!ATTRLIST targetnode
type CDATA #REQUIRED >
L'exemple de la figure 50 montre que la syntaxe des spécifications de pré-couplage peut être complexe et réclamer des spécifications assez longues. Cela va à l'encontre des objectifs que nous nous sommes fixés dans le chapitre 2.
Il est également difficile de prévoir quels pré-couplages seront nécessaires pour la correction d'une relation de massif retrouvée par la comparaison d'arbres de types. Le pré-couplage permettant de compléter ou de préciser la relation trouvée par cette comparaison, il est logique que la spécification d'un pré-couplage intervienne suite à une première transformation automatique. Le mode d'utilisation de la méthode proposée dans ce chapitre est donc le plus souvent un processus cyclique impliquant la transformation automatique et la spécification explicite.
Pour ces deux raisons, nous proposons de n'utiliser ce langage que pour la mémorisation des pré-couples et d'intégrer la spécification de pré-couplage à l'application de transformation. L'utilisateur ne verra donc pas ce langage, mais pourra spécifier les pré-couples à travers une interface simple.
6.4 Comparaison de types avec pré-couplage
Nous proposons maintenant un algorithme de comparaison d'arbres de types canoniques prenant en compte un ensemble de pré-couples entre les noeuds de l'arbre source et les noeuds de l'arbre de types cible.
6.4.1 Principe de la comparaison
L'algorithme de comparaison doit prendre en compte une relation partielle de couples noeud source - noeud cible dans un processus de comparaison des arbres de types.
Pour cela, l'algorithme reprend l'automate présenté dans le chapitre 5, mais effectue un traitement particulier lorsque l'état courant contient l'indice d'un noeud pré-couplé. Ce traitement diffère selon la position du noeud cible du pré-couplage dans l'empreinte cible par rapport à l'indice définissant l'état courant. Il est également affecté par la relation entre le constructeur du type source et le constructeur du type cible du pré-couplage.
Ces deux facteurs interviennent de manière indépendante sur l'algorithme de comparaison : l'indice du type pré-couplé met en cause les caractères précédant ceux représentant les noeuds pré-couplés dans la source et la cible ; la relation entre les constructeurs influence la façon dont est comparée la descendance des types pré-couplés. Ces descendances sont représentées par les sous-chaînes délimitées par les caractères représentant le début et la fin des types pré-couplés dans les empreintes. Nous désignerons ces deux étapes de l'opération de pré-couplage par les deux termes :
- détermination du contexte d'un pré-couple et
- comparaison de types hétérogènes. Deux types sont hétérogènes s'ils sont définis par des constructeurs différents.
6.4.1.1 Contexte d'un pré-couple
Le contexte d'un pré-couple p entre les noeuds ui et vj est calculé lorsque l'automate de comparaison traite le caractère ui de la source qui représente le noeud origine du pré-couple. L'automate est alors dans un état (i, k).
Cet état ne peut être atteint que suite à une transition Mt, M1, M'1 (qui implique la reconnaissance du caractère d'indice i-1), ou M'1 (qui implique un retour en arrière après l'échec de la reconnaissance de la sous-chaîne contenant le caractère pré-couplé).
Examinons la comparaison effectuée par l'automate présenté dans le chapitre 5 relativement à l'indice du noeud pré-couplé dans l'empreinte cible. Dans la source, les caractères correspondant aux noeuds précédant le noeud pré-couplé (en vert) ont déjà été reconnus dans leur intégralité. Seule l'image par j des noeuds ancêtres (en bleu) a été traitée. Les images du noeud pré-couplé sont présentées en rouge. Plusieurs cas de figure peuvent se produire. Nous illustrons chacun d'entre eux en montrant la comparaison des empreintes source et cible avec un pré-couple correspondant au cas présenté :
- L'indice k du noeud cible est compris entre j et
l'indice du caractère de SV représentant le noeud
couplé avec le parent du noeud origine du pré-couple.
[Here is a Drawing]
- L'indice k du noeud cible est supérieur à celui du
caractère de SV représentant le noeud couplé
avec le parent du noeud origine du pré-couple.
[Here is a Drawing]
- Le noeud cible du pré-couplage a déjà
été exploré par l'automate, c'est à dire qu'il
existe un indice i' tel que 0<i'£i et l'état (i', g(i)) est dans la
suite des états menant à (i, j). Ce cas est illustré par
la configuration suivante :
[Here is a Drawing]
Ces trois cas de figure sont traités de la façon suivante :
- Le premier cas est le plus simple. L'indice dans l'empreinte cible doit simplement être incrémenté jusqu'à g(i). Le compteur de sommet de pile doit être incrémenté chaque fois que le caractère de sommet de pile est rencontré ; il doit être décrémenté chaque fois que le caractère inverse est rencontré.
- Dans le second cas, il n'est pas possible d'avancer l'indice de
l'empreinte cible jusqu'à l'indice du noeud cible du pré-couple
car cela conduirait à ne pas respecter la hiérarchie du couplage
et donc ne conduirait pas à une relation de massif.
Lorsqu'un noeud pré-couplé est rencontré dans ce contexte, supposons que la pile contienne (v1, (i1, j1), k1)(v2, (i2, j2), k2)...(vp, (ip, jp), kp). Soit n le plus petit indice compris dans [1..p] tel que a(jn) < j(g(i)), les noeuds correspondant aux éléments de la pile compris entre n et p compris (représentés en rouge ci-dessous) ne peuvent pas participer à un massif contenant g(i). En effet la bijection entre l'empreinte et l'arbre de type implique que ces noeuds ne soient pas des ancêtres du noeud cible du couplage. La comparaison reprend donc dans l'état (in,a(jn)+1) et les p-n éléments du sommet de la pile sont éliminés.
[Here is a Drawing]
Ce saut dans l'empreinte source est similaire à celui effectué par l'automate de comparaison automatique lorsqu'un massif n'a pas pu être trouvé dans une partie de l'empreinte (transition M'3).
- Dans le troisième cas, si le dernier noeud couplé (en
orange) de l'arbre cible et le noeud cible du pré-couple ont un
ancêtre commun dont le constructeur est liste (dont l'image est
représentée en rouge ci-dessous, le pré-couple
étant symbolisé par la flèche rouge), la comparaison peut
localement transgresser la règle de conservation de l'ordre des noeuds
car une instance de liste pourra être engendrée pour chaque
branche de l'arbre source.
Pour cela, tous les noeuds ascendants du noeud origine du pré-couplage qui ne sont pas ancêtres du noeud précédemment couplé dans l'arbre source doivent être reconsidérés. La comparaison reprend donc dans un état (i', j') où i' est l'indice associé à l'ascendant le plus éloigné du noeud source. Ce retour en arrière est symbolisé par la flèche verte.
Ainsi, dans l'exemple, il est possible de conserver le couplage de l'agrégat
[Here is a Drawing]{TT}et de la liste(T)précédant le noeud origine du pré-couple :
L'exemple ci-dessus montre que l'état dans lequel à été rencontré le pré-couple doit être mémorisé dans la pile pour être rétabli après la comparaison. Cette mémorisation permet la reconnaissance des noeuds ascendants du noeud origine du pré-couple ou le retour dans un état cohérent si la comparaison ne peut s'effectuer (flèche bleue). Ce retour en arrière dans l'empreinte cible est similaire au développement d'une récursion dans l'algorithme de comparaison du chapitre 5.
Si la condition d'existence d'un noeud de type liste dans les ancêtres du noeud pré-couplé n'est pas remplie, alors le pré-couple fait échouer la comparaison. Suivant la nature de l'application, il faut soit éliminer ce pré-couple et continuer la comparaison, soit arrêter la transformation avec un cas d'échec.
6.4.1.2 Comparaison de types hétérogènes
Lorsque le contexte de couplage a pu être déterminé et pris en compte dans l'algorithme, la descendance des noeuds pré-couplés doit également être comparée pour que la transformation puisse s'effectuer. Les pré-couples pouvant mettre en relation des types de constructeurs différents, la technique de comparaison diffère selon le constructeur du type source et le constructeur du type cible du pré-couple.
Dans le tableau 51, nous analysons les différents cas de figure pouvant se présenter lors de la spécification de pré-couples. Dans chaque cellule, les deux nombres représentent les arités respectives des types source et cible sur la première ligne, et des instances de ces types sur la seconde. Ainsi, les types définis par le constructeur liste ont une arité de 1 (un seul fils dans l'arbre de type), mais les instances sont des éléments dont l'arité est supérieure à 1. Inversement, les types définis par le constructeur choix ont une arité multiple (les alternatives du choix), mais leurs instances ont une arité égale à 1.
| Constructeur du type cible | Constructeur du type sourceListe | Choix | Agrégat |
|---|---|---|---|
| générique | 1, n | 1, n | 1, n |
| spécifique | n, n | n, n | n, n |
| générique | n, n | n, n | n, n |
| spécifique | 1, n | 1, n | 1, n |
| générique | n, n | n, n | n, n |
| spécifique | n, n | n, n | n, n |
Figure 51 - Relation entre les arités des types et des instances en fonction des constructeurs des types source et cible d'un pré-couple.
Dans le cas de la comparaison de types, l'arité des instance du type source doit être inférieure ou égale à celle du type cible. Ce critère élimine la possibilité de pré-couple entre un type défini par le constructeur liste ou agrégat avec un type défini par un constructeur choix.
Un type liste ne peut être pré-couplé avec un type agrégat qu'à la condition que toutes les instances du type liste aient une cardinalité inférieure à l'arité du type cible. Le modèle de types ne permettant pas de représenter la cardinalité des listes, ces pré-couple ne peuvent être utilisés que pour les comparaisons utilisant la forme réduite de l'empreinte source (cf. section 5.4.1). Si toutes les instances du type liste ont une cardinalité inférieure à l'arité du type agrégat, alors le noeud fils du type liste est comparé avec chacun des noeuds fils de l'agrégat. Si toutes ces comparaisons successives aboutissent, la transformation peut être réalisée.
Des pré-couples peuvent être définis entre un type source de constructeur choix et un type de constructeur liste. Une solution est trouvée à la condition que chaque noeud fils du noeud de l'arbre de type source soit la racine d'un massif du fils du noeud liste dans l'arbre de type cible. La comparaison avec l'empreinte source spécifique est plus adéquate car elle ne nécessite pas la reconnaissance d'un massif pour l'ensemble des alternatives d'un type choix, mais seulement de ceux qui sont effectivement instanciés.
Le dernier cas est celui de la comparaison d'un type source de constructeur choix et d'un type de cible de constructeur agrégat. Dans ce cas, chaque alternative du choix doit être un massif d'au moins un type composant l'agrégat. Comme dans le cas de la transformation en liste, l'utilisation des empreintes spécifiques permet de retrouver des solutions supplémentaires dans le cas où des alternatives de choix non instanciées font échouer la comparaison des empreintes génériques.
6.4.1.3 Algorithme
L'algorithme de comparaison avec pré-couplage
TraiterPreCouple utilise la fonction
Comparer(i,j) qui implémente
l'automate de comparaison automatique sur les sous-empreintes
délimitées respectivement par i, jU(jU-1(i))
et j, jV(jV-1(j)). L'algorithme prend en entrée une
liste de pré-couples, accessibles par la fonction
PCouple(i) qui retourne g(i) et un état
(i, j) tel g(i) soit défini, c'est à
dire que jU-1(i) est un noeud origine d'un pré-couple.
La fonction TraiterPreCouple est appelé par
l'algorithme de comparaison automatique lorsque l'indice i de
l'état courant correspond à un type pré-couplé.
Dans cet algorithme, la présence d'un pré-couple ayant pour
noeud origine jU-1(i) est testée à chaque
itération de la boucle. La fonction TraiterPreCouple
retourne l'état dans lequel doit reprendre la comparaison automatique
après détermination du contexte ou un état d'échec
de l'algorithme de comparaison qui appliquera une transition permettant de
traiter l'échec partiel. Cette fonction utilise également les
fonction Alpha et Inverse définies en 5.2.2.5.
Cet algorithme est composé de deux parties : la détermination du contexte de pré-couple implémente les trois cas présentés dans la section 6.4.1.1, la comparaison de type hétérogènes implémente l'analyse de cas de la section 6.4.1.2.
Fonction TraiterPreCouple (i, j) -> état
/*
traite un pré-couple U[i] -> V[PCouple(i)]
(i, j) est l'état de départ.
*/
{
/*
Détermination du contexte du pré-couple
*/
/* cas 3 : le noeud cible à déjà été
exploré */
si PCouple (i) £ j alors
/* recherche si il existe un type liste dans les */
/* ancêtres du dernier noeud couplé */
n := pile.etat.j;
tantque (n > 0 et n ¹ '(')
n := n - 1;
fintantque
si n ¹ 0 alors
empiler ('@', (i,j), Alpha (i));
j := n;
sinon
retourner echec;
finsi
/* cas 1 : la cible du pré-couple est avant le caractère */
/* fermant image du noeud en sommet de pile */
sinon si PCouple (i) < Alpha (pile.etat.j) alors
/* avance en j jusqu'à la cible du pré-couple */
tant que j < PCouple (i)
si v[j] = pile.symb alors
pile.compte := pile.compte + 1;
sinon si v[j] = Inverse (pile.symb) alors
pile.compte := pile.compte - 1;
finsi
fintantque
/* cas 2 : la cible du pré-couple est après le
caractère */
/* fermant image du noeud en sommet de pile */
sinon
/* dépile les noeuds ne pouvant participer au massif */
tantque Alpha (pile.etat.j) < PCouple (i)
i := pile.etat.i;
j := Alpha (pile.etat.j) + 1;
dépiler (pile);
fintantque
finsi
/*
Comparaison de types hétérogènes
*/
si j = PCouple (i) alors
si u[i] = v[j] alors
/* les deux types ont le même constructeur */
Comparer (i, j);
sinon si u[i] = '(' alors
/* le constructeur du type origine est la liste */
si v[j] = '[' alors
/* le constructeur du type cible est le choix */
retourner echec;
sinon si v[j] = '{' alors
/* le constructeur du type cible est l'agrégat */
i' := i;
j' := j;
succes := vrai;
/* compare le type fils du type liste avec chaque */
/* fils du type agrégat */
tant que sucess et j' ¹ Alpha (j)
succes := Comparer (i', j');
si succes alors
i' := i;
fintantque
finsi
sinon si u[i] = '['
/* le constructeur du type origine est le choix */
si v[j] = '(' alors
/* le constructeur du type cible est la liste */
i' := i;
j' := j;
succes := vrai;
/* compare chaque fils du type choix avec le type */
/* fils du type liste */
tant que succes et i' ¹ Alpha (i)
succes = Comparer (i', j');
si succes alors
j' := j;
fintantque
sinon si v[j] = '{'
/* le constructeur du type cible est l'agrégat */
/* existe-t-il un massif de chaque alternative du */
/* avec un type fils du type agrégat */
i' := i;
i'' := i;
j' := j;
succes := vrai;
tant que sucess et i' ¹ Alpha (i)
trouvé := Faux;
tantque Øtrouvé et j' ¹ Alpha (j)
trouvé := Comparer (i'', j');
si Øtrouvé alors
i'' := i';
finsi
fintantque
succes := trouve;
i' := i'';
j' := j;
fintantque
sinon si u[i] = '{'
/* le constructeur du type source est l'agrégat */
si v[j]='[' alors
/* le constructeur du type cible est le choix */
echec
sinon si v[j] = '(' alors
/* le constructeur du type cible est la liste */
/* existe-t-il une relation de massif entre chaque */
/* type fils de l'agrégat et le type de la liste */
i' := i;
j' := j;
succes := vrai;
tant que sucess et i' ¹ Alpha (i)
sucess := Comparer (i', j');
si sucess alors
j' := j;
fintantque
finsi
finsi
finsi
}
Figure 52 - fonction de transition associée à un noeud pré-couplé
L'algorithme de transformation semi-automatique intégrant la fonction de transition pour les noeuds pré-couplés construit ainsi un ensemble de couples entre l'arbre de types source et les noeuds du massif image dans l'arbre de types cible. Ce couplage peut être utilisé pour conduire la transformation des éléments source dans le type cible selon la méthode exposée dans le chapitre précédent (cf. section 5.3).
6.4.2 Pré-couplage et types récursifs
La méthode de transformation avec pré-couplage présentée dans la section 6.4.1 permet la spécification de pré-couples sur des arbres de types. Elle ne prend donc pas en compte le cas de la définition récursive du type cible. Nous proposons ici une adaptation de l'algorithme précédent pour prendre en compte ce cas de figure.
Pour prendre en compte des pré-couples de types définis récursivement il faut reconsidérer le cas 3 exposé plus tôt car le pré-couplage d'un noeud de l'arbre de types source avec un noeud déjà exploré de l'arbre de type cible ne conduit pas forcément à un échec. En effet, ce noeud est susceptible de participer à un couplage dans une branche récursive de la cible.
Ainsi, si dans un état (i, j) le noeud j(i) est couplé avec un noeud xj' tel que j(xj') £ j, alors l'algorithme avance dans l'empreinte du type cible jusqu'à rencontrer un caractère de récursion @ d'indice r tel que a(r) £ j(xj'). Cette récursion est développée en empilant l'état (i, r). On peut alors continuer depuis le cas 1 exposé en 6.4.1.1.
Si la comparaison des types hétérogènes pré-couplés échoue, le sommet de pile est dépilé et la stratégie de retour de l'algorithme non récursif est appliquée.
La comparaison avec pré-couplage et type récursif n'est pas complète : en effet l'algorithme ne retrouve pas tous les couplages possibles. Ceci se produit dans le cas où il faudrait développer plusieurs niveaux de récursion pour retrouver un indice j inférieur à j(xj'). Pour prendre en compte ce cas, l'algorithme doit explorer tous les développements récursifs possibles à partir de l'indice j dans l'empreinte du type cible. Cette recherche implique une complexité exponentielle de l'algorithme de comparaison. Par conséquent, nous limitons le développement à un seul niveau de récursion conformément à la règle énoncée dans la section 5.4.4 disant qu'on ne développe pas de types récursifs tant que l'on a pas progressé dans la reconnaissance de l'empreinte source.
6.5 Applications de la transformation avec pré-couplage
Cette section présente l'intégration dans les applications documentaires de la méthode de transformation avec pré-couplage. Dans un premier temps nous décrivons le module d'import des documents XML qui ne sont pas associés à une DTD connue par Thot. Dans une deuxième partie, nous discutons plus généralement de l'application de cette méthode pour répondre aux autres besoins de transformation.
L'application présentée dans la section suivante montre que l'information contenue dans le document source et exploitée par l'application peut être de deux natures : si la DTD du document source est connue, la transformation se fonde sur cette DTD pour générer
6.5.1 Importation de documents XML dans Thot
L'éditeur Thot permet de réutiliser des documents quelle que soit leur DTD d'origine, ou même des documents venant sans DTD connue. Pour réaliser cette fonction d'import, nous avons développé un module fondé sur la transformation avec pré-couplage. Cette application montre l'aptitude de cette méthode à remplir l'objectif de conversion de documents que nous nous étions fixés au début de ce travail.
Nous illustrons la description de cette application avec l'exemple de la transformation d'un document de type exercice en paragraphe défini dans la figure 38.
6.5.1.1 Principe de l'application
Thot permet de manipuler des documents XML conformes à un ensemble de DTD connues par le système (Rapport, Paragraphe, Exposé, etc.). Lorsque l'utilisateur ouvre un document XML qui référence une DTD inconnue, ou lorsqu'il ne référence pas de DTD, Thot propose à l'utilisateur de transformer le document pour le conformer à une DTD connue du système. Cette fonction de l'éditeur utilise la transformation avec pré-couplage et intègre une méthode spécification interactive de pré-couples.
Le processus de transformation du document XML source comporte plusieurs étapes :
- une empreinte est d'abord générée à partir de la structure du document source (étape représentée en bleu dans la figure 53) ;
- les empreintes sont ensuite comparées et la transformation automatique est effectuée (en vert) ;
- La solution proposée est désambiguisée par la spécification d'un pré-couple. Une nouvelle comparaison avec pré-couplage est alors effectuée et une nouvelle solution à la transformation est proposée (en rouge).
La troisième étape du processus est répétée jusqu'a ce que l'utilisateur juge la transformation pertinente, il peut alors éditer le document comme les autres documents Thot.
[Here is a Drawing]Figure 53 - Processus de conversion de documents XML en documents Thot
6.5.1.2 Étapes de la transformation
Le document XML est initialement affiché dans une vue qui présente la hiérarchie des éléments composant ce document (Figure 54). Le nom du type de chaque élément XML est présenté en gras et un filet vertical délimite son contenu qui peut être composé de texte ou d'autres éléments.
Figure 54 - vue de la hiérarchie des éléments XML
Le menu Transformation contient une entrée DTD cible... qui permet d'afficher un formulaire proposant de sélectionner la DTD dans laquelle le document doit être converti.
Une fois la DTD cible choisie, une première transformation automatique est effectuée. Pour cela, un arbre de types spécifique est créé à partir de la structure du document source. Cet arbre de type ne correspond pas toujours à une DTD (celle-ci n'étant pas connue par le système) et ne reflète que partiellement la structure du document, celle qui peut être automatiquement déduite et qui dépend de la source de l'information. Cette structure peut être fondée sur les caractéristiques physiques du document s'il provient d'une analyse d'image ou d'un traitement de texte. Elle peut aussi refléter une composante logique si le document est produit à partir de requêtes de bases de données ou de l'interrogation d'un moteur de recherche sur le Web.
Pour générer l'arbre de type, la procédure suivie consiste à parcourir la structure du document source et à générer les noeuds correspondants dans l'arbre de types en déterminant leur constructeur en fonction du nombre d'occurrences de l'élément correspondant. Chaque fois qu'un noeud de la structure source est parcouru, le traitement suivant est effectué :
- Si le noeud courant de l'arbre de type est nul :
- Si l'élément courant n'a qu'un seul fils, alors un noeud de constructeur choix est créé dans l'arbre de types comme fils du noeud père. Le fils de l'élément courant est parcouru avec le nouveau noeud comme noeud père et un noeud courant nul.
- Si l'élément à plusieurs fils de même type, alors un noeud de constructeur liste est créé dans l'arbre de types. Le premier fils de l'élément courant est d'abord parcouru avec un noeud courant nul. Les fils suivants sont ensuite parcourus avec le noeud de l'abre de type créé par le parcours du premier fils comme noeud courant.
- Si l'élément courant à plusieurs fils de types différents, alors un noeud de constructeur agrégat est créé. Les fils de l'élément courant sont parcourus avec un noeud courant nul.
- Si le noeud courant de l'arbre de types n'est pas nul alors :
- Si le constructeur du noeud courant est le choix :
- Si l'élément courant n'a qu'un seul fils et si le type de ce fils est identique au type de l'un des fils du noeud courant, alors le fils de l'élément courant est parcouru avec le fils du noeud de même type comme noeud courant.
- Si l'élément courant n'a qu'un seul fils de type différent de tous les fils du noeud courant, alors une nouvelle alternative du choix est créée et le fils de l'élément courant est parcouru avec un noeud courant nul.
- Si l'élément courant à plusieurs fils alors un noeud liste est inséré comme père du noeud courant et tous les fils sont traités comme s'ils étaient fils uniques (les deux cas précédents).
- Si le constructeur du noeud courant est la liste :
- Si les fils de l'élément courant ont tous un type identique à celui du fils du noeud liste, chcun de ces fils sont parcourus avec le noeud fils du noeud liste comme noeud courant.
- Sinon un noeud choix est inséré comme fils du noeud liste et chaque fils de l'élément courant est parcouru avec le noeud choix comme noeud courant.
- Si le constructeur du noeud courant est l'agrégat, alors :
- Si tous les fils du noeud courant respectent l'ordre de l'agrégat tel qu'il est défini dans l'arbre de types, alors chacun des fils est parcouru avec le noeud de l'arbre du même type.
- Sinon un noeud choix est inséré comme fils du noeud agrégat et chaque fils de l'élément courant est parcouru avec le noeud choix comme noeud courant.
- Si le constructeur du noeud courant est le choix :
Cette analyse par cas permet d'implémenter une fonction qui produit un arbre de types correspondant à la structure du document source, mais dont toutes les occurences des fils des éléments liste sont représentés par le même noeud.
Après que cet arbre de types ait été créé, la transformation s'effectue selon la méthode automatique donnée dans le chapitre 5. Le document résultant de cette transformation est affichée dans une vue formatée Thot (figure 55).
Figure 55 - Document résultant de la transformation automatique
Le document résultant de la transformation peut ne pas convenir à l'utilisateur. Ainsi dans l'exemple, l'élément source énoncé a été transformé en élément liste, chaque paragraphe composant l'énoncé ayant été transformé en item de liste. Un autre facteur de non pertinence est la transformation des éléments réponse (9h00 et 180 km) en éléments cite alors qu'il aurait été plus pertinent de les intégrer aux paragraphes des réponses.
L'utilisateur peut alors procéder à la correction de la transformation proposée. Pour cela, il spécifie des pré-couples de manière incrémentale pour raffiner ce résultat. La spécification de chaque pré-couple déclenche une nouvelle comparaison et le résultat est immédiatement affiché dans la vue du document cible.
La spécification d'un pré-couple se fait en deux temps :
- Dans un premier temps, le noeud source est sélectionné
« par l'exemple ». Pour cela l'utilisateur sélectionne un
élément particulier dans la vue du document source. Cet
élément est affiché en rouge vif et tous les
éléments du même type (plus précisément dont
le type porte le même nom) sont affichés en rouge foncé.
L'utilisateur a alors une perception de la sélection et de l'ensemble
d'éléments du même type canonique qui seront
impliqués par la transformation utilisant le pré-couple
Ainsi, pour spécifier le pré-couple entre les éléments réponse et le texte des item de liste, l'utilisateur sélectionne un des éléments du type réponse qui s'affiche en rouge vif (ici 9h00) et l'autre élément de même type (180 km) est affiché en rouge foncé. La désignation des éléments réponse est illustrée par la figure 56.
Figure 56 - Détermination du type origine d'un pré-couple
- Le second temps consiste à déterminer le(s) noeuds cible du
pré-couplage. Pour cela, l'utilisateur peut soit désigner un
élément déjà présent dans le document
cible, soit utiliser le menu d'insertion de Thot pour créer de nouveaux
éléments du type cible du pré-couple.
Dans l'exemple, il suffit à l'utilisateur de désigner un simple paragraphe pour spécifier la cible du pré-couple dont l'origine est le type réponse.
Lorsqu'un pré-couple est spécifié, une nouvelle transformation intégrant cette spécification est effectuée, le résultat est immédiatement affiché dans la vue du document cible Thot. Lorsque l'utilisateur juge la transformation pertinente, il peut fermer la vue du document source et éditer le document Thot de façon classique.
Pour accroître la souplesse et la facilité d'utilisation du système de transformation, nous avons ajouté deux fonctions permettant de modifier des pré-couples et de mémoriser les pré-couplages utilisés pour la conversion du document.
6.5.1.3 Modification des pré-couples
Au cours du processus de correction, il se peut qu'un pré-couple ne mène pas à une solution adéquate. Ceci peut être causé par une erreur de manipulation de l'utilisateur ou par un effet de bord non prévu lors de la spécification impliquant une mauvaise transformation d'éléments autres que ceux qui ont servi à spécifier le pré-couple.
Pour supprimer ces erreurs, il est nécessaire que l'utilisateur puisse visualiser, et éventuellement supprimer ou modifier un pré-couple entré précédemment.
Par définition du système de type, un élément est défini par un unique type canonique. Par conséquent, il ne peut exister qu'un unique pré-couple impliquant un élément du document source. Le pré-couple associé au type canonique de l'élément peut donc être affiché lors de la sélection de l'élément source. La perception d'un pré-couple est rendue par deux moyens :
- Le nom du type du noeud cible affiché à côté du noeud origine du pré-couple sélectionné.
- Les éléments définis par le type canonique cible du pré-couple sont affichés sur fond de couleur.
Le menu Transformation de la vue source permet de supprimer ou de définir un pré-couple. Lorsqu'un pré-couple est modifié ou supprimé, la transformation est immédiatement relancée, donnant ainsi à l'utilisateur un retour instantané de la commande effectuée.
6.5.1.4 Mémorisation des pré-couples
Lorsqu'une transformation est jugée pertinente par l'utilisateur, l'ensemble des pré-couples spécifiés durant la phase de spécification est mémorisée dans la syntaxe précédemment définie (cf. section 6.3.2). Le langage de pré-couplage permet de mémoriser le contexte dans lequel un pré-couple a été défini. Dans cette application, il permet de mémoriser le type de l'élément source et la DTD cible.
Lorsqu'un nouveau document sera ouvert, les expressions des pré-couplages mémorisées seront évaluées et pourront être utilisées lors de la comparaison initiale.
6.5.2 Pré-couplage et applications des transformations
La technique de transformation présentée dans les deux derniers chapitres repose sur le modèle d'arbre de types. Cette représentation des structures génériques des données ne sont pas liées à un environnement spécifique tel que la boîte à outils Thot.
Ainsi nous pouvons envisager de proposer un mécanisme de transformations de structure s'appuyant sur l'interface DOM [Wood 98] lui permettant de s'intégrer dans de nombreuses applications XML. La norme XML est de plus en plus utilisée et est en passe de devenir un format de représentation de données de référence. La prise en compte de cette norme est non seulement une priorité dans le développement des logiciels d'édition mais aussi une préoccupation dans d'autres domaines (bases de données, recherche d'information, publication Web). XML est la garantie de l'utilisation d'une syntaxe commune facilitant l'échange de documents entre applications. Si XML permet une compatibilité au niveau syntaxique, les structures sont spécifiques aux documents. Par exemple, les balises employées dans un document provenant d'un traitement de texte seront certainement différentes de celles employées dans un document résultant d'une requête sur une base de données.
6.6 Conclusion
Nous avons proposé dans ce chapitre une méthode de transformation combinant la transformation automatique et la méthode déclarative. La transformation automatique est basée sur des similarités entre la structure générique définissant les éléments source et la structure du type cible. Ce mode de transformation est uniquement fondé sur la structure. Les expressions de transformation spécifient des correspondances explicites entre certains types de la structure source et un sous ensemble des types cible. Ces correspondances permettent d'exprimer la sémantique de la transformation par la liaison des types d'éléments jouant des rôles similaires dans les structures des documents source et cible.
L'originalité de notre méthode est de donner une part prépondérante à la transformation automatique, des spécifications de relations appelées pré-couplage venant compléter et corriger cette transformation.
Nous avons défini un langage de spécification permettant de décrire ces pré-couplages. Nous avons ensuite proposé une méthode interactive et incrémentale qui complète le processus de transformation. En effet, l'intervention de l'utilisateur permet d'établir des correspondances localisées qui permettent de réduire les possibilités de couplage incorrect.
Nous avons finalement proposé plusieurs champs d'application de cette méthode de transformation répondant aux besoins que nous avons identifiés au début de ce travail.