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]/=smPour 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.
[x10,x11,x12, ...], [x20,x21,x22, ...], ... [xn0,xn1,xn2,...]
, construit la liste de tuples [(x10,x20,...xn0), (x11,x21,...xn1),...], et "miraculeusement", cette fonction devient son propre inverse, si on précède l'argument (unique) par l'étoile. Ceci agit comme la transposition d'un tableau 2-dim.
Python 3 encourage avec l'insistance l'usage des mécanismes itératifs, dont plusieurs sont prédéfinis. Ceci évite la nécessité de programmer des boucles. [[Mon cours précédent de Python OO pour L2 couvre les itérateurs très sérieusement]]. Ils sont indispensables en TAL.
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 resUn 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 changeFinalement : 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.