306
7 Arbres digitaux
Preuve La propriété d’indépendance entre intervalles fondamentaux disjoints permet de décomposer E Z [v] en additionnant les contributions du péage sur tous les
nœuds internes possibles. Chacun de ces nœuds est associé à un préfixe w ∈ A
∗ . De
plus γ (z) n’est autre que l’espérance de γ (N) lorsque N est une variable aléatoire
de loi de Poisson de paramètre z.
Remarque 7.26 Pour les exemples traités ci-après (taille et longueur de cheminement externe d’un trie), la fonction γ dépend uniquement du cardinal de ω.
Le lemme additif 7.25 s’étend à une classe plus grande de paramètres où la
fonction de péage dépend du multi-ensemble des lettres initiales (appelé « tranche »)
des mots de ω. Par exemple la tranche de l’ensemble
ω = {aaa . . . , aab . . . , abb . . . , baa . . . , cab . . . }
est {a, a, a, b, c}. En effet, ce sont ces lettres et elles seulement qui régissent le
principe de partitionnement de trie(ω) à la racine. Dans le cas d’une fonction de
péage γ qui ne dépend que du cardinal, la composition du multi-ensemble des
premières lettres n’a pas d’importance. Seul joue le fait que la taille du multiensemble suit une loi de Poisson.
L’analyse des tries PATRICIA notamment considère le nombre d’éléments distincts de ce multi-ensemble, et non plus seulement le cardinal, puisqu’un nœud
interne existe seulement si le multi-ensemble contient au moins deux lettres
distinctes. Un autre paramètre comme la longueur de cheminement externe des
tries hybrides (où le coût d’accès d’un nœud à ses enfants est pris en compte ; cf.
l’exercice 7.12) nécessite de considérer plus finement les nœuds internes et les liens
qui les relient à leurs sous-tries et donc d’étudier les « tranches » de manière plus
précise.
Taille d’un trie Avec la définition de la fonction de péage
γ (ω) = 1 {|ω|≥2} ,
la série de Poisson de l’équation (7.23) s’écrit
γ (Z) = e
−Z
∞
k=2
γ (k)
Z k
k!
= 1 − (1 + Z) e
−Z .
D’après le lemme 7.25, nous calculons donc l’espérance de la taille dans le modèle
de Poisson :
E Z [S] =
w∈A
∗
1 − e
−Zp w (1 + Zp w )
.
7 Arbres digitaux
Preuve La propriété d’indépendance entre intervalles fondamentaux disjoints permet de décomposer E Z [v] en additionnant les contributions du péage sur tous les
nœuds internes possibles. Chacun de ces nœuds est associé à un préfixe w ∈ A
∗ . De
plus γ (z) n’est autre que l’espérance de γ (N) lorsque N est une variable aléatoire
de loi de Poisson de paramètre z.
Remarque 7.26 Pour les exemples traités ci-après (taille et longueur de cheminement externe d’un trie), la fonction γ dépend uniquement du cardinal de ω.
Le lemme additif 7.25 s’étend à une classe plus grande de paramètres où la
fonction de péage dépend du multi-ensemble des lettres initiales (appelé « tranche »)
des mots de ω. Par exemple la tranche de l’ensemble
ω = {aaa . . . , aab . . . , abb . . . , baa . . . , cab . . . }
est {a, a, a, b, c}. En effet, ce sont ces lettres et elles seulement qui régissent le
principe de partitionnement de trie(ω) à la racine. Dans le cas d’une fonction de
péage γ qui ne dépend que du cardinal, la composition du multi-ensemble des
premières lettres n’a pas d’importance. Seul joue le fait que la taille du multiensemble suit une loi de Poisson.
L’analyse des tries PATRICIA notamment considère le nombre d’éléments distincts de ce multi-ensemble, et non plus seulement le cardinal, puisqu’un nœud
interne existe seulement si le multi-ensemble contient au moins deux lettres
distinctes. Un autre paramètre comme la longueur de cheminement externe des
tries hybrides (où le coût d’accès d’un nœud à ses enfants est pris en compte ; cf.
l’exercice 7.12) nécessite de considérer plus finement les nœuds internes et les liens
qui les relient à leurs sous-tries et donc d’étudier les « tranches » de manière plus
précise.
Taille d’un trie Avec la définition de la fonction de péage
γ (ω) = 1 {|ω|≥2} ,
la série de Poisson de l’équation (7.23) s’écrit
γ (Z) = e
−Z
∞
k=2
γ (k)
Z k
k!
= 1 − (1 + Z) e
−Z .
D’après le lemme 7.25, nous calculons donc l’espérance de la taille dans le modèle
de Poisson :
E Z [S] =
w∈A
∗
1 − e
−Zp w (1 + Zp w )
.