5.2.1.1 Mise sous forme canonique

Le type d'élément tel qu'il est défini dans la DTD est d'abord mis sous forme canonique. La mise sous forme canonique d'un type se fonde sur la représentation sous forme de graphe de type et produit un arbre de types canonique.

Les opérations nécessaires à la mise sous forme canonique d'un graphe de types sont :

• L'élimination des types identité.
• La définition d'arbres finis : le graphe de type est transformé en graphe connexes sans cycles. Pour cela, les règles récursives sont traitées séparément (voir section 5.4.4). Le graphe de types est exploré et chaque branche est répliquée si elle a déjà été parcourue précédemment.
• La représentation systématique des éléments optionnels de la DTD. Ces derniers seront éventuellement ignorés par la relation de massif. Par contre, les éléments exclus ne sont pas représentés dans la branche d'arbre concernée par l'exclusion.

Les noeuds non terminaux des arbres canoniques sont étiquetés par les constructeurs choix, liste et agrégat. Les feuilles de ces arbres sont étiquetées par les types de base.

5.2.1.2 Ordre pour les arbres de types

L'algorithme de recherche de massifs nécessite la définition d'un ordre sur les arbres de types sans quoi le problème de la détermination de l'existence d'une relation de massif entre deux types est indécidable [Kilpeläinen 92].

Plusieurs ordres peuvent être proposés pour prendre en compte :

• les constructeurs des fils de la racine du sous-arbre de types,
• la profondeur du sous-arbre de type,
• le nombre de types compris dans le sous-arbre.

La relation d'ordre sur les constructeurs est notée <c.

Le choix de la relation d'ordre associée à l'arbre de types est déterminant pour la pertinence des relations de massif trouvées par l'algorithme de comparaison d'empreintes (voir section 5.6). Pour présenter l'algorithme, nous choisissons la relation d'ordre suivante sur les types canoniques d'une structure générique S :

1. si t Î BS (type de base) et t'Î CS (type construit) alors t < t'.
2. si t et t' Î CS avec t = c (t1,..., tm) et t' = c'(t'1,...,t'n ) alors

   t < t' si et seulement si :

   ---

   c<cc'

   ou

   c = c', m < n et " i Î [1,.., m], ti = t'i.

   ou

   c = c', $i Î [1,.., min (m, n)] tel que "j Î [1,.., i-1], tj = t'j et ti < t'i.

   ---

Cette définition implique le choix d'un ordre sur les types de base et sur les constructeurs. Pour les types de base, nous choisissons arbitrairement T (texte) < G(graphique) < S (symbole) < P (image), l'ordre des feuilles n'ayant pas de conséquence pour la comparaison. Les constructeurs sont ordonnés selon deux critères :

• le critère principal est l'arité des types qu'ils sont susceptibles d'engendrer : les types de constructeur liste ont une cardinalité égale à un, les types de constructeur choix et agrégat ont une arité supérieure à un.

  liste <c choix, agrégat.

• un critère secondaire est l'arité des instances des éléments des types concernés : les éléments dont le constructeur de type est le choix ont un unique fils, tandis que les éléments dont le constructeur de type est agrégat ont plusieurs fils.

  choix <c agrégat.

Cet ordre a pour but de comparer prioritairement les sous-arbres comprenant le plus petit nombre de noeuds, ceci pour trouver les relations de massifs les plus « compactes » possible.

5.2.1.3 Linéarisation des arbres de types canoniques

Une empreinte de type est ensuite construite à partir de l'arbre de types produit par la canonisation. Une empreinte d'un type est une chaîne de caractères contenant des parenthèses pour représenter les constructeurs de type (différentes sortes de parenthèses sont utilisées pour représenter les différents constructeurs) et des lettres pour représenter les types de base. Le parenthésage des empreintes reflète la structure générique du type. La figure 38 représente la DTD définissant le type exercice, l'arbre de type canonique correspondant et l'empreinte du type.

Dans les empreintes, le constructeur choix est représenté par des crochets, le constructeur liste par des parenthèses, le constructeur agrégat par des accolades. Les types de base sont identifiés par les lettres T pour le type texte, G pour le type graphique, S pour le type symbole mathématique, P pour le type image et R pour le type référence. Les autres types de base sont représentés par des lettres minuscules pour les types définis comme vides et par le caractère @ pour les pseudo-types de base récurrence.

