58
2 Aléa sur les arbres
produit par une telle source est
EDBNZRBIAENHN ZUNKDMXZWHEYMHAVZWHWJZ
UFLKHYCABAOGQBQTSRDNORGCQNXWDPSTJBASDEKXHUR.
La deuxième étape, naturelle, consiste à considérer des probabilités non uniformes
calculées à partir d’un corpus 6 (ici le tome 1 des Misérables par Victor HUGO). Nous
obtenons alors un mot qui « ressemble » déjà plus d’un point de vue syntaxique à une
phrase naturelle en français (l’alphabet contient cette fois-ci les lettres accentuées,
les caractères de ponctuation « ;., !" ?’- »), par exemple :
UEANPNAI NYO !AHNAS EERRTQSEPINÉIRVIIIVPEIVOGELDVTA EAOIELEVMAÈI,
’A TNEIE AEAO. ULNPIOAMET.
Remarque 2.23 Lorsque l’ensemble ω de n mots est constitué de mots aléatoires
indépendants pour une source sans mémoire, nous sommes dans le modèle infini
i.i.d. déjà décrit dans la définition 2.17.
Cas particulier important : alphabet binaire, A = {0, 1}. Ce sont ces sources qui
sont le plus souvent rencontrées dans les analyses car elles permettent de donner
des résultats plus « lisibles » (sans trop de paramètres et donc plus facilement
interprétables).
– Source binaire sans mémoire symétrique (appelée aussi non biaisée). Cette source
peut être vue comme le développement en base 2 d’un réel choisi uniformément
dans [0, 1]. L’alphabet est {0, 1} et les probabilités d’émettre 0 ou 1 sont toutes
deux égales à 1/2. Pour ce modèle nous avons donc p w = 1/2 |w| pour tout mot
w fini. Ce modèle sera traité en détail pour l’analyse des tries dans le chapitre 7.
– Source binaire sans mémoire biaisée avec probabilités (p, q = 1 − p) d’émettre
les symboles 0 et 1 (respectivement). Pour un mot w la probabilité fondamentale
associée est
p w = p
|w| 0 (1 − p)
|w| 1 ,
où |w| a est le nombre de symboles a présents dans w.
2.3.4 Source avec dépendance markovienne
Le prochain échelon à gravir consiste à prendre en compte les dépendances entre les
lettres. En effet, la lettre ‘T’ en anglais a toutes les chances d’être suivie d’un ‘H’.
6 Voir la page du projet Gutenberg http://www.gutenberg.org/ pour trouver des textes tombés dans
le domaine public.
2 Aléa sur les arbres
produit par une telle source est
EDBNZRBIAENHN ZUNKDMXZWHEYMHAVZWHWJZ
UFLKHYCABAOGQBQTSRDNORGCQNXWDPSTJBASDEKXHUR.
La deuxième étape, naturelle, consiste à considérer des probabilités non uniformes
calculées à partir d’un corpus 6 (ici le tome 1 des Misérables par Victor HUGO). Nous
obtenons alors un mot qui « ressemble » déjà plus d’un point de vue syntaxique à une
phrase naturelle en français (l’alphabet contient cette fois-ci les lettres accentuées,
les caractères de ponctuation « ;., !" ?’- »), par exemple :
UEANPNAI NYO !AHNAS EERRTQSEPINÉIRVIIIVPEIVOGELDVTA EAOIELEVMAÈI,
’A TNEIE AEAO. ULNPIOAMET.
Remarque 2.23 Lorsque l’ensemble ω de n mots est constitué de mots aléatoires
indépendants pour une source sans mémoire, nous sommes dans le modèle infini
i.i.d. déjà décrit dans la définition 2.17.
Cas particulier important : alphabet binaire, A = {0, 1}. Ce sont ces sources qui
sont le plus souvent rencontrées dans les analyses car elles permettent de donner
des résultats plus « lisibles » (sans trop de paramètres et donc plus facilement
interprétables).
– Source binaire sans mémoire symétrique (appelée aussi non biaisée). Cette source
peut être vue comme le développement en base 2 d’un réel choisi uniformément
dans [0, 1]. L’alphabet est {0, 1} et les probabilités d’émettre 0 ou 1 sont toutes
deux égales à 1/2. Pour ce modèle nous avons donc p w = 1/2 |w| pour tout mot
w fini. Ce modèle sera traité en détail pour l’analyse des tries dans le chapitre 7.
– Source binaire sans mémoire biaisée avec probabilités (p, q = 1 − p) d’émettre
les symboles 0 et 1 (respectivement). Pour un mot w la probabilité fondamentale
associée est
p w = p
|w| 0 (1 − p)
|w| 1 ,
où |w| a est le nombre de symboles a présents dans w.
2.3.4 Source avec dépendance markovienne
Le prochain échelon à gravir consiste à prendre en compte les dépendances entre les
lettres. En effet, la lettre ‘T’ en anglais a toutes les chances d’être suivie d’un ‘H’.
6 Voir la page du projet Gutenberg http://www.gutenberg.org/ pour trouver des textes tombés dans
le domaine public.