Statistique des n-grammes

Voici comment engendrer un texte synthétique à partir d'un échantillon réel (comme il a été dit, pour l'instant nous travaillons au niveau des lettres, les mots viendront plus tard).

Rappelons comment on construit le dictionnaire avec les fréquences des lettres, ensuite montrons l'assemblage des distributions multidimensionnelles.

La chaîne sg (le résultat d'un simple nettoyage du texte verne.txt) sera traitée par la fonction suivante :

def freq1(txt):
    d={}
    for c in txt:
        d[c]=d.get(c,0)+1 # get: contenu ou val. par défaut
    return d
Et le test :
>>> freq1(sg)
{',': 13782, '4': 63, 'n': 51836, '2': 144, 'â': 408, '9': 34,
 '°': 96, 'd': 26122, 'p': 19897, 'ç': 391, ')': 2, ';': 270,
 'ë': 16, 'o': 36083, '(': 2, 'g': 6426, '5': 71, 'q': 7924, 
 'f': 6994, 'j': 4199, 'i': 49595, 'l': 37146, '«': 531, 
 '8': 100, 'y': 1478, '!': 1049, 'ô': 453, 'h': 5378, 
 'r': 45036, '.': 7640, 'z': 1042, 'w': 109, '_': 1730, 
 ':': 162, '»': 509, 't': 46947, '&': 2, 'a': 53952, '0': 83,
 's': 59282, 'e': 100980, '6': 94, '1': 269, 'c': 21763, 
 '-': 5567, ' ': 143204, 'b': 6089, 'u': 42241, 'û': 334, 
 'v': 10149, 'm': 21094, '7': 106, 'é': 12872, 'k': 202, 
 'ù': 228, "'": 8313, 'ê': 1233, 'ï': 36, '?': 764, '3': 88,
 'è': 2514, 'x': 3095, 'æ': 2, 'à': 3320, 'î': 595}
Il faut normaliser cette distribution, calculer la somme d'occurrences, et diviser les nombres par cette somme. Calculer la somme peut se faire de plusieurs manières, par une boucle explicite :
dv=freq1(sg); sm=0
for ch in dv: sm+=dv[ch]
for ch in dv: dv[ch]/=sm
Pour les fréquences des n-grammes de longueur quelconque, le code est similaire ; le calcul de la somme normalisante est plus simple :
def freqn(txt,n):
    d={}
    for i in range(len(txt)-n+1):
        c=txt[i:i+n]
        d[c]=d.get(c,0)+1
    sm = sum(list(d.values()))
    for c in d: d[c]/=sm
    return d

d1=freqn(sg,1); d2=freqn(sg,2)
d3=freqn(sg,3); d4=freqn(sg,4)
On peut avoir l'impression que la mémoire nécessaire pour la sauvegarde des n-grammes explose vite, mais la répartition des fréquences des séquences plus longues est déséquilibrée, plusieurs manquent. Ainsi le dictionnaire des fréquences des lettres a 65 clés, mais d2 au lieu de $65\cdot 65 = 4225$, seulement 1092, et d3 : 7831. [[doc.:freqn.py]]

La génération d'un texte qui respecte les probabilités des caractères individuels, est la combinaison des fonctions ci-dessus.

def frgen1(dct):
    cles,vals = zip(*dct.items())
    cdist=cumsum(vals)
    def fun():
        r=random(); k=0
        while r > cdist[k]: k+=1
        return cles[k]
    return fun

f1=frgen1(dv)
stxt=''.join((f1() for i in range(2000)))
Ceci donne (par exemple)
ere l tat osersqisea-pnun ateîéniemiaeizr l- l  isrtd'  t  qg
ear rinlttls cnir  n r1iei'qruéélltose !etn uujeiatt dhiivt'
epciuetsrrsrefncaa ono,iteau a tp sc .nitesa-eima  meu nrnbtc 
u'  iose- âp nmei fntglanqeolrarjr n ots ta einej,sarm oestrt 
uiauidgéieeic.i'e u s a eat t ttavud u  nd.iss. bnameld. eloa 
t»doelsvseacé'efm ruyta hurue rtitrdieee e'aaudveg  s  iyan 
ùilotetu aabeeeoiètneseep eir?loseo'isulrucéllys , ...
Rien de fascinant... Observez l'usage de quelques techniques de programmation Python qui peuvent vous être inconnues.

Construction des probabilités conditionnelles

Passons à la construction des générateurs plus "réalistes". Afin de construire $p(l_2|l_1)$ il faut avoir les probabilités des 1- et des 2-grammes.

La structure de données qui décrira la n-distribution, sera un dictionnaire double. Les clés de ce dictionnaire sont des (n-1)-grammes, donc pour une 2-distribution : des caractères. La valeur correspondante est un dictionnaire secondaire, indexé par le caractère suivant (par ex. le second) et la valeur correspondante est la probabilité conditionnelle en question.

def pcond(d1,d2):
    res={}   # Le résultat final
    for ch in d1:   # Première clé
        p1=d1[ch]
        dch={}      # Dictionnaire interne
        res[ch]=dch
        for c2 in d2:
            if c2[0]==ch:  # Second car. si le 1er OK:
                dch[c2[1]]=d2[c2]/p1
    return res
Un très petit problème numérique peut nous pourrir la vie : à cause de la division, la probabilité conditionnelle risque d'être très légèrement dé-normalisée, ceci demande des micro-corrections, qui ne seront pas discutées ici.

Le dictionnaire obtenu ainsi peut être utilisé pour la synthèse, qui sera séquentielle, caractère après caractère. Le synthétiseur est un automate dont l'état est le caractère courant, qui vient d'être engendré. On n'a pas besoin d'autre information, de l'historique, c'est un automate "à mémoire très courte". Un tel procédé porte le nom de processus de Markov.

Le tableau (dictionnaire) de probabilités conditionnelles sera directement utilisé pour la génération aléatoire non-uniforme. Mais une petite optimisation se suggère : il est inutile de garder ce dictionnaire à deux niveaux, le dictionnaire interne sert uniquement pour piloter le générateur aléatoire. La ligne verte res[ch]=dch doit être éliminée, et avant le retour de res, nous ajoutons res[ch] = frgen1(dch).

La génération est le programme suivant :

d11 = pcond(d1,d2)
c0=frgen1(d1)();  l=[c0] # pour bien commencer
for i in range(4000):
    c1=d11[c0]();  l.append(c1)
    c0=c1   # L'état actuel change
Finalement : txt2 = ''.join(l) est le texte résultant. Pas la peine de le montrer ici. Il faut aller plus loin. Une généralisation assez faible de notre processus de Markov spécifie l'état courant comme étant le dernier (n-1)-gramme engendré : les derniers $n-1$ caractères du dernier n-gramme. Pour démarrer il faudra synthétiser le premier caractère comme 1-gramme, ensuite le second comme ci-dessus, et nous pourrons utiliser les dictionnaires d3, d4, etc.

La procédure qui tire le caractère suivant étant donnés les deux dictionnaires, n- et (n-1)- est presque identique que dans le cas $n=2$.

def ngram(d1,d2):
    res={}
    for ch in d1:
        p1=d1[ch]
        dch={}
        for c2 in d2:
            if c2[:-1]==ch:
                dch[c2[-1]]=d2[c2]/p1
        res[ch]=frgen1(dch)
    return res
d21 = ngram(d2,d3);  d31 = ngram(d3,d4)   # etc. 
... j'alle-ci, airent, les ont pas. sans cer la le capitables,
et les parmétion trinsibleure, il fleur, il les -- magit 
auprès du capitaient de tunne anne ter des des se ter. 
j'apportaines mais j'accompales de marée de mons même, sa 
vastre d'heur, surface en compais la faire la signé qu'elles 
de goût avec mon charposés. ce mieur sous épais suit de qui 
famis contendernie supéries fit ned estes cylle, proment deux 
! firme, louillancs, de la nage vivre en havrille de sont 
flant étrinsieur, cour ned ...
Pour les 4-grammes le texte synthétisé ressemble beaucoup à la langue française. Les 3-grammes en français sont encore trop amorphes, mais pour quelques autres langues suffisent pleinement pour engendrer les mots "presque naturels". L'expérience que nous avons faite a l'air assez artificiel. Qu'avons nous appris d'utile?...

Les corrélations statistiques sont essentielles pour la reconnaissance superficielle d'une langue. La génération Markovienne des séquences linguistiques donne des résultats assez raisonnables, et cela suggère que notre reconnaissance est de "mémoire courte" (essentiel pour l'apprentissage de la parole par des très petits enfants).

Nous avons revisé aussi quelques techniques de programmation en Python... Répétons que la même stratégie peut être et est utilisée à un autre niveau : génération des mots. Tandis que le n-grammes au niveau de caractères produisent des mots approximatifs, avec les mots la couche lexicale est parfaite, mais la structure phrasale, la syntaxe sera incorrecte. Le modèle statistique de la langue peut être considéré incomplet.

(Cependant, quelques représentants de l'école dite "connexionniste" considèrent que les structures formelles, telles que la grammaire, ne correspondent pas aux processus mentaux humains. Ceci n'est pas une école populaire.)

La distribution fréquentielle des mots, et la synthèse des "discours" avec les vrais mots tirés d'un échantillon, feront partie d'un exercice en TP.


Avant il nous faut travailler un peu sur l'analyse : séparation et déconstruction des mots d'une langue. La section suivante du cours c'est l'analyse lexicale, et les expressions régulières.

Ces dernières sont une formalisation des mécanismes de reconnaissance (et remplacement) des chaînes, et sont absolument essentielles pour les langages formels, et la compilation, mais elles seront utiles également ici.