300
7 Arbres digitaux
3. Nous constatons par le calcul pour chacun des paramètres étudiés qu’à n fixé le
lien entre le modèle fini équiprobable et le modèle infini i.i.d. uniforme (binaire)
se fait grâce à la formule
lim
d→∞
1
2 d
n
[z
n
]v
(d) (z) = n![z
n
] v(z).
Bien qu’intuitif, ce lien n’est pas détaillé à notre connaissance dans la littérature
pour le cas général.
4. Il est relativement aisé de généraliser cette approche au cas des tries paginés
de capacité b (aussi appelés b-tries). Leur analyse est importante car, pour une
utilisation effective des tries paginés, nous avons besoin de connaître l’influence
de la taille de la page sur les paramètres de l’arbre (comme la hauteur) pour
pouvoir régler au mieux la valeur de b en fonction des applications.
7.1.3 Approche symbolique (sources)
Dans cette section, l’alphabet A n’est plus nécessairement binaire : nous considérons que des clés sont produites indépendamment par la même source S, elle-même
modélisée grâce à l’ensemble de ses probabilités fondamentales (p w ) w∈A
∗ (voir la
section 2.3.2). Ces mots sont infinis et le trie est construit sur cet ensemble de mots.
Nous introduisons d’abord un outil méthodologique pour l’analyse : la paramétrisation d’une source qui permet de définir une application M qui associe aux réels de
l’intervalle [0, 1] des mots infinis de A
N . Ce procédé sera utilisé systématiquement
pour définir le modèle probabiliste d’un ensemble de clés.
Paramétrisation d’une source de symboles
Dans la suite nous supposerons que toutes les probabilités fondamentales
{p w } w∈A
∗ , définies comme les probabilités d’apparition d’un préfixe w fini
p w = P {x ∈ A
N , x admet w pour préfixe},
sont données et non nulles, ce qui revient à dire que la source peut produire tous les
mots de A
N .
Remarque 7.18 Il est facile pour une source sans mémoire (comme une source
markovienne) de calculer effectivement les probabilités fondamentales {p w } w∈A
∗
à partir de la description relativement succincte de la source (voir la section 2.3.2).
7 Arbres digitaux
3. Nous constatons par le calcul pour chacun des paramètres étudiés qu’à n fixé le
lien entre le modèle fini équiprobable et le modèle infini i.i.d. uniforme (binaire)
se fait grâce à la formule
lim
d→∞
1
2 d
n
[z
n
]v
(d) (z) = n![z
n
] v(z).
Bien qu’intuitif, ce lien n’est pas détaillé à notre connaissance dans la littérature
pour le cas général.
4. Il est relativement aisé de généraliser cette approche au cas des tries paginés
de capacité b (aussi appelés b-tries). Leur analyse est importante car, pour une
utilisation effective des tries paginés, nous avons besoin de connaître l’influence
de la taille de la page sur les paramètres de l’arbre (comme la hauteur) pour
pouvoir régler au mieux la valeur de b en fonction des applications.
7.1.3 Approche symbolique (sources)
Dans cette section, l’alphabet A n’est plus nécessairement binaire : nous considérons que des clés sont produites indépendamment par la même source S, elle-même
modélisée grâce à l’ensemble de ses probabilités fondamentales (p w ) w∈A
∗ (voir la
section 2.3.2). Ces mots sont infinis et le trie est construit sur cet ensemble de mots.
Nous introduisons d’abord un outil méthodologique pour l’analyse : la paramétrisation d’une source qui permet de définir une application M qui associe aux réels de
l’intervalle [0, 1] des mots infinis de A
N . Ce procédé sera utilisé systématiquement
pour définir le modèle probabiliste d’un ensemble de clés.
Paramétrisation d’une source de symboles
Dans la suite nous supposerons que toutes les probabilités fondamentales
{p w } w∈A
∗ , définies comme les probabilités d’apparition d’un préfixe w fini
p w = P {x ∈ A
N , x admet w pour préfixe},
sont données et non nulles, ce qui revient à dire que la source peut produire tous les
mots de A
N .
Remarque 7.18 Il est facile pour une source sans mémoire (comme une source
markovienne) de calculer effectivement les probabilités fondamentales {p w } w∈A
∗
à partir de la description relativement succincte de la source (voir la section 2.3.2).