7.2 Analyses asymptotiques
309
Nous ne traitons ici que le cas où les mots sont infinis. En effet, dans le seul
modèle fini que nous ayons considéré (modèle fini équiprobable), tous les ensembles
de n mots de longueur d sont équiprobables. Pour un alphabet binaire, cela impose
l’inégalité
n ≤ 2
d .
Ainsi si d est constant ou d’ordre sous-logarithmique par rapport à n, le modèle
présente peu d’intérêt pour les tries : dans ce cas le nombre d’ensembles de clés
sur lequel mener l’analyse est très petit voire nul. De plus, de manière informelle,
lorsque d est assez grand par rapport à log n, les résultats attendus sont à la limite
les mêmes que dans le modèle infini i.i.d. uniforme.
Pour les paramètres additifs comme la longueur de cheminement externe ou la
taille, plusieurs approches sont possibles pour accéder à un équivalent asymptotique
des expressions exactes obtenues à partir des séries de Poisson.
Dans la suite, nous exposons d’abord deux techniques moins particulières que
celles que nous venons de voir et qui s’appliquent à des sources plus générales.
Nous présentons ici trois méthodes. La première méthode, élémentaire, est
présentée dans la section 7.2.1. Elle est restreinte au modèle i.i.d. infini uniforme
sur les symboles (équivalent à la source sans mémoire binaire non biaisée).
Ensuite nous présentons dans la section 7.2.2 l’analyse asymptotique par transformée de Mellin également dans le même modèle infini i.i.d. binaire uniforme car
cela constitue l’approche classique dans la littérature.
Enfin nous présentons dans la section 7.2.3 une dernière méthode pour le modèle
plus général avec une source de la section 7.1.3, qui fait appel à une transformation
intégrale via la formule dite de Nörlund-Rice [196, 197].
Le fait qu’il y ait plusieurs approches (Mellin et Rice) n’est pas étonnant et tient
pour beaucoup au cycle Mellin-Newton-Poisson (voir la monographie de Flajolet et
al. à ce sujet [100]).
Dans la section 7.2.4 nous analyserons le paramètre multiplicatif de la hauteur.
7.2.1 Paramètres additifs : méthode élémentaire
Dans cette section, nous nous plaçons dans le modèle infini i.i.d. uniforme pour
un alphabet binaire et une distribution uniforme sur les symboles. C’est strictement
équivalent à considérer un modèle de source sans mémoire binaire symétrique qui
produit des clés indépendamment. Il est possible d’obtenir à partir des formules
exactes par dépoissonisation algébrique un équivalent asymptotique grâce à des
moyens de calculs élémentaires. Nous traitons dans cette section uniquement le cas
de la longueur de cheminement externe avec cette approche. La même méthode peut
être suivie pour la taille d’un trie dans le même modèle.
Nous notons dans cette partie L n = E n [ l’espérance de la longueur de
cheminement d’un trie à n clés dans le modèle infini i.i.d. uniforme. Nous avons
309
Nous ne traitons ici que le cas où les mots sont infinis. En effet, dans le seul
modèle fini que nous ayons considéré (modèle fini équiprobable), tous les ensembles
de n mots de longueur d sont équiprobables. Pour un alphabet binaire, cela impose
l’inégalité
n ≤ 2
d .
Ainsi si d est constant ou d’ordre sous-logarithmique par rapport à n, le modèle
présente peu d’intérêt pour les tries : dans ce cas le nombre d’ensembles de clés
sur lequel mener l’analyse est très petit voire nul. De plus, de manière informelle,
lorsque d est assez grand par rapport à log n, les résultats attendus sont à la limite
les mêmes que dans le modèle infini i.i.d. uniforme.
Pour les paramètres additifs comme la longueur de cheminement externe ou la
taille, plusieurs approches sont possibles pour accéder à un équivalent asymptotique
des expressions exactes obtenues à partir des séries de Poisson.
Dans la suite, nous exposons d’abord deux techniques moins particulières que
celles que nous venons de voir et qui s’appliquent à des sources plus générales.
Nous présentons ici trois méthodes. La première méthode, élémentaire, est
présentée dans la section 7.2.1. Elle est restreinte au modèle i.i.d. infini uniforme
sur les symboles (équivalent à la source sans mémoire binaire non biaisée).
Ensuite nous présentons dans la section 7.2.2 l’analyse asymptotique par transformée de Mellin également dans le même modèle infini i.i.d. binaire uniforme car
cela constitue l’approche classique dans la littérature.
Enfin nous présentons dans la section 7.2.3 une dernière méthode pour le modèle
plus général avec une source de la section 7.1.3, qui fait appel à une transformation
intégrale via la formule dite de Nörlund-Rice [196, 197].
Le fait qu’il y ait plusieurs approches (Mellin et Rice) n’est pas étonnant et tient
pour beaucoup au cycle Mellin-Newton-Poisson (voir la monographie de Flajolet et
al. à ce sujet [100]).
Dans la section 7.2.4 nous analyserons le paramètre multiplicatif de la hauteur.
7.2.1 Paramètres additifs : méthode élémentaire
Dans cette section, nous nous plaçons dans le modèle infini i.i.d. uniforme pour
un alphabet binaire et une distribution uniforme sur les symboles. C’est strictement
équivalent à considérer un modèle de source sans mémoire binaire symétrique qui
produit des clés indépendamment. Il est possible d’obtenir à partir des formules
exactes par dépoissonisation algébrique un équivalent asymptotique grâce à des
moyens de calculs élémentaires. Nous traitons dans cette section uniquement le cas
de la longueur de cheminement externe avec cette approche. La même méthode peut
être suivie pour la taille d’un trie dans le même modèle.
Nous notons dans cette partie L n = E n [ l’espérance de la longueur de
cheminement d’un trie à n clés dans le modèle infini i.i.d. uniforme. Nous avons