2.3 Aléa sur les arbres digitaux
55
dernier modèle, une distribution de probabilité sur les mots infinis est définie de
manière sous-jacente.
Nous allons plus loin dans la section 2.3.2 en définissant la notion de source de
symboles à même de produire des mots infinis (y compris ceux du modèle infini
i.i.d.). Les sources les plus connues sont les sources sans mémoire 5 et les sources à
dépendance markovienne, mais il en existe également d’autres types – non présentés
ici – de sources comme par exemple les sources dynamiques [245] qui fournissent
un cadre encore plus général. Toutes ces sources ont en commun de permettre le
calcul explicite de la probabilité, appelée dans la suite probabilité fondamentale p w ,
qu’un mot infini X ∈ A
N commence par un préfixe fini w ∈ A
∗ . Nous présentons
un cadre formel pour modéliser une source, appelée source probabilisée de mots
infinis.
Remarque 2.14 Remarquons que dans le cas des tries des suffixes, le modèle
probabiliste considère un seul mot ainsi que l’ensemble de ses suffixes. Ce
modèle, intéressant pour certaines applications, par exemple pour l’indexation en
algorithmique du texte, est difficile à analyser car il y a une grande dépendance
entre les suffixes. Une analyse est parfois possible en supposant que des suffixes de
positions suffisamment « éloignées » l’une de l’autre dans un texte sont quasiment
indépendants.
Remarque 2.15 Pour les besoins de l’analyse des arbres digitaux nous aurons
souvent recours à un modèle de Poisson pour le cardinal de l’ensemble de mots,
i.e., le nombre de mots est une variable aléatoire qui suit une loi de Poisson. Ce qui
nous intéresse surtout dans ce modèle moins naturel que celui où le cardinal est fixé
à une certaine valeur (appelé dans la suite modèle de Bernoulli) sont les propriétés
d’indépendance de ces variables aléatoires qui simplifient les analyses. Ce modèle
de Poisson, essentiel pour l’analyse, est décrit en section 7.1.3.
2.3.1 Modèles usuels.
Les modèles usuels pour l’analyse des arbres digitaux supposent que les clés soient
de longueur infinie. En pratique, ce n’est (évidemment !) pas toujours le cas. Le plus
souvent, les modèles à clés infinies peuvent être vus comme une approximation
de la réalité informatique, suffisante pour l’analyse, mais il existe des situations
dans lesquelles le modèle naturel est le modèle fini (par exemple, en géométrie
algorithmique).
5 Les sources sans mémoire sont parfois appelées sources de Bernoulli car dans le cas binaire
les caractères produits correspondent à un processus de Bernoulli. Nous ne reprenons pas cette
terminologie ici puisqu’il y aura un risque de confusion avec le modèle de Bernoulli désignant un
ensemble de cardinal fixé.
55
dernier modèle, une distribution de probabilité sur les mots infinis est définie de
manière sous-jacente.
Nous allons plus loin dans la section 2.3.2 en définissant la notion de source de
symboles à même de produire des mots infinis (y compris ceux du modèle infini
i.i.d.). Les sources les plus connues sont les sources sans mémoire 5 et les sources à
dépendance markovienne, mais il en existe également d’autres types – non présentés
ici – de sources comme par exemple les sources dynamiques [245] qui fournissent
un cadre encore plus général. Toutes ces sources ont en commun de permettre le
calcul explicite de la probabilité, appelée dans la suite probabilité fondamentale p w ,
qu’un mot infini X ∈ A
N commence par un préfixe fini w ∈ A
∗ . Nous présentons
un cadre formel pour modéliser une source, appelée source probabilisée de mots
infinis.
Remarque 2.14 Remarquons que dans le cas des tries des suffixes, le modèle
probabiliste considère un seul mot ainsi que l’ensemble de ses suffixes. Ce
modèle, intéressant pour certaines applications, par exemple pour l’indexation en
algorithmique du texte, est difficile à analyser car il y a une grande dépendance
entre les suffixes. Une analyse est parfois possible en supposant que des suffixes de
positions suffisamment « éloignées » l’une de l’autre dans un texte sont quasiment
indépendants.
Remarque 2.15 Pour les besoins de l’analyse des arbres digitaux nous aurons
souvent recours à un modèle de Poisson pour le cardinal de l’ensemble de mots,
i.e., le nombre de mots est une variable aléatoire qui suit une loi de Poisson. Ce qui
nous intéresse surtout dans ce modèle moins naturel que celui où le cardinal est fixé
à une certaine valeur (appelé dans la suite modèle de Bernoulli) sont les propriétés
d’indépendance de ces variables aléatoires qui simplifient les analyses. Ce modèle
de Poisson, essentiel pour l’analyse, est décrit en section 7.1.3.
2.3.1 Modèles usuels.
Les modèles usuels pour l’analyse des arbres digitaux supposent que les clés soient
de longueur infinie. En pratique, ce n’est (évidemment !) pas toujours le cas. Le plus
souvent, les modèles à clés infinies peuvent être vus comme une approximation
de la réalité informatique, suffisante pour l’analyse, mais il existe des situations
dans lesquelles le modèle naturel est le modèle fini (par exemple, en géométrie
algorithmique).
5 Les sources sans mémoire sont parfois appelées sources de Bernoulli car dans le cas binaire
les caractères produits correspondent à un processus de Bernoulli. Nous ne reprenons pas cette
terminologie ici puisqu’il y aura un risque de confusion avec le modèle de Bernoulli désignant un
ensemble de cardinal fixé.