Markov Text Generation

Page web ISIMA
Fichier .org source
Défi de programmation - Markov Text Generation

web_cover.png?fit=1050%2C450&ssl=1

1. Introduction

Le but de l’exercice est de, à partir d’une phrase donnée, repérer les combinaisons de mots possibles et d’ensuite générer une phrase commençant par une suite de mots donnée, la phrase est générée avec les combinaisons trouvées plus tôt.

2. Approche utilisée

2.1. Description synoptique

A partir de la phrase seed (la phrase que l’on veut compléter procéduralement), on regarde les d premiers mots (d est la depth donnée), et on regarde dans la phrase d’exemple les mots qui peuvent suivre.
Si plusieurs mots peuvent suivre on en choisi un aléatoirement.
On répète l’opération jusqu’à avoir une phrase de longueur souhaitée.

2.2. Algorithme

Fonction getWord :
Prend en entrée une phrase, un index, une chaîne de caractères result, et renvoie le mot numéro index de la phrase dans result. Avec index=0, result est égal au 1er mot de phrase.
Count = 0
wordIndex = -1
Pour chaque caractères de phrase :

  • Count = 0

  • Tant que le caractère n’est pas un espace :

    • Incrémenter Count
    • Passer au caractère suivant

    Fin tant que

  • Si Count > 0 :
    • Incrémenter wordIndex
    • Si wordIndex = index :

      • Pour chaque Count précédents caractères :

        • Ajouter le caractère à result

        Fin pour

      • Sortir de la fonction

Fin pour

Fonction wordCount :
Prend en entrée une phrase et renvoie le nombre de mot dans cette phrase. Il y a nombre d'espaces + 1 mots dans la phrase.
Count = 0
Pour chaque caractères de phrase :

  • Si le caractère est un espace :
    • Incrémenter Count

Fin pour
Renvoyer Count + 1

Fonction map :
Prend en entrée une phrase, une depth, une clé inKey composé de depth mots et une valeur de retour inValue, renvoie dans inValue le tableau des mots qui suivent la clé à chaque fois que celle-ci est trouvée dans la phrase. La fonction renvoie le nombre de fois où la clé apparait.
Index = 0
Pour chaque mots (noté mot1) de la phrase, excluant les depth derniers mots :

  • variable key : une chaîne de caractères contenant mot1
  • variable value : une chaîne de caractères vide

  • Pour chaque depth-1 suivant mots (noté mot2) :

    • key = key + «   » + mot2

    Fin pour
    value = mot suivant les depth mots

  • Si key et inKey sont identiques :
    • Ajouter value au tableau inValue
    • Incrémenter Index

Fin pour
Renvoyer Index

Fonction principale :
t : le texte d’entrée
d : la depth souhaitée
l : la longueur du texte de sortie souhaitée
s : le début du texte de sortie
Boucle de d jusqu’à l :

  • variable key contenant les depth précédents mots
  • variable possibleValues : tableau de chaîne de caractères
  • mise à jour de possibleValues avec la fonction map
  • num = valeur de retour de map
  • index = valeur aléatoire entre 0 et num
  • s = s + «   » + élément index de possibleValues

Fin pour
Afficher s

3. Résolution

3.1. Programme

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define M 1001

int random_seed = 0;
int pick_option_index(int num_of_options ) {
    random_seed += 7;
    return random_seed % num_of_options;
}

// Récupère le n-ième mot de la phrase
void getWord(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 (=nbr d'espaces + 1)
int wordCount(char phrase[]) {
    int count = 0;
    int n = strlen(phrase);
    for (int i = 0; i<n; i++) {
        if (phrase[i] == ' ') {
            count++;
        }
    }
    return count+1;
}

// A partir d'une chaine de caractere, récupère le mot qui suit
// liste de mots si la chaine d'entrée est présente plusieurs fois
int map(char phrase[], int depth, char inKey[], char inValue[M][M]) {
    int index = 0;
    int max = wordCount(phrase);

    for (int i=0; i<max-depth; ++i) {
        char key[M];
        char value[M];

        getWord(phrase, i, key);
        for (int j=1; j<depth; j++) {
            char tmp[M];
            getWord(phrase, i+j, tmp);
            sprintf(key, "%s %s", key, tmp);
        }
        getWord(phrase, i+depth, value);

        if (strcmp(inKey, key) == 0) {
            strcpy(inValue[index], value);
            ++index;
        }
    }
    return index;
}


int main()
{
    // Entrées du programme
    char spc[1] = {' '};
    char t[1001];                   // text
    scanf("%[^\n]", t);             //
    int d;                          // depth
    scanf("%d", &d);                //
    int l;                          // lenght
    scanf("%d", &l); fgetc(stdin);  //
    char s[1001];                   // seed text
    scanf("%[^\n]", s);             //

    // A partir du texte d'entrée, regarde le mot suivant possible
    // Recommence jusqu'à avoir la longueur de phrase souhaitée
    char key[M], tmp[M];
    int num;
    for (int i=d; i<l; ++i) {
        getWord(s, i-d, tmp);
        strcpy(key, tmp);
        char possiblesValues[M][M] = {};

        for (int j=1; j<d; ++j) {
            getWord(s, i-(d-j), tmp);
            sprintf(key, "%s %s", key, tmp);
        }
        num = map(t, d, key, possiblesValues);
        sprintf(s, "%s %s", s, possiblesValues[pick_option_index(num)]);
    }
    printf("%s", s);

    return 0;
}

3.2. Test

A partir du test suivant (markovText.txt) :

one fish is good and no fish is bad and that is it
1
4
one

A partir du texte donnée et d’un texte seed, le programme génère la suite du texte :

one fish is good

4. Comparaison avec une autre solution

A partir de cette solution externe :

#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);
}

Cette solution propose la création d’un dictionnaire associant un clé (une chaîne de caractères contenant d mots) à une valeur (une liste de mots). Des fonctions permettent de la lecture et écriture du dictionnaire.
Le programme lit d’abord la phrase afin de construire le dictionnaire et ensuite reconstruit une phrase à partir du dictionnaire construit.

5. Bilan

J’ai compris assez rapidement le principe du problème posé, mais j’ai trouvé l’implémentation plus compliquée que ce que je ne pensais et m’a demandé beaucoup de temps. Je suis conscient que ma solution n’est pas la meilleure d’un point de vue efficacité mais elle fonctionne et j’ai eu du mal à implémenter une solution plus efficace.

Auteur: Rémi SCHIRRA

Created: 2024-05-03 ven. 13:47