Markov text generation
Table of Contents
1. Introduction text generation
Vous avez créé un jeu et souhaitez que les PNJ parlent, même si cela n’a aucun sens. Étant paresseux, vous ne voulez pas écrire toutes les déclarations absurdes, vous avez donc décidé de créer un générateur de texte. Heureusement, vous disposez d’un tas de texte à utiliser comme données d’entraînement.
2. Solution expliquée
Pour cette exercice il nous faut générer du texte à partir d’une phrase de départ, dans mon code, je créer 3 fonctions:
- nombreDeMots, qui compte le nombre de mots dans une phrase.
- prendreMotX, qui vient récuperer le mot numéro X d’une phrase.
- comparaison, qui va venir comparer si deux mots sont équivalent et renvoie l’index de chacun de ces mots.
Puis dans mon main je viens boucler sur le nombre de mot que doit avoir la phrase et j’ajoute la bonne suite de mot attendue. Ceci est rendu possible avec les fonctions incluse dans <string.h>.
#include <stdlib.h> #include <stdio.h> #include <string.h> #include <stdbool.h> #define M 1001 int random_seed = 0; int pick_option_index(int num_of_options ) { random_seed += 7; return random_seed "tangle MarkovText.c" num_of_options; } // Récupère le X-ième mot de la phrase désiré void prendreMotX(char phrase[], int index, char result[]) { int i, j, count; int len = strlen(phrase); int wordIndex = -1; for (i = 0; i < len; i++) { count = 0; while (i < len && phrase[i] != ' ') { count++; i++; } if (count > 0) { wordIndex++; if (wordIndex == index) { for (j = i - count; j < i; j++) { result[j - (i - count)] = phrase[j]; } result[count] = '\0'; return; } } } result[0] = '\0'; } // Compte le nombre de mot dans la phrase a partir du nombre d'espaces int nombreDeMots(char phrase[]) { int compteur = 0; int n = strlen(phrase); for (int i = 0; i<n; i++) { if (phrase[i] == ' ') { compteur++; } } return compteur+1; } // on prends en entrée une chaine de caractere puis on vient trouver le prochain mot, // et fait une liste des mots si plusieurs mots correspondes int comparaison(char phrase[], int depth, char inKey[], char inValue[M][M]) { char map[M][M]; int index = 0; int max = nombreDeMots(phrase); for (int i=0; i<max-depth; ++i) { char key[M]; char value[M]; prendreMotX(phrase, i, key); for (int j=1; j<depth; j++) { char tmp[M]; prendreMotX(phrase, i+j, tmp); sprintf(key, ""tangle MarkovText.c"s "tangle MarkovText.c"s", key, tmp); } prendreMotX(phrase, i+depth, value); if (strcmp(inKey, key) == 0) { strcpy(inValue[index], value); ++index; } strcpy(map[i], key); } return index; } int main() { //initialisations de la profondeur et de la longueur //initialisations de la phrase de base ainsi que le début de la phrase à générer char spc[1] = {' '}; char t[1001]; scanf(""tangle MarkovText.c"[^\n]", t); int d; scanf(""tangle MarkovText.c"d", &d); int l; scanf(""tangle MarkovText.c"d", &l); fgetc(stdin); char s[1001]; scanf(""tangle MarkovText.c"[^\n]", s); char key[M], tmp[M]; int num; //ajoute les bons mots dans la phrase à générer selon les mots antécédants for (int i=d; i<l; ++i) { prendreMotX(s, i-d, tmp); strcpy(key, tmp); char possiblesValues[M][M] = {}; for (int j=1; j<d; ++j) { prendreMotX(s, i-(d-j), tmp); sprintf(key, ""tangle MarkovText.c"s "tangle MarkovText.c"s", key, tmp); } num = comparaison(t, d, key, possiblesValues); sprintf(s, ""tangle MarkovText.c"s "tangle MarkovText.c"s", s, possiblesValues[pick_option_index(num)]); } printf(""tangle MarkovText.c"s", s); return 0; }
3. Tests et exécutions
Les test sont intéligents pusiqu’ils ajoutent plusieurs fois les même mots afin de nous faire utiliser 1/ la génération aléatoire 2/ la profondeur de la phrase pour déterminer le prochain mot.
Test avec comme entrées
gcc -Wextra -Wall -Werror MarkovText.c ./a.out stop there once was a girl named dorothy stop dorothy had a dog named toto stop dorothy lived with her aunt and uncle with her dog named toto stop she was a girl of who dreamed of traveling stop 3 10 stop dorothy had
Résultat:
stop dorothy had a dog named toto stop dorothy lived
4. solutions de la communauté
Dans la solution de MJZ, il recrée le principe de dictionnaire afin de chercher et de trouver efficacement des mots avec une clé, il utilise lui aussi des fonctions de <string.h>.
#include <stdio.h> #include <string.h> char t[1001], s[1001], dict[500][50][50]; int d, l, ndict, options[500]; int pick(int i){ static int seed = 0; return (seed += 7) % i; } int dictcmp(int a, int b){ for(int i = 0; i < d; i++) if(strcmp(dict[a][i], dict[b][i])) return 1; return 0; } int dictfind(){ int j = 0; for(; dictcmp(j, ndict); j++); return j; } char* read(char **p){ char *q = NULL; for(int i = 0, n; i < d; i++){ if(sscanf(*p, "%s%n", dict[ndict][i], &n) != 1) return NULL; *p += n; if(q == NULL) q = *p; } return q; } void makedict(char *p){ char *q = read(&p); if(q == NULL) return; int j = dictfind(); if(sscanf(p, "%s", dict[j][d + options[j]++]) != 1) return; if(j == ndict) ndict++; makedict(q); } int main(){ scanf("%[^\n]", t); scanf("%d%d\n", &d, &l); scanf("%[^\n]", s); makedict(t); char *p, *p2, *p3 = s; for(;;){ p2 = p3; p3 = read(&p3); if(p3 == NULL) break; p = p2; p3++; l--; } l -= d - 1; while(l--){ p = read(&p); int j = dictfind(); strcat(s, " "); strcat(s, dict[j][d + pick(options[j])]); } puts(s); }