Pour générer un mot, il suffit de générer une suite aléatoire de lettre, et pour générer une lettre aléatoire il suffit de générer un nombre aléatoire, et pour générer une nombre aléatoire il suffit d'une source d'entropie quelconque, cet source d'entropie est généralement une broche de la carte mère qui pendouille dans le vide et qui est soumise à des fluctuations électromagnétiques, au bruit thermique et aux interférences ambiantes, ce qui fait varier sa tension de façon apparemment aléatoire.
Prenons l'alphabet suivant:
| a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z |
Cet alphabet contient 26 lettres, ce qui veut dire que la probabilité de tirer une lettre au hasard est de 1/26 (3,85%) pour chaque lettre. Comme toutes les lettres ont la même chance d'être tirée, on dit que la distribution est uniforme. Autrement dit, c'est complètement nul pour générer des mots qui sonnent bien:
On peut déjà améliorer cette distribution en lui donnant la forme de la distribution de fréquence d'apparition des lettres dans une langue donnée (ici le français). On a donc une distribution... pas uniforme (informe ? difforme ?):
| a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z |
Cet approche possède un problème fondamental: elle ne respecte pas les enchaînements de lettres.
Prenons un exemple concret: en français, les lettres G et N sont très souvent voisines (lasagne, châtaigne, gnôle...) tandis que les lettres X et F ne se suivent jamais. Notre génération basée uniquement sur les fréquences d'apparitions pourrait (et ne devrait pas) générer X→F puisque l'on génère lettre par lettre, indépendamment de la précédente.
On génère toujours des mots pourris.
Pour affiner notre modèle, on peut donc prendre en compte l'enchaînement de lettre. Par exemple, donner 11.8% de chance à G→N d'apparaître, et 0% de chance à X→F.
Si on applique ce principe à toute les combinaisons de lettres (A→A, A→B, A→C...Z→Z), on obtient une matrice de transition. C'est la jolie matrice colorée ci-dessus !
Cet enchaînement s'appelle une chaîne de Markov, et comme on a regardé une (1) lettre puis une autre, c'est une chaîne de Markov d'ordre 1.
Hélas, ces enchainements/chaînes/transitions, d'ordre 1 ont aussi un problème: la transition G→N est fréquente, la transition N→T l'est aussi, mais la transition G→N→T n'existe pas en français. Pour résoudre ce problème il faut donc prendre en compte deux (2) lettres suivies d'une autre (AA→A, AA→B, AA→C...ZZ→Z) les lecteurs les plus attentifs auront donc devinés qu'il s'agit là une chaîne de Markov d'ordre 2. Malin !
On peut donc généraliser une chaîne de Markov d'ordre N par la transition de N lettres A vers B. Ces "A" comme je les appelle, sont appelés des n-grammes (monogramme, bigramme, trigramme...) selon l'ordre. Mais je trouve ça complètement nul parce que B n'a pas de nom.
Selon ma notation, une transition d'ordre N de A vers B donnerait donc quelque chose comme: (A)N→B.
Pour un alphabet de taille T (26 en l'occurence) et un ordre N, on a donc T^(N+1) transitions possibles. Pour notre ordre 1, T²=26²=676 transitions, des broutilles pour un ordinateur ! Un ordre 10 ? 26^10 = environ 141 000 milliards de transitions. C'est pour ça que j'ai choisi de n'afficher que la matrice d'ordre 1; la matrice d'ordre 2 étant déjà trop longue.
Pour notre générateur de mot "plausibles" l'ordre 1 ne suffit pas comme nous l'avons vu, l'ordre 2 est peu mieux, mais je trouve que l'ordre 6 donne les meilleurs résultats.
J'aimerais faire un gros bigup à David Louapre de la chaîne ScienceEtonnante qui a fait une super vidéo qui explique tout ça sûrement mieux que moi. En tout cas sa vidéo m'a donné une frustration terrible: et en anglais alors ? et en espagnol ? pourquoi s'arrêter à l'alphabet latin, quid du grec et du cyrillique ?
En quête de réponse, je me suis tourné vers le Projet Gutenberg cité dans la vidéo, qui est une gigantesque archive de livres dans le domaine public dans plein de langues. En téléchargeant l'ensemble des livres (txt-files.tar.zip) on peut faire des tas de trucs chouettes, notamment calculer ces chaînes de Markov.
Parmis l'étagère gigantesque qui trône dorénavant dans mon SSD, se trouve des livres écrits dans tout un tas de langues différentes. L'anglais, le français, l'italien... tout ça est bien trop classique. Il y a des livres en arapaho, en langues mayas ou encore en maori.
Chaque livre est accompagné de métadonées XML (rdf-files.tar.zip) qui nous permettent de filtrer les livres: est-ce qu'un livre anglais du 15ème siècle est pertinent pour entraîner notre générateur de mot ? Et si le livre est écrit ici et là en plusieurs langues ?
Mon premier programme (books.c) trie donc les livres ainsi, et génère une liste de livres exploitables par langue.
"Qu'importe le flacon, pourvu qu'on ait l'ivresse !" je sais plus qui a dit ça mais c'est à peu près ma stratégie.
Mon second programme (words.c) ouvre un livre, lit mot à mot et le stocke dans une hashmap, la valeur étant le nombre de fois que le mot apparaît. Les mots capitalisés sont exclus, pour éviter de stocker des noms propres. Une fois qu'on a généré tout les mots, on peut regarder quels mots apparaissent trop peu de fois pour les supprimer.
Mon triage de mot étant si sommaire, les chiffres romains (xv, xvi, ii, iii...) par exemple sont sélectionnés, et ça empoisonne un peu le dataset. Les dictionnaires de vieux mots sortis "récemment" sont aussi un problème.
Dans les années 60, les américains inventent le standard ASCII afin d'encoder des caractères imprimables de façon standardisée. À l'époque, l'octet 0001'0010 pouvait signifier 'e' ou bien '7' d'un ordinateur à l'autre. Ce standard permet donc d'uniformiser la façon dont "l'alphabet" est encodé en binaire.
L'anglais n'est pas une langue qui utilise des accents contrairement au français, donc pour imprimer 'ç' ou 'à' en ASCII vous pouvez aller voir ailleurs. Cet ailleurs c'est l'UTF-8, un encodage à longueur variable de 1 à 4 octets. L'UTF-8 permet d'élargir significativement la possibilité de caractères imprimables, ce qui est... super cool...
C'est particulièrement embettant pour calculer des chaînes de Markov par exemple, mais bon c'est pas comme si c'était notre projet...
"Calculer" une chaîne de Markov d'ordre N, revient simplement à enregistrer toutes les combinaisons de lettres de longueur N qui se trouvent dans un mot. Par exemple dans le mot "bonjour", pour un ordre 2 on va avoir ces transitions:
Traduisons à la louche l'algorithme:
Bon, très bien, faisons ça sur le mot "bonjour":
| . | . | . | . | . | . | . |
|---|---|---|---|---|---|---|
| b | o | n | j | o | u | r |
char* word = "bonjour";
size_t wordlen = strlen(word);
size_t window_width = order + 1;
for (size_t i=0; i <= wordlen - window_width; ++i) {
char* token_A = strndup(word + i, window_width - 1);
char* token_B = strndup(word + i + window_width - 1, 1);
char* transition = strndup(word + i, window_width);
... // stockage hashmap
}
Facile hein ? Sauf que dans ce cas le mot est uniquement composé de caractères ASCII de 8 bits, donc pour se "décaler de 1 lettre" il suffit simplement de se décaler de 1 octet (++i). Sauf qu'en UTF-8, le concept de longeur de lettre est variable !!! Donc on peut pas se décaler de 1 octet et forcément tomber sur une nouvelle lettre !!! on pourrait tomber en plein milieu d'un octet UTF-8 !!!
Utilisons maintenant la traduction de "bonjour" en espagnol: "boñjour". Ce mot possède une lettre 'ñ' encodée sur 2 octets. Les autres lettres ont le même encodage qu'en ASCII car l'UTF-8 est rétro-compatible, c'est-à-dire 1 octet:
| . | . | . | . | . | . | . | . |
|---|---|---|---|---|---|---|---|
| b | o | ñ | j | o | u | r | |
Il faut maintenant décoder codepoint par codepoint ce qui est beaucoup plus embettant:
char* word = "boñjour";
size_t wordlen_cp = utf8len(word); // how many codepoints in the word
size_t remaining = wordlen_cp; // how many codepoints left in the word when we slide the window
size_t window_width = order + 1; // width = 3 for a markov(2), 4 for a markov(3), etc.
utf8_int8_t* win = word; // window pointer
// slide the window until we bump the end of the word
while (remaining >= window_width)
{
// slide codepoint by codepoint in the window
utf8_int8_t* tok = win;
size_t token_A_size = 0;
for (int i=0; i < window_width - 1; ++i) {
utf8_int32_t cp;
utf8_int8_t* next = utf8codepoint(tok, &cp);
token_A_size += utf8codepointsize(cp);
tok = next;
}
size_t token_B_size = utf8codepointcalcsize(tok);
char* token_A = strndup(win, token_A_size);
char* token_B = strndup(tok, token_B_size);
char* transition = strndup(win, token_A_size + token_B_size);
... // stockage hashmap
// advance to the next codepoint = next window
win += utf8codepointcalcsize(win);
remaining--;
}
Une fois les transitions, A et B stockés dans des hashmaps dont la valeur correspond au nombre de fois qu'on l'a vu ; il faut normaliser chaque transition par la somme des occurences des A, c'est à dire ramener à une valeur entre 0 et 1.
Par exemple, pour toutes les combinaisons de C: C→A, C→B, C→C, C→D... quand notre générateur de mot a la lettre 'C' et doit choisir quelle lettre mettre ensuite, il doit faire un tirage difforme comme on l'a vu précédemment. prob(C→A) = 11,1%, prob(C→B) = 0,1%, prob(C→C) = 3.1%, etc.
Nouveau problème !
Pour chaque A, il faut parcourir chaque B afin de calculer la somme de tout les A pour normaliser les transitions. Cela veut dire qu'il faut parcourir A*B données soit T^(O+2)... Pour un ordre 5, il faut parcourir T^7 = 26^7 = 8 milliards de transitions.
On peut se dire "bon aller mon PC est rapide" oui mais ta RAM est terriblement plus lente que ton CPU et jamais de la vie 8 milliards de transitions tiennent dans les caches L1, L2 et L3 du CPU. Avec cet algorithme, je calculais toutes les chaînes d'ordre 1 à 5 de toutes les langues en une trentaine de minutes, ce qui est très mauvais.
Cet algorithme de normalisation a une complexité temporelle O(N²), et on peu la rendre linéaire (ou O(NlogN) je sais pas trop). Plutôt que de partir de A et de B, puis de fabriquer la clé "AB" afin de récupérer la valeur dans la hashmap, on peut plutot parcourir la hashmap et extraire A et B ! En français, il n'y a aucun mot qui contient "XWQZ" donc la transition "XVQZ" n'a jamais été enregistrée dans notre hashmap. Toutes ces absences de combinaisons font baisser drastiquement le nombre de clé à récupérer.
La question qui se pose c'est: comment j'extrais A et B de "AB" ? J'ai trouvé un trick sympa. On part du principe que B est toujours une seule lettre. Il suffit donc de partir de la fin de la transition "AB" et de remonter octet par octet. Si l'octet est un caractère ASCII ou bien un header UTF-8 (qui sert à dire "je fais n octets"), on a notre B. Sinon, et bien on remonte encore d'un octet. Supposons la transition "ubô":
| . | . | . | . |
|---|---|---|---|
| u | b | ô | |
En vert les caractères ASCII, en bleu le header UTF-8, en orange un octet de continuation UTF-8.
char* transition = transitions[i].key; // "ubô"
size_t transition_len = strlen(transition);
char* token_B = transition + transition_len;
while (token_B > transition)
{
token_B--; // walk backward 1 byte
unsigned char c = (unsigned char)*token_B;
// ASCII (0-127) or header UTF-8 (C0-FF)
if (c < 128 || c >= 0xC0) break;
// else: UTF8 continuation byte -> walk backward more
}
// Normalize
char token_A[256];
size_t lenA = transition_len - strlen(token_B);
memcpy(token_A, transition, lenA);
token_A[lenA] = '\0';
transitions[i].value /= shget(tokens_A->set, token_A);
On peut trivialement déduire A à partir de B, et comme on a stocké dans la hashmap de A le nombre de fois où A apparaît, on peut diviser le nombre de fois que la transition apparait par le nombre de fois que A apparaît. Ouf ça en fait des apparitions...
Notons que je travaille au niveau des octets et que l'UTF-8 est un problème uniquement parce que je programme en C. David Louapre l'a fait en 45 lignes de Python mais le Python c'est nul et le C c'est plus rigolo.
Avec ces algorithmes, les 30 minutes sont descendues à... 8 secondes.
Il faut exporter nos distributions informes en objet Javascript afin de pouvoir générer les mots sur ce site. Au début je pensais exporter en C, puis compiler ce C en WASM afin de réduire la taille des matrices. Que nenni ! La compression gz ou brotli revient à la même chose en JS ou en WASM. Le seul avantage du WASM serait d'accéder plus rapidement aux valeurs des matrices, mais pour générer 6 ou 7 lettres le JS est assez rapide.
Bon alors comment on génère une lettre avec une distribution informe ? La somme de toutes les probabilités font 1, donc on peut les arranger sur une ligne de 0 à 1. Par exemple les probabilités de 'a' (au pif):
| 0 | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1 |
| a | b | c | d | ||||||
On génère un nombre aléatoire entre 0 et 1, et on place la valeur qu'on obtient sur cette échelle. La zone dans laquelle on tombe nous donne la prochaine lettre.
Quelques mots rigolos en français:
Au delà de l'ordre 4, les mots générés sont souvent des mots qui existent.
Les données Gutenberg et le code source sont disponibles ici:
J'ai compilé avec clang, GCC et MSVC sans problème. J'utilise une seule translation unit donc une seule invocation du compilateur est nécessaire:
$> gcc -O3 books.c -o books.exe $> gcc -O3 words.c -o words.exe $> gcc -O3 markov.c -o markov.exe
Attention sur Linux a pas appeler le programme le même nom que les dossiers (books/ words/ markov/).
Liste des super librairies que j'ai utilisé: