76
3 Arbres, algorithmes et données
tries paginés de capacité b > 1 (voir la figure 1.33), le seul changement est qu’une
feuille peut contenir au plus b clés. Il faudra donc utiliser une autre structure de
données (tableau, liste chaînée) pour la gestion des feuilles.
Arbre PATRICIA
Dans l’implémentation des tries, nous pouvons stocker en chaque nœud un couple
(lettre,skip) qui indique la première lettre de la marque (c.-à-d. la lettre qui a
mené à la création d’une nouvelle branche) et le nombre de symboles à « sauter »,
qui de toute façon n’influencent pas la recherche. De la sorte nous accélérons l’accès
à la feuille susceptible de contenir l’information recherchée ; la recherche se conclut
par une comparaison lettre à lettre entre le motif recherché et le mot trouvé, dans
la mesure où certaines lettres ont pu être sautées. Un exemple d’arbre Patricia est
donné dans la figure 1.34.
Mentionnons aussi que l’informatisation du Oxford English Dictionary, réalisée
par Gonnet et al. dans les années 80, utilise des arbres PATRICIA.
Arbre digital de recherche
Soit un arbre digital de recherche dst(S) construit sur un ensemble fini de mots S ;
cf. la définition 1.45 et la figure 1.35. Le principe de recherche d’une clé dans un
tel arbre est le suivant. Soit α la clé (c’est un mot !) à rechercher dans l’arbre ;
la clé s 1 à la racine de dst(S) est comparée à α selon l’ordre lexicographique. En
cas de succès, la recherche est finie. Sinon, nous recherchons le mot α privé de son
premier symbole dans le sous-arbre relatif à ce premier symbole ; il y a échec si ce
sous-arbre n’existe pas.
La recherche d’une clé conduit à parcourir une branche qui est nécessairement
un préfixe de la clé (comme pour un trie). La différence avec le trie se situe dans
le fait que nous effectuons une comparaison de mots (et non de symboles) selon
l’ordre lexicographique en chaque nœud interne, et que l’algorithme s’arrête en cas
d’égalité de mots.
Trie des suffixes
Le trie des suffixes est une structure de données peu utilisée mais importante car
elle est sous-jacente à celle d’arbre des suffixes, qui est une structure de données
efficace.
Soit w = w 1 . . . w n ∈ A
∗ un mot fini de longueur n sur l’alphabet A. Notons
w[i . . j] = w i w i+1 . . . w j si i ≤ j , et w[i . . j] = ε si i > j . L’ensemble des
suffixes suff(w) est l’ensemble des mots obtenus par « décalage » du mot w, i.e.,
suff(w) = {w[k . . n], | 1 ≤ k ≤ n}.
3 Arbres, algorithmes et données
tries paginés de capacité b > 1 (voir la figure 1.33), le seul changement est qu’une
feuille peut contenir au plus b clés. Il faudra donc utiliser une autre structure de
données (tableau, liste chaînée) pour la gestion des feuilles.
Arbre PATRICIA
Dans l’implémentation des tries, nous pouvons stocker en chaque nœud un couple
(lettre,skip) qui indique la première lettre de la marque (c.-à-d. la lettre qui a
mené à la création d’une nouvelle branche) et le nombre de symboles à « sauter »,
qui de toute façon n’influencent pas la recherche. De la sorte nous accélérons l’accès
à la feuille susceptible de contenir l’information recherchée ; la recherche se conclut
par une comparaison lettre à lettre entre le motif recherché et le mot trouvé, dans
la mesure où certaines lettres ont pu être sautées. Un exemple d’arbre Patricia est
donné dans la figure 1.34.
Mentionnons aussi que l’informatisation du Oxford English Dictionary, réalisée
par Gonnet et al. dans les années 80, utilise des arbres PATRICIA.
Arbre digital de recherche
Soit un arbre digital de recherche dst(S) construit sur un ensemble fini de mots S ;
cf. la définition 1.45 et la figure 1.35. Le principe de recherche d’une clé dans un
tel arbre est le suivant. Soit α la clé (c’est un mot !) à rechercher dans l’arbre ;
la clé s 1 à la racine de dst(S) est comparée à α selon l’ordre lexicographique. En
cas de succès, la recherche est finie. Sinon, nous recherchons le mot α privé de son
premier symbole dans le sous-arbre relatif à ce premier symbole ; il y a échec si ce
sous-arbre n’existe pas.
La recherche d’une clé conduit à parcourir une branche qui est nécessairement
un préfixe de la clé (comme pour un trie). La différence avec le trie se situe dans
le fait que nous effectuons une comparaison de mots (et non de symboles) selon
l’ordre lexicographique en chaque nœud interne, et que l’algorithme s’arrête en cas
d’égalité de mots.
Trie des suffixes
Le trie des suffixes est une structure de données peu utilisée mais importante car
elle est sous-jacente à celle d’arbre des suffixes, qui est une structure de données
efficace.
Soit w = w 1 . . . w n ∈ A
∗ un mot fini de longueur n sur l’alphabet A. Notons
w[i . . j] = w i w i+1 . . . w j si i ≤ j , et w[i . . j] = ε si i > j . L’ensemble des
suffixes suff(w) est l’ensemble des mots obtenus par « décalage » du mot w, i.e.,
suff(w) = {w[k . . n], | 1 ≤ k ≤ n}.