7.2 Analyses asymptotiques
323
σ 0 = 1
(s) =
1
h(S)
1
s − 1
+ O(1),
où h(S) est l’entropie de la source (définie dans l’équation (7.31)) et qui possède
soit une région sans pôles à droite (s) = 1, soit une infinité de pôles régulièrement
espacé sur la droite (s) = 1 mais une bande sans pôles à gauche de cette droite.
Dans le deuxième cas, la source est dite périodique.
Pour conclure et donc appliquer la formule de Rice (7.34), nous avons besoin
de calculer le résidu de G n (s) en s = 1. Ceci revient principalement à connaître le
développement en série de Laurent de (s)/(s − 1) au voisinage du pôle s = 1.
Une fois ce développement obtenu, cela est chose facile (du moins tout logiciel de
calcul formel en est capable) de calculer le résidu.
Dans les cas de la taille et de la longueur de cheminement externe, nous calculons
le développement en série de Laurent au voisinage de s = 1 :
– Taille :
(s) = (s − 1))(s)
=
1
h(S)
+ O(s − 1).
– Longueur de cheminement externe :
(s) = ss(s)
=
1
h(S)
1
s − 1
+ O(1).
Un calcul de résidu donne alors la proposition suivante
Proposition 7.39 (Taille et longueur de cheminement d’un trie) Les espérances
de la taille S et de la longueur de cheminement externe d’un trie construit sur n
mots produits par une source probabilisée S domestiquée sont
E n [S] =
⎧
⎨
⎩
n
1
h(S) + ϕ(log n)
+ o(n) si la source est périodique
n
h(S) + o(n)
sinon.
E n [] =
1
h(S)
n log n + O(n),
où h(S) est l’entropie de la source et ϕ(u) est un terme oscillant de moyenne nulle
et de très faible amplitude (de l’ordre de 10 −5 ).