Constructeur	Liste	Choix	Agrégat
Caractère	{	[	[	(	{

Type de base	texte	graphique	symbole	image
Caractère	T	G	S	P	a, b, c...	@

Type de base	référence	autres	récurrence
Caractère	R	T	G	S	P	a, b, c...	@

Un alphabet des constructeurs et des types de base est ainsi établi : S = {'{', '[', '(', 'T', 'G', 'S', 'P','a',...,'z'}, L'ensemble S des inverses est {'}', ']', ')', 'T', 'G', 'S', 'P','a',..., 'z'}. Les applications associant un noeud de l'arbre de types au caractère représentant son constructeur dans S sont notées e pour les types construits et b pour les types base.

Dans les empreintes, nous confondons les caractères représentant les types de base et leur inverses. En effet, les types de base étant des feuilles des arbres de types, l'opération de réduction effectuée par les transitions M1 et M1' de l'automate présenté dans la section 5.2.2 est unifiée pour être réalisée par la transition Mt.

---

DTD :

<!ELEMENT exercice   (titre, énoncé, solution) >
<!ELEMENT énoncé     (p | question)+           >
<!ELEMENT solution   (pa)+                     >
<!ELEMENT titre      (#PCDATA)                 >
<!ELEMENT p          (#PCDATA)                 >
<!ELEMENT question   (#PCDATA)                 >
<!ELEMENT pa         (#PCDATA | réponse)       >
<!ELEMENT réponse    (#PCDATA)                 >
<!ATTRLIST question   ident    ID    #REQUIRED >
<!ATTRLIST réponse    ident    ID    #REQUIRED >
<!ATTRLIST exercice   niveau   CDATA  "1"      >

Arbre de types :

• {exercice}
  • titre
    • T
  • (énoncé)
    • [énoncé#1]
      • p
        • T
      • question
        • T
  • (solution)
    • [pa]
      • T
      • réponse
        • T

Empreinte :

{T([TT])([TT])}

---

Figure 38 - DTD, arbre de types et empreinte du type exercice

La définition donnée des empreintes de types est proche de celle des mots de Dyck. La différence réside dans la représentation des noeuds terminaux par un caractère unique.

Définition

L'empreinte générique d'une forêt d'arbres de types est un mot défini par les règles suivantes :

1. w = b(x) si x Î BS
2. w = e(x) w' e(x) w'' si x Î CS et w' et w'' sont les empreintes respectives des enfants et des successeurs de x.

Comme pour les mots de Dyck, une bijection f est définie entre les arbres canoniques et les empreintes. Remarquons que :

• À tout arbre canonique A du système de types des documents structurés, on associe un mot unique F(A) Î D(S) définie par : F(A) = F0(r(A)) où r(A) est la racine de l'arbre A et F0 l'application de A dans D(S), elle-même définie récursivement par :F0(x) = e(x)[Here is a formula]F0(y) e(x)

  (si x est une feuille : F0(x) = b(x)).

• L'application F est une bijection de A°, l'ensemble des arbres canoniques de types sur l'ensemble D(S).
• À tout noeud x d'un arbre canonique A on peut associer un unique couple d'entiers (i, j) indices respectifs dans F(A) de e(x) et e(x) (pour les noeuds terminaux, on associe le couple (i, i) où i est l'indice de b(x)). Ces indices sont ceux permettant la construction de F-1. On notera i = jA(x) et j = jA(x) (et lorsqu'il n'y a pas ambiguïté i = j(x) et j = j(x). Ces deux applications sont injectives.
• L'application a = j o j-1 qui pour un noeud x associe l'indice de e(x) à celui de e(x) dans F(A) est bijective. a associe le caractère « parenthèse ouvrante » associé à un noeud avec le caractère « parenthèse fermante » associé au même noeud.

Un tableau de références vers les noeuds de l'arbre canonique de types est construit simultanément à l'empreinte. Ce tableau est utilisé lors de la génération des éléments transformés pour lier un indice de l'empreinte au type canonique qu'il représente. Il implémente[Here is a formula] (voir section 5.3).

5.2.2.1 Principe de la comparaison

La comparaison des empreintes de types pour la recherche de massif se fait à l'aide d'un l'automate à pile.

À chaque couple d'indices (i, j) des empreintes source et destination est associé un état de l'automate. À chaque état, l'automate compare les caractères ui et vj et effectue une transition vers un nouvel état. Une pile permet de mémoriser les caractères de S rencontrés dans l'empreinte cible alors que leur image par a n'a pas encore été rencontrée.

L'état initial (1, 1) est celui associant les indices représentant deux types de plus haut niveau (deux premiers caractères des empreintes). Les états terminaux sont ceux associant l'indice de la parenthèse fermante du type source de plus haut niveau (|u|+1) avec un indice quelconque de l'empreinte destination (l'ensemble des indices de l'empreinte source à été parcouru si et seulement un massif à été trouvé). La pile contient des triplets (caractère, état de retour, compteur) définis comme suit :

• Le caractère est la parenthèse ouvrante (vj) correspondant à l'état courant lorsque le triplet à été empilé.
• L'état de retour (s) est utilisé pour les retours arrière en cas d'échec d'une solution partielle.
• Le compteur (k) totalise les parenthèses ouvertes identiques au symbole de sommet de pile depuis qu'il à été empilé.

5.2.2.2 Automate de comparaison

La comparaison des empreintes de types pour la recherche de massif se fait à l'aide de l'automate à pile {Q, A, Y, qinit, Qfin, M} :

• Ensemble des états : Q = [1, |u| + 1]N ´ [1, |v| + 1]N
• Alphabet d'entrée : A = S(u) È S(v)
• Alphabet de pile :

  Y = S(v) ´ ([0, |u| + 1]N ´ [0, |v| + 1]N) ´ [0, |v| + 1]N

• État initial : qinit = (1, 1)
• Symbole initial de la pile : e
• Ensemble des états terminaux : Qfin = {(|u| +1, j) ½ j Î [1, |v| +1]N}
• Mouvements élémentaires :
  M = Mt È M1 È M1' È M2 È M3 È M'3 È M4 È M5 où chaque transition est définie par un tuple {état initial, caractère d'entrée dans l'empreinte cible, sommet de pile initial, état suivant la transition, sommet de pile suivant la transition} et par un ensemble de conditions sur l'état initial et le sommet de pile :
  • La transition Mt est activée lorsque les symboles source et cible correspondant à l'état courant sont des symboles de base. On progresse sur les deux empreintes à la fois.Mt = {(i, j), vj, (y, s, k), (i+1, j+1), (y, s, k)}conditions : ui = vj , ui Î B

  • La transition M1 est activée lorsque les symboles source et cible coïncident entre eux et avec l'inverse du symbole en sommet de pile, le compteur étant égal a 0. Cette transition est activé lorsqu'un type et sa descendance a été reconnu. L'automate passe alors de l'état (i, j) à l'état (i+1, j+1) en dépilant. On progresse sur u et v.

    M1 = {(i, j), vj, ([Here is a formula], s, 0), (i+1, j+1), e}

    condition : ui = vj

  • La transition M'1 est déclenchée lorsque les symboles source et cible coïncident entre eux et sont des parenthèses ouvrantes. Cette transition est activée lors de la reconnaissance du constructeur d'un type, avant d'inspecter la descendance. On passe alors dans l'état (i+1, j+1) en empilant le symbole reconnu. On progresse sur u et v.

    M'1 = {(i, j), vj, (y, s, k), (i+1, j+1), (y, s, k)(vj, (i, j+1), 0)}

    conditions : ui = vj, y ¹ vj-1

  • La transition M2 est activée lorsque les symboles source et cible coïncident entre eux et sont des parenthèses fermantes. Le compteur de pile n'étant pas nul, la parenthèse ouvrante correspondante dans la cible n'a pas été reconnue (transition M'1). On passe dans l'état (i, j+1) en décrémentant le compteur de pile. On progresse sur v.

    M2={(i, j), vj, ([Here is a formula], s, k), (i, j+1), ([Here is a formula], s, k-1)}

    condition : k ¹ 0

  • Les transitions M3 et M'3 sont activées lors que le symbole cible est l'inverse du symbole de sommet de pile, les symboles source et cible étant différents. Ces transitions sont déclenchées lorsque l'algorithme n'a pas pu trouver de massif dans une sous-arborescence d'un type.

    La transition M'3 mène dans l'état défini par l'indice source de l'état empilé et dont les deux indices ont été incrémentés. L'indice cible de l'état empilé est incrémenté. On progresse sur u par rapport à l'état dans lequel on a engagé la comparaison (état empilé). Cet état différencie notre automate de celui proposé par Frilley. Nous verrons dans la démonstration du théorème 1 comment cet état permet de reconnaître le massif que l'automate de Frilley ne reconnaît pas (cf. section 5.1).

    M'3={(i, j), vj, ([Here is a formula], (i', j'), 0), (i'+1, j'), ([Here is a formula], (i', j'+1), 0)}

    condition : ui ¹ vj

    Le transition M3 est activée lorsque les transitions M'3 successives n'ont pas pu mener à une solution (l'indice j est égal à l'indice de l'état de retour empilé). Cette transition mène à l'état suivant (en j) l'état empilé. Si (i, j) est l'état courant et (i', j') l'état de retour, le nouvel état est (i, a-1(j'+1)+1). Le sommet de pile est dépilé. On progresse sur v par rapport à l'état dans lequel on a engagé la comparaison (état empilé).

    M3={(i, j), vj, ([Here is a formula], (i', j'), 0), (i', a-1(j'+1)+1), e }

  • La transition M4 est activée lorsque les symboles source et cible ne coïncident pas et que le symbole cible est le même que le symbole stocké sur le sommet de la pile (ouvrant). Le compteur de pile est alors incrémenté et on passe à l'état (i, j+1). On progresse sur v.

    M4={(i, j), vj, ([Here is a formula], s, k), (i, j+1), ([Here is a formula], s, k+1)}

    condition : ui ¹ vj

  • La transition M5 est activée dans les autre cas, le symbole source ne correspond ni au symbole cible, ni au sommet de pile, ni à son inverse. On progresse sur v.

    M5={(i, j), vj, ([Here is a formula], s, k), (i, j+1), ([Here is a formula], s, k)}

    condition : ui ¹ vj, y ¹ vj-1, y ¹ vj

5.2.2.3 Un exemple de comparaison

Pour illustrer les transitions de l'automate prenons l'exemple de la comparaison de l'empreinte du type exercice avec celle du type paragraphe donnée dans la figure 39.

---

DTD :

<!ELEMENT paragraphe
         (simple|cite|groupe|liste|titré)>
<!ELEMENT simple           (#PCDATA)     >
<!ELEMENT cite             (#PCDATA)     >
<!ELEMENT groupe           (paragraphe)+ >
<!ELEMENT liste            (item)+       >
<!ELEMENT item             (paragraphe)+ >
<!ELEMENT titré            (titre, corps)>
<!ELEMENT titre            (#PCDATA)     >
<!ELEMENT corps            (paragraph)+  >

Empreinte :

[TT(@)((@)){T(@)}]

---

Figure 39 - DTD et empreinte du type Paragraphe

L'empreinte du type paragraphe contient des symboles '@' marquant les définitions récursives de types. Dans un premier temps nous considérerons des développements récursifs nécessaires à la correspondance, la section 5.4.4 présente une méthode pour traiter les types récursifs. En développant les récursions nécessaires, l'empreinte du type paragraphe devient :

[TT(@)((@)){T([TT([TT(@)((@)){T(@)}])(([TT(@)((@)){T(@)}])){T(@)}])}]

Le déroulement pas à pas de cet exemple est présenté sous la forme des 2 chaînes placées l'une sous l'autre de telle sorte que les symboles reconnus de la source soient alignés verticalement avec le symbole correspondant de la cible. Les symboles * représentent les indices de progression dans chaque empreinte. À chaque étape nous donnons également l'état de la pile.

La comparaison commence sur l'indice 1 des deux empreintes avec une pile vide :

*
{T([TT])([TT])}
[TT(@)((@)){T([TT([TT(@)((@)){T(@)}])(([TT(@)((@)){T(@)}])){T(@)}])}]
*
Pile : e

Une suite de transitions M5 mène à l'état (1,12).

           *
           {T([TT])([TT])}
[TT(@)((@)){T([TT([TT(@)((@)){T(@)}])(([TT(@)((@)){T(@)}])){T(@)}])}]
           *
Pile : e

Ensuite, la suite de transitions M'1, Mt, M'1, M'1, Mt, Mt conduit à l'état (7, 18) en empilant les parenthèses ouvrantes rencontrées avec les états correspondant :

                 *
           {T([TT])([TT])}
[TT(@)((@)){T([TT([TT(@)((@)){T(@)}])(([TT(@)((@)){T(@)}])){T(@)}])}]
                 *
Pile : ('{',2,13,0) ('(',4,15,0) ('[',5,16,0)

Une suite de transitions M5 et une transition M4 (état 7, 19) mènent à l'état (7,35), le compteur du sommet de pile n'étant pas nul, il est décrémenté (transition M2).

                                   *
           {T([TT                  ])([TT])}
[TT(@)((@)){T([TT([TT(@)((@)){T(@)}])(([TT(@)((@)){T(@)}])){T(@)}])}]
                                   *
Pile : ('{',2,13,0) ('(',4,15,0) ('[',5,16,1)

Une suite de transitions M5, M4 et M2 mènent à l'état (7, 66).

                                                                 *
...{T([TT                                                ])([TT])}
...{T([TT([TT(@)((@)){T(@)}])(([TT(@)((@)){T(@)}])){T(@)}])}]
                                                                 *
Pile : ('{',2,13,0) ('(',4,15,0) ('[',5,16,0)

Dans l'état (7, 68) le symbole cible est identique à l'inverse du symbole de sommet de pile et le compteur de pile est nul, la concordance démarrée à l'état (1, 12) est complète. Mais la transition M3 déclenchée dans l'état suivant provoque un retour à l'état (2, 13)

                                                                   *
...{T([TT                                                ])([TT])}
...{T([TT([TT(@)((@)){T(@)}])(([TT(@)((@)){T(@)}])){T(@)}])}]
                                                                   *
Pile : ('{',2,13,0)

L'état de retour est alors changé en (2, 14) et la comparaison se poursuit.

             *
           { T(    [TT])([TT])}
[TT(@)((@)){T([TT([TT(@)((@)){T(@)}])(([TT(@)((@)){T(@)}])){T(@)}])}]
             *
Pile : ('{',2,14,0)

Après avoir reconnu une autre parenthèse et un autre crochet, la transition M1 valide la reconnaissance du type choix.

                                   *
           {   T ([TT              ])([TT])}
[TT(@)((@)){T([TT([TT(@)((@)){T(@)}])(([TT(@)((@)){T(@)}])){T(@)}])}]
                                   *
Pile : ('{',2,14,0) ('(',4,20,0) ('[',5,21,0)

L'algorithme se poursuit jusqu'a ce que l'intégralité de l'empreinte source ait été parcourue (succès de la reconnaissance) ou que la pile soit vide alors que l'instance source n'a pas été entièrement parcourue (échec de la reconnaissance).

                                                                   *
           {   T ([TT              ])( [TT              ] )        }
[TT(@)((@)){T([TT([TT(@)((@)){T(@)}])(([TT(@)((@)){T(@)}])){T(@)}])}]
                                                                   *

Ici la comparaison s'est terminée avec succès et une relation de massif à été trouvée entre les structures des deux types d'éléments. La figure 40 montre la mise en correspondance entre les noeuds de l'arbre de types source et l'arbre de types cible. Les noeuds de l'arbre cible présentés en rouge sont les noeuds image de la relation de massif.

[Here is a Drawing]

Figure 40 - Types mis en correpondance par la transformation automatique

5.2.2.4 Validité de l'automate

Nous montrons maintenant la consistance et la complétude de l'automate de comparaison d'empreintes de types non récursifs.

Théorème 1

---

Désignons par L(u, v) le langage reconnu par l'automate à pile précédemment défini, Alors L(u, v) ¹ Æ si et seulement si U Í V

---

Preuve

Nous allons faire la démonstration par récurrence sur le cardinal |v| à u fixé.

Remarquons qu'à cause des mouvements de M5, L(u,v) est non vide si et seulement s'il contient le mot v lui-même.

Remarquons également qu'en tout état (i, j) atteignable de l'automate, nécessairement i £ j. Ceci entraîne d'une part que les mouvements de M3 mènent toujours en état (h, k) tel que h < i (l'état précédent étant (i, j)) et d'autre part que si |v| < |u|, il vient |v| < |u| - 1 et par suite aucun état terminal ne peut être atteint (puisque l'automate se bloque sur un état (i, j) et que, dans ce cas, i £ j £ |v| + 1 £ |u| + 1).

Nous supposerons donc que |v| ³ |u|, ce qui permet de commencer la récurrence en |u| = |v|.

¨ Si |u| = |v|, Supposons d'abord que U Í V. Dans ce cas U º V, ce qui entraîne la succession de mouvements suivants (qui sont tous dans M1 È M1' È Mt) :

(vi R|v|-i+1(v),(i, i),( y (c, s, 0)))® (R|v|-i+1(i+1, i+1), (y Q ((c, s, 0)(vi ,(i, j) ,0)))

Les empreintes étant des chaînes parenthésées et par la relation d'absorption Q définie par les transitions M1 , M1' et Mt , l'automate arrive donc après |u| mouvements, en la configuration :

(e, (|u|+1, |u|+1), e)

Il s'agit d'un état terminal et le mot v a été reconnu donc L(u,v) ¹ Æ.

Réciproquement, si l'automate reconnaît au moins un mot w, alors il reconnaît le mot v et il est parvenu en un état terminal, celui-ci ne pouvant être que de la forme : (|u|+1, |u|+1) puisque |u| = |v|. Nous en déduisons aussi que |v| = |u|.

D'après le fonctionnement de l'automate ceci ne peut se produire que si l'on a exécuté une suite de mouvements élémentaires de la forme :

(vi R|v|-i+1(v),(i, i), (y (c, s, 0)))® (R|v|-i+1(v), (i+1, i+1), (y Q ((c, s, 0)(vi ,(i, j) ,0))

Rn(v) étant le suffixe d'ordre n de l'empreinte v.

Cette suite n'est réalisable que si, pour tout indice i, ui = vj. Ce qui permet de conclure que u = v = w et par suite que U º V (seuls les mouvements élémentaires de M1ÈM1'ÈMt font avancer simultanément i et j) et donc U Í V .

¨ Supposons le résultat établi à un rang |v| = k ³ |u| et montrons-le au rang supérieur :

Remarquons d'abord que si L(u, v) ¹ Æ, alors l'automate a réussi à atteindre un état terminal par une suite d'états q1 = (i1, j1),...,qk = (ik, jk) en reconnaissant le mot v qui est aussi dans le langage reconnu.

On construit alors l'ensemble E :

E = {qh = (ih, jh) ½ ih+1 = ih + 1 et " h' ¹ h, ih' = ih Þ jh' < jh}

Supposons qu'il existe deux couples (ih, jh) et (ih', jh') dans E tels que ih = ih' et jh ¹ jh'. Alors, par définition de E jh' < jh et par croissance des indices jh < jh' ce qui est absurde. D'autre part, pour tout indice i Î [1, |u|], il est clair qu'il existe un indice j tel que (i, j) Î E puisque l'on atteint un état terminal.

Donc E définit une application f de {1,..., |u|} dans {1,..., |v|} telle que vf(i) = ui pour tout i (en effet le mouvement effectué en l'état (i, f(i)) ne peut conduire qu'en l'état (i+1, f(i)+1), par définition de E, ce qui implique que ce mouvement est dans M1 È M1' È Mt ).

Remarquons que la suite j1,..., jk est strictement croissante par construction de l'automate, en effet le retour sur j occasionné par la transition M3' implique qu'aucun élément de E ne comprenne un indice j qui soit compris entre l'indice de départ et l'indice résultant de la transition. Donc la sous-suite des indices jh pour lesquels il existe ih tel que (ih, jh) Î E est elle-même croissante (strictement).

Supposons alors qu'il existe dans E deux couples (ih, jh) et (ih', jh') tels que ih > ih' et h < h'. Alors comme l'automate parvient en état terminal (l'état qk) il existe nécessairement un indice l > h' tel que ih = il. Comme l > h', l > h et donc nécessairement jl > jh, la suite (j1, j2,..., jk) étant croissante. Mais ceci est contradictoire avec le fait que (ih, jh) Î E. Donc la sous-suite des indices ih pour lesquels il existe jh tel que (ih, jh) Î E est croissante. Ce qui nous permet de conclure que l'application f est strictement croissante (ce qui implique d'ailleurs qu'elle est bijective sur son image).

Posons m = jV-1o f o jU. Par construction de f, ui = vf(i) pour tout i, donc, par définition des applications jU et jV, e'(m(x)) = e(x) pour tout xÎU.

Soit y = jV o jV-1o f o jU et m = jV-1o y . Par construction m = m.

Analysons maintenant les mouvements de M1, M2 et M4 :

Si (ih, jh) Î E, avec uih Î C, ce couple est associé à un autre couple (ih', jh') Î E dans un mouvement de M1 (l'appartenance de ce couple à E résulte de celle de (ih, jh)). Par construction de l'automate, il vient : ih' = a-1(ih). Si le compteur de pile est nul, on a aussi exactement jh' = a-1(jh). Si le compteur n'est pas nul, cette dernière égalité n'est pas vérifié et on a seulement : jh' £ a-1(jh). Mais, si ql = (il, jl) désigne l'état qui suit exactement qh' dans la liste d'états de E, il vient aussi : jh' £ a-1(jh) £ jl (sinon il y aurait eu empilement et non incrémentation du compteur).

Or, par définition de f et de y, jh' = f(ih') et

a-1(jh) = jVo jV-1(jh) = y (ih)

Donc comme f est croissante, y l'est aussi. Et, par suite m est aussi croissante,

Si x et y sont deux noeuds de l'arbre U comparables pour l'ordre partiel de cet arbre, alors (avec x £ y) :

jU(x) £ jU(y) £ jU(y) £ jU(x)

ce qui implique, par croissance de l'application y, que :

y(jU (x)) £ y(jU (y)) £ y(jU(y)) £ y(jU(x))

que l'on peut écrire sous la forme

jV(m(x)) £ jV(m(y)) £ jV(m(y)) £ jV(m(x))

et, comme m = m :

jV(m(x)) £ jV (m(y)) £ jV (m(y)) £ jV (m(x))

Donc m(x) et m(y) sont aussi comparables dans V et se comparent dans le même ordre.

On vérifie de même que si x et y sont incomparables dans U, alors ils restent incomparables dans V, ceci résultant de l'inégalité :

jU (x) £ jU (y) £ jU (y) £ jU (x)

Donc m est bien un isomorphisme de U sur m(U) et donc U Í V ·

Réciproquement montrons que si U Í V alors langage L (u, v) n'est pas vide.

Il eiste au moins un noeud x0 Î V tel que U Í V-{x0}. On choisit alors un tel noeud maximisant la fonction j(x0) et l'on considère l'automate construit sur les deu arbres U et V' = V - {x0}. La maimisation de la fonction j(x0) peut conduire à le détermination de x0 comme racine de l'arbre V. C'est précisément le cas dans le contre exemple de l'automate de Frilley donné en 5.1. Nous expliquons dans la suite de cette démonstration comment la transition M'3 introduite permet de traiter le cas où le 0 déterminé par maximisation est égal à la racine de V.

Nous considérons donc dans un premier temps que l'ensemble V' est bien un massif de V puisque x0 est différent de la racine.

Comme U Í V', le langage reconnu par cet automate contient au moins F (V'), celui-ci étant reconnu par une suite d'états [Here is a formula]), 1 £ h £ k. Nous considérons alors, dans l'automate construit sur U et V, la suite d'états q1 = (i1, j1), ... , qk = (ik, jk) définie par :

• Pour tout indice h, 1 £ h £ k, ih = [Here is a formula].
• Pour tout indice h tel que : 1 £ [Here is a formula] < j(x0), jh = [Here is a formula].
• Pour tout indice h tel que : j(x0) £ [Here is a formula] < j(x0) - 1, jh = [Here is a formula] + 1.
• Pour tout indice h tel que : j(x0) - 1 £ [Here is a formula] £ ½ F(V')½ + 1, jh = [Here is a formula] + 2.

Nous ajoutons les deux états q et q' définis par : si h est l'indice tel que [Here is a formula]) alors [Here is a formula]) et de même, si h' est l'indice tel que [Here is a formula] alors [Here is a formula].

Il ne reste alors plus qu'à trier cette suite d'états sur l'ordre des jh.

Remarquons maintenant que, jusqu'en l'état q, tous les mouvements sont possibles car ils se produisent dans l'automate reconnaissant L (U, V'). Désignons par (i, j) l'état qui précède immédiatement l'état q dans notre liste. Le mouvement exécuté à partir de cet état ne peut pas être dans M3. S'il était dans M1 È M'1È Mt, cela impliquerait que x0 est « indispensable » pour la reconnaissance de U dans V', i.e. il n'existe pas d'autre noeud x'0 pouvant jouer le rôle avant x0 lui-même au sens de l'ordre préfixe.

Mais comme on a choisi x0 en maximisant la valeur de j (x0), cela signifierait exactement que U Ë V', ce qui est contradictoire avec l'hypothèse ou encore que x0 est racine de l'arbre V.

Dans ce dernier cas, la transition M'3 joue le rôle de « maximisation » de la fonction j(x0). Lorsque l'automate ne permet pas de trouver une solution pour un sous-arbre (vj Î S, le compteur du sommet de pile état nul et i ¹ j(qt), qt étant l'état placé en sommet de pile) la transition M'3 simule le fait que j-1(vj) soit racine de l'arbre en provoquant la comparaison de ui avec chacun de ses fils.

On parvient donc bien en l'état q et ce, par un mouvement de M4 È M5 È M'3 qui ne change pas le caractère de dessus de pile. Tout au plus, ce mouvement incrémente le compteur associé à ce caractère.

Par rapport à l'automate reconnaissant L(U, V') seule la valeur associée au caractère de sommet de pile est donc susceptible d'avoir changé. Mais ceci n'aucune influence sur les mouvements suivants car V est un arbre : le « compteur » sera nécessairement décrémenté en q'. On vérifie alors sans difficulté que l'ensemble des états que nous avons construits sont effectivement atteints. Par suite L (U, V) ¹ Æ, ce qui assure le résultat. ¨

5.2.2.5 Algorithme de comparaison

L'automate de reconnaissance de massif est implémenté par l'algorithme donné dans la figure 41.

Cet algorithme prend en entrée deux chaînes bien parenthésées appelées respectivement u pour la chaîne représentant le type de l'élément source et v pour la chaîne représentant le type dans lequel l'élément doit être converti. L'algorithme utilise une pile pour mémoriser les parenthèses ouvrantes rencontrées au cours du déroulement de l'algorithme. Chaque élément de la pile contient trois informations : pile.symb est le symbole représentant le constructeur du type de l'élément comparé ('{', '[' ou '(') ; pile.état est l'état de retour sur erreur correspondant à l'état courant quand le type à été empilé ; pile.compte est le nombre de parenthèses identiques à pile.symb rencontrées depuis que le type a été empilé.

L'algorithme utilise également les fonctions Inverse, AjoutCouple, SupprCouple et Alpha. Inverse renvoie la parenthèse fermante opposée à celle qui lui est passée en paramètre (c'est à dire ')' pour '(', ']' pour '[' et '}' pour '{'). La fonction AjoutCouple(i,j) enregistre une relation entre le type d'indice i dans la source et le type d'indice j dans la cible. La fonction SupprCouple(i1, i2) efface les relations concernant l'ensemble des types dont les indices dans l'empreinte source sont compris entre i1 et i2. La fonction Alpha implémente a et a-1. Elle retourne l'indice de la parenthèse opposée au caractère dont l'indice est passé en paramètre.

Le résultat est un ensemble de couples (type source, type cible), appelé couplage de u dans v, qui sont utilisés pour la conversion de l'instance source u.

i := 1;            /* indice source */
j := 1;            /* indice cible */
empiler (pile, e); /* initialisation de la pile */

tantque i <= |u| et j <= |v| faire   /*boucle principale*/
  si u[i] = v[j] alors
    si v[j] = 'T' alors
  
      /* cas 1 transition Mt : deux terminaux égaux */
      AjoutCouple (i,j);
      i := i + 1;
  
    sinon /* v[j] != 'T'*/
      si v[j] = Inverse (pile.symb) alors
       /* v[j] est une parenthese fermante inverse 
          du symbole en sommet de pile */ 
        si pile.compte = 0 alors

          /* cas 2, transition M1 : 
             compte = 0 signifie que v(j) est la
             parenthèse fermante associée a celle du sommet 
             de pile :
             le type u[i] est en relation avec v[j]
             transition M1 */
          AjoutCouple (i, j);
          i := i + 1;  
          dépiler (pile);

        sinon /* pile.compte != 0 */

          /* cas 3, transition M2 : v[j] n'est pas au même 
             niveau de parenthésage que le sommet de pile */
          pile.compte := pile.compte - 1;

        finsi
      sinon /* v[j] != inverse (pile.symb) */
        /* v[j] n'est pas l'inverse du somment de pile */
        si v[j] Î ('{','[','(') alors
       
          /* cas 4, transition M1' : v[j] est une parenthèse ouvrante, 
             on empile le type correspondant */
          empiler (pile, (v[j],(i, j),0));
          i := i + 1; 
 
        finsi
        /* l'autre cas ne peut arriver car les chaînes 
           sont bien parenthésées */
      finsi
    finsi     
    i := i + 1;  
  sinon   /* u[i] != v[j] */
    si v[j] = Inverse (pile.symb) alors
       /* v[j] est une parenthese fermante inverse 
          du symbole en sommet de pile */ 
      si pile.compte > 0 alors

        /* cas 5, transition M2: 
           v[j] correspond à un autre niveau de
           parenthésage que le type en sommet de pile */
        pile.compte := pile.compte - 1;

      sinon /* pile.compte = 0 */

        /* cas 6 : 
           le compteur ne peut plus être décrémenté
:
           la correspondance de types echoue partiellement. 
           les couplages de tous les types de l'instance
           source compris entre pile.ind et i sont effacées */
        si (pile.état.j < j - 1) alors
          /* transition M3 */
            SupprCouple (pile.état.i + 1, i);
            i := pile.état.i + 1;
              /* j est incrémenté en fin de boucle */   
            j := pile.état.j - 1; 
            pile.état.j := pile.état.j + 1;
        sinon /* transition M3' */
           SupprCouple (pile.état.i, i);
           j := Alpha ( pile.état.j + 1);
           i := pile.état.i;
           dépiler (pile);
        finsi
      finsi
    finsi
    si v[j] = pile.symb et u[i] Ï ('}',']',')')
      alors

      /* cas 7, transition M4: v[j] est une parenthèse identique
à la
         derniere empilée */
      pile.compte := pile.compte + 1;

    finsi

     /* cas 8,  transition M5: 
        v[j] n'est ni identique ni inverse au symbole
        de sommet de pile, on ne fait qu'avancer dans la
        chaîne cible */

  finsi
  j := j + 1; /* progression dans la chaîne cible */
fintantque

si i > ½u½ alors 
  retourner succes;
sinon 
  retourner echec; 
finsi

Figure 41 - Algorithme de comparaison d'empreintes.

Théorème 2

La complexité de l'algorithme est polynômiale en O(|v|2).

Preuve

Si l'on ne considère que les états Mt È M1 È M1' È M2 È M3 È M4 È M5, l 'indice j est systématiquement incrémenté par ces état, ils peuvent donc engendrer au plus |v| itérations de la boucle de l'algorithme.

Considérons maintenant la transition M'3 cette transition ne peut entraîner le parcours supplémentaire que des fils du noeud de V correspondant à l'état (i, j) dans lequel est déclenchée la transition. Par conséquent, au plus |v| transitions M'3 sont déclenchée lors de la comparaison. La comparaison des fils entraînant au plus jj - jj £ |v| transitions. Le surcoût dû à la transition M'3 est donc |v|2. Le nombre d'itérations de la boucle est donc limité par |v|+|v|2. Par conséquent la complexité de l'algorithme est O(|v|2).

Cet algorithme calcule un massif de l'arbre de types source U dans l'arbre de types cible V s'il en existe au moins un. Dans le cas de la comparaison de types de documents structurés, il peut exister un grand nombre de solutions - ceci est dû au nombre limité de constructeurs du système de types et à la forte composante textuelle des documents traités, qui implique de nombreuses correspondances possibles entre les types de base intervenant dans les structures génériques des documents.

Les relations trouvées par cet algorithme sont des relations de massif entre types non définis récursivement. Aussi, pour prendre en compte les relations d'absorption et trouver des relations entre types récursifs, qui sont fréquents dans les structures considérées (les paragraphes, les sections d'articles, les arbres sont définis récursivement), nous étendons la méthode de comparaison de types effectuée par l'algorithme de recherche de massif.

Pour optimiser le processus de transformation, nous évitons certaines comparaisons superflues. Lorsque la comparaison est effectuée entre deux types appartenant à une même structure générique, les éléments comparés peuvent être du même type. Il est, dans ce cas superflu de comparer les images de ces descendants dans les empreintes. Grâce à la table associative construite lors de la génération de l'empreinte, l'utilisation de la fonction fu-1 qui associe le noeud de l'arbre de type U à l'indice d'un symbole de l'empreinte appartenant à l'ensemble S est immédiate, on ajoute l'état M''1 à l'automate de comparaison :

M''1={((i, j), vj, (y, h, k), ((fu o fu-1(i)) + 1, j + 1), (y, h, k))}

avec la condition ui = vj, y ¹ vj-1

Cet état permet d'éviter la comparaison de la descendance de deux types égaux.