Discussion :

[Loceka]

Bonjour,

Tout d'abord, désolé pour ce titre peu explicite, j'espère qu'il le deviendra après l'exposé du problème.

Dans le cadre de la création d'un document DOM (XML, tout ça) je voudrais calculer (ou estimer) l'endroit où doit être inséré un nouvel élément dans une liste d'éléments existants en fonction de la DTD associée au parent.

Exemple :
Un élément test déclare la DTD suivante :

Code XML :

Sélectionner tout - Visualiser dans une fenêtre à part

<!ELEMENT test (sub, (title, sub, text)*)

Etant donné que je suis en création, il est possible de n'avoir qu'une partie des éléments, comme par exemple :

Code xml :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<test>
  <title/>
  <sub/>
</test>
<!--  ou bien  -->
<test>
  <sub/>
  <text/>
</test>
<!--  ou encore  -->
<test>
  <sub/>
  <title/>
</test>

Si je veux rajouter l'élément sub dans chacun de ces trois cas, je n'ai normalement qu'une seule solution "optimale" : celle qui me donne la DTD la plus valide possible :

Code XML :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
<test>
  <sub/><!-- nouvellement inséré -->
  <title/>
  <sub/>
</test>
<!--  ou bien  -->
<test>
  <sub/>
  <sub/><!-- nouvellement inséré -->
  <text/>
</test>
<!--  ou encore  -->
<test>
  <sub/>
  <title/>
  <sub/><!-- nouvellement inséré -->
</test>

Ou, pour décrire ça de façon moins verbeuse et surtout plus proche de mon code actuel :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
[title, sub] -> [sub, title, sub]
[sub, text]  -> [title, sub, sub]
[sub, title] -> [title, sub, sub]

Le truc bien entendu c'est que je n'arrive à rien.

J'avais testé plusieurs algos dont le dernier en date ressemblait à ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fonction rechercheIndexPossible(filsActuels:Liste, nouveauFils:Element) : Entier {
  dernierFils:Element;
  pour (i := filsActuels.length ; i >= 0; i--) {
    si (nouveauFils estInsérable entre filsActuels[i] et dernierFils) {
      // on ajoute après l'élément actuel
      return i + 1;
    }
  }
  // le nouveau fils n'est insérable après aucun élément actuel, on teste s'il l'est avant le premier :
  si (nouveauFils estInsérable avant dernierFils) {
    return 0;
  }

  // impossible de l'insérer
  return -1;
}

Le problème c'est qu'en déroulant l'algo sur les exemple que j'ai donné, on voit tout de suite que ça ne fait pas ce que je veux.

Du coup je n'ai plus aucune idée de comment estimer l'index d'insertion pour que ça donne au moins un état qui soit compatible avec la DTD (si on considère qu'on ajoute suffisament d'éléments pour ça).

Je suppose qu'il faut passer par du backtracking pour ça mais mes cours d'IA remontent à loin et je serai actuellement incapable de faire un tel algo en partant de zéro.

Du coup si vous avez des pistes à me proposer ou un début d'algo, je suis preneur !

Merci d'avance,
Loceka.

[Loceka]

(sub, (title, sub, text)*) est représenté par

Code (sub, (title, sub, text)*) est représenté par :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
            Groupe
              type: séquence
              obligatoire
          /               \
         /                 \
        /                   \
Elem                      Groupe
  nom: sub                  type: séquence
  obligatoire               multiple ou nul
                          /        |       \
                         /         |        \
                        /          |         \
                Elem           Elem           Elem
                  nom: title     nom: sub       nom: text
                  obligatoire    obligatoire    obligatoire

[Loceka]

Bon, je crois que j'ai trouvé une solution.

Elle se fait en deux étapes distinctes :

1. Rechercher l'ensemble des indexes possibles d'insertion dans la liste des fils actuels.
2. estimer (à l'aide d'une heuristique) la position la plus pertinente pour l'insertion.

Du coup, il ne me reste plus qu'à trouver une heuristique potable, mais pour ça je doute que vous puissiez m'aider.