54
2 Aléa sur les arbres
Le modèle probabiliste que nous venons de définir sur les arbres binaires de
recherche s’étend naturellement aux autres types d’arbres de recherche : les arbres
2-3 que nous avons rencontrés en section 1.2.6, ainsi que les arbres-B présentés en
section 3.2.2 (a), les quadtrees en section 3.2.2 (b) et les arbres m-aires de recherche
en section 8.1.1.
Sous le modèle des permutations uniformes, la loi de l’arbre construit à partir de
n clés i.i.d. de même loi continue est la même que celle de l’arbre construit à partir
d’une permutation uniformément choisie dans S n .
2.3 Aléa sur les arbres digitaux
Les arbres digitaux rentrent dans la catégorie des arbres marqués. Cependant la
nature de l’aléa est différente de celle des sections précédentes.
L’arbre digital est construit sur un ensemble de mots et il y a donc plusieurs
aspects à considérer du point de vue de la modélisation selon la chaîne
symbole → mot → ensemble de mots.
Dans les arbres digitaux aléatoires, l’aléa peut intervenir à plusieurs niveaux :
– Tout d’abord une clé est un mot, lui même vu comme une séquence de symboles.
Nous définissons donc un modèle probabiliste sur les symboles qui composent le
mot. Ils peuvent ou non être indépendants les uns des autres. Les mots peuvent
être finis ou infinis.
– Une fois le modèle sur les symboles, et donc sur les mots, défini, il faut aussi
préciser le modèle probabiliste pour un ensemble de mots. Là aussi nous pouvons
considérer les clés indépendantes ou non entre elles.
– Enfin le cardinal de l’ensemble de mots peut lui aussi être aléatoire.
Dans ce livre toutes les analyses d’arbres digitaux considèrent des clés indépendantes et produites par le même processus : les clés sont donc i.i.d (indépendantes
et identiquement distribuées).
En pratique, les clés à stocker dans un arbre digital peuvent être de nature très
diverse. Cela peut aussi bien être des mots de la langue française, que des clés de
hachage, ou encore des suites de bits ou des mots-machine.
Nous considérons donc un alphabet fini dont les lettres sont appelées « symboles 4 ».
Dans la section 2.3.1, nous décrivons deux modèles probabilistes usuels pour un
ensemble de mots : le modèle fini équiprobable et le modèle infini i.i.d. Dans ce
4 En programmation le terme « chaîne de caractères » (string en anglais) désignant une séquence
de lettres ou caractères est souvent employé. Cependant dans le domaine de la combinatoire des
mots ou de théorie de l’information, nous parlons plutôt de mots, vus comme des séquences de
symboles.
2 Aléa sur les arbres
Le modèle probabiliste que nous venons de définir sur les arbres binaires de
recherche s’étend naturellement aux autres types d’arbres de recherche : les arbres
2-3 que nous avons rencontrés en section 1.2.6, ainsi que les arbres-B présentés en
section 3.2.2 (a), les quadtrees en section 3.2.2 (b) et les arbres m-aires de recherche
en section 8.1.1.
Sous le modèle des permutations uniformes, la loi de l’arbre construit à partir de
n clés i.i.d. de même loi continue est la même que celle de l’arbre construit à partir
d’une permutation uniformément choisie dans S n .
2.3 Aléa sur les arbres digitaux
Les arbres digitaux rentrent dans la catégorie des arbres marqués. Cependant la
nature de l’aléa est différente de celle des sections précédentes.
L’arbre digital est construit sur un ensemble de mots et il y a donc plusieurs
aspects à considérer du point de vue de la modélisation selon la chaîne
symbole → mot → ensemble de mots.
Dans les arbres digitaux aléatoires, l’aléa peut intervenir à plusieurs niveaux :
– Tout d’abord une clé est un mot, lui même vu comme une séquence de symboles.
Nous définissons donc un modèle probabiliste sur les symboles qui composent le
mot. Ils peuvent ou non être indépendants les uns des autres. Les mots peuvent
être finis ou infinis.
– Une fois le modèle sur les symboles, et donc sur les mots, défini, il faut aussi
préciser le modèle probabiliste pour un ensemble de mots. Là aussi nous pouvons
considérer les clés indépendantes ou non entre elles.
– Enfin le cardinal de l’ensemble de mots peut lui aussi être aléatoire.
Dans ce livre toutes les analyses d’arbres digitaux considèrent des clés indépendantes et produites par le même processus : les clés sont donc i.i.d (indépendantes
et identiquement distribuées).
En pratique, les clés à stocker dans un arbre digital peuvent être de nature très
diverse. Cela peut aussi bien être des mots de la langue française, que des clés de
hachage, ou encore des suites de bits ou des mots-machine.
Nous considérons donc un alphabet fini dont les lettres sont appelées « symboles 4 ».
Dans la section 2.3.1, nous décrivons deux modèles probabilistes usuels pour un
ensemble de mots : le modèle fini équiprobable et le modèle infini i.i.d. Dans ce
4 En programmation le terme « chaîne de caractères » (string en anglais) désignant une séquence
de lettres ou caractères est souvent employé. Cependant dans le domaine de la combinatoire des
mots ou de théorie de l’information, nous parlons plutôt de mots, vus comme des séquences de
symboles.