Probleme – L'arbre préfixe, ou pourquoi chercher un mot ne dépend pas du dictionnaire

1. Le type et les deux opérations. C'est un arbre général : un nœud a autant de fils que de lettres différentes qui peuvent le suivre.

(* lettre portee, « un mot finit ici », fils *)
type trie = Noeud of char * bool * trie list

let vide = Noeud ('*', false, [])                 (* la racine ne porte rien *)

(* Insere le suffixe mot[i..] sous t. Renvoie le trie modifie.
   Precondition : 0 <= i <= String.length mot. *)
let rec insere (Noeud (c, fin, fils)) mot i =
  if i = String.length mot then Noeud (c, true, fils)
  else
    let l = mot.[i] in
    let rec dans = function
      | [] -> [insere (Noeud (l, false, [])) mot (i+1)]      (* branche NEUVE *)
      | (Noeud (l', _, _) as f) :: r ->
          if l' = l then insere f mot (i+1) :: r else f :: dans r
    in Noeud (c, fin, dans fils)

(* Renvoie true ssi mot[i..] est un mot complet range sous t. *)
let rec appartient (Noeud (_, fin, fils)) mot i =
  if i = String.length mot then fin
  else
    let l = mot.[i] in
    let rec cherche = function
      | [] -> false
      | (Noeud (l', _, _) as f) :: r ->
          if l' = l then appartient f mot (i+1) else cherche r
    in cherche fils

2. Correction et coût.

Terminaison. Variant : $|mot|-i$, qui décroît de $1$ à chaque descente. La fonction auxiliaire cherche termine par l'ordre induit sur la liste de fils.

Invariant de la structure, et c'est lui qu'il faut énoncer avant tout : le chemin de la racine à un nœud épelle un préfixe, et le drapeau fin y vaut true exactement quand ce préfixe est un mot de l'ensemble. L'insertion le préserve — elle ne pose true qu'au bout du chemin du mot inséré — et la recherche l'exploite : elle descend le long du chemin épelé par le mot et lit le drapeau.

Complexité. La recherche visite au plus $|mot|$ nœuds, et examine à chaque étage au plus $\sigma$ fils, où $\sigma$ est la taille de l'alphabet. Le coût est $O(\sigma |mot|)$ — il ne dépend pas du nombre de mots rangés. C'est le fait remarquable de la structure, et il vaut aussi pour l'insertion.

3. Les mesures. Sur le dictionnaire de dix mots arbre, arc, arche, art, bas, base, basique, but, a, arbrisseau :

$25$ nœuds portant une lettre — $26$ avec la racine — pour $44$ lettres écrites : $19$ lettres ont été partagées entre mots à préfixe commun — le ar de arbre, arc, arche, art, arbrisseau, le bas de bas, base, basique. C'est le second intérêt de la structure : elle compresse les préfixes.

Comparaisons de lettres effectuées par une recherche :

Trois lignes méritent un commentaire. arb est faux bien que le chemin existe : c'est un préfixe, pas un mot, et c'est précisément à cela que sert le drapeau — sans lui, la structure ne distinguerait pas les deux. zut coûte $2$ comparaisons seulement : la racine n'a que les fils a et b, et l'échec est immédiat. basiques coûte autant que basique : on s'arrête faute de fils s, sans lire la fin du mot.

Comparaison avec une liste de mots. Chercher dans une liste de $m$ mots demande $O(m)$ comparaisons de chaînes, soit $O(m\times |mot|)$ caractères dans le pire cas. Avec $m=10$, l'écart est mince ; avec $m=300000$ — la taille d'un dictionnaire français — le trie fait toujours $O(\sigma |mot|)$, soit quelques dizaines de comparaisons, et la liste plusieurs millions. Le coût du trie est indépendant de $m$, et c'est tout ce qui compte.

4. Le lien avec le cours. Un trie est un arbre d'arité quelconque : sa réalisation naturelle en OCaml est la liste de fils écrite ci-dessus, et cette liste est la conversion « fils gauche, frère droit ». Le premier fils est le fils gauche du binaire, les frères suivants forment la chaîne droite. La fonction cherche qui parcourt la liste des fils est exactement le parcours de cette chaîne de frères.

On y retrouve le défaut mesuré à l'exercice 10.7 : la fratrie devient un peigne. Un nœud à $26$ fils a une hauteur binaire de $25$, et la recherche d'une lettre y coûte jusqu'à $26$ comparaisons — c'est le facteur $\sigma$ de la complexité. Deux remèdes classiques : remplacer la liste de fils par un tableau de $\sigma$ cases indexé par la lettre, qui ramène le coût à $O(|mot|)$ au prix de $\sigma$ pointeurs par nœud ; ou par un arbre binaire de recherche sur les lettres, qui donne $O(|mot|\log \sigma )$ en espace linéaire. Le choix se fait sur la taille de l'alphabet, et c'est un exemple parfait de ce que le cours annonçait : la structure de données se taille à la mesure des opérations qu'on répète.