1.2 Arbres marqués
31
Fig. 1.31 L’arbre
lexicographique associé à
Y = {aaba, baab, aa, ab}
Remarquons que la connaissance de Pref(Y ) ne permet pas de retrouver Y , sauf si
aucun mot de Y n’est préfixe d’un autre. L’arbre lexicographique est représenté sur
la figure 1.31.
Nous vérifions aisément que l’ensemble Pref(Y ) définit bien un arbre préfixe au
sens de la définition 1.2, éventuellement infini dès que l’ensemble Y contient au
moins un mot infini : il suffit de remplacer l’ensemble de mots U de la définition 1.2
par l’ensemble A
∗ .
Nous donnons ci-dessous une première définition des tries. La structure de trie
associée à un ensemble de mots Y est l’arbre lexicographique associé à l’ensemble
minimal dans Pref(Y ) nécessaire pour distinguer les mots les uns des autres (ce qui
n’est possible que si aucun mot de Y n’est préfixe d’un autre mot de Y ).
Définition 1.40 Soit Y un ensemble de mots sur A tel qu’aucun mot ne soit préfixe
d’un autre. Pour tout mot w de A
∗ , notons N w := N w (Y ) le nombre de mots de Y
qui admettent w comme préfixe. Soit
I := {u ∈ Pref(Y ) | N u ≥ 2}.
Le trie trie(Y ) est l’arbre dont l’ensemble des nœuds est
N =
{ε} ∪ (I · A)
∩ Pref(Y ).
L’ensemble I est l’ensemble des nœuds internes du trie, et N \ I est l’ensemble des
nœuds externes.
Cette définition est incomplète car « traditionnellement » une information est
attachée aux nœuds externes d’un trie, qui caractérise la clé unique associée à ce
nœud (en général, cette information est le suffixe obtenu en retirant de la clé la
marque du chemin menant au nœud).
Une définition plus usuelle des tries est la suivante. Elle associe un r-uplet à tout
nœud interne (avec r la taille de l’alphabet) : ce sont les façons dont une branche
(ou encore ici un mot) peut s’étendre. De plus chaque nœud externe est associé à
une clé.
31
Fig. 1.31 L’arbre
lexicographique associé à
Y = {aaba, baab, aa, ab}
Remarquons que la connaissance de Pref(Y ) ne permet pas de retrouver Y , sauf si
aucun mot de Y n’est préfixe d’un autre. L’arbre lexicographique est représenté sur
la figure 1.31.
Nous vérifions aisément que l’ensemble Pref(Y ) définit bien un arbre préfixe au
sens de la définition 1.2, éventuellement infini dès que l’ensemble Y contient au
moins un mot infini : il suffit de remplacer l’ensemble de mots U de la définition 1.2
par l’ensemble A
∗ .
Nous donnons ci-dessous une première définition des tries. La structure de trie
associée à un ensemble de mots Y est l’arbre lexicographique associé à l’ensemble
minimal dans Pref(Y ) nécessaire pour distinguer les mots les uns des autres (ce qui
n’est possible que si aucun mot de Y n’est préfixe d’un autre mot de Y ).
Définition 1.40 Soit Y un ensemble de mots sur A tel qu’aucun mot ne soit préfixe
d’un autre. Pour tout mot w de A
∗ , notons N w := N w (Y ) le nombre de mots de Y
qui admettent w comme préfixe. Soit
I := {u ∈ Pref(Y ) | N u ≥ 2}.
Le trie trie(Y ) est l’arbre dont l’ensemble des nœuds est
N =
{ε} ∪ (I · A)
∩ Pref(Y ).
L’ensemble I est l’ensemble des nœuds internes du trie, et N \ I est l’ensemble des
nœuds externes.
Cette définition est incomplète car « traditionnellement » une information est
attachée aux nœuds externes d’un trie, qui caractérise la clé unique associée à ce
nœud (en général, cette information est le suffixe obtenu en retirant de la clé la
marque du chemin menant au nœud).
Une définition plus usuelle des tries est la suivante. Elle associe un r-uplet à tout
nœud interne (avec r la taille de l’alphabet) : ce sont les façons dont une branche
(ou encore ici un mot) peut s’étendre. De plus chaque nœud externe est associé à
une clé.