Markov Text Generation

Table of Contents

Retour vers le site

google.png

Figure 1: Google Search Prediction

1. Présentation du problème

Le but de cet exercice est de réussir à générer du texte grace à une chaine de caractère d’entrainement. Pour illustrer le problème, on peut prendre l’exemple de la completion de recherche sur Google. Lorsque l’on tape 2 mots, Google nous propose ensuire une multitude de recherche qui pourrait nous convenir. 1 Pour cela nous allons donc nous baser sur les principes de n-gramme et de Chaîne de Markov.

1.1. Qu’est-ce qu’un n-gramme ?

Un n-gramme est une sous-séquence de n éléments construite à partir d’une séquence donnée.2 Prenons un exemple :

  • Séquence : "one fish is good but no fish is bad and that is it"

Je décide de faire par exemple un 2-gramme (ou bien bi-gramme). Nous allons donc faire des groupes de 2 éléments (ici des mots) à qui l’on associe le mot suivant : 

"one fish" => "is"
"fish is" => "good"
"is good" => "but"
"good but" => "no"
"but no" => "fish"
"no fish" => "is"
"fish is" => "bad"

On arrive ici à un couple déjà existant, le couple "fish is". On ajoute donc au couple déjà existant le mot suivant. 

"one fish" => "is"
"fish is" => "good", "bad"
"is good" => "but"
"good but" => "no"
"but no" => "fish"
"no fish" => "is"
"is bad" => "and"
"bad and" => "that"
"and that" => "is"
"that is" => "it"

On continue ainsi de suite jusqu’à la fin de la séquence.

1.2. Qu’est-ce qu’une chaîne de Markov ?

Une chaîne de Markov est une suite de variables aléatoires \((X_n, n \in N)\) qui permet de modéliser l’evolution dynamique d’un système aléatoire : \(X_n\) représente l’état du système à l’instant \(n\)3.

2. Code

2.1. Structures

2.1.1. WAIT Liste Chainée

  1. Définition

    Une liste chainée est une structure de donnée permettant de stocker à l’instar d’un tableau des variables de même type. Cependant, une liste chainée est de taille variable. En effet, il est possible d’ajouter et de supprimer des éléments de la liste à tout moment. En contre partie, là où le tableau permet l’accès à un élément en temps constant, celui-ci se fera en temps linéaire dans le pire des cas )Il s’agit de la dernière valeure de la liste).

  2. Maillon

    Une liste chainée est composée de Maillon qui pointent les uns vers les autres. Un Maillon est un élément composé d’une valeur et d’un pointeur vers le prochain Maillon.

    1. Implémentation en C du Maillon

      Voici une implémentation d’un Maillon possible en C. 

      typedef struct Link {
    struct Link *next;
    char *value;
} Link;

      Ici les valeurs stockées sont des chaînes de charactère.

  3. Implémentation en C de la Liste

    Voici une implémentation possible d’une Liste Chainée. 

    typedef struct LinkList{
    Link *head;
} LinkList;

    Il est à noter que la structure Liste Chainée est en réalité superficielle car il s’agit simplement d’un pointeur vers le premier Maillon de la Liste.

  4. TODO Schéma
  5. TODO Méthodes ascociées

    Afin de tirer profit de notre Liste Chainée, il convient de lui ascocier quelques méthodes.

    1. Initialiser une Liste

      Il paraît indispensable de savoir créer une liste afin de l’initialiser. Pour celui voici mon implémentation. 

      LinkList *init(char *value){
    LinkList *liste = malloc(sizeof(LinkList));
    Link *maillon = malloc(sizeof(Link));

    if (liste == NULL || maillon == NULL){
        exit(EXIT_FAILURE);
    }

    maillon->value = value;
    maillon->next = NULL;
    liste->head = maillon;

    return liste;
}
    2. WAIT Insérer un élément

      Une autre fonction assez trivial est le fait de pouvoir insérer un élément dans notre Liste. Dans notre implémentation, l’élément est inséré à la tête de notre liste. L’opération ce fait donc en temps constant. 

      void insert_list(LinkList *liste, char *value){
    Link *new = malloc(sizeof(Link));
    if (liste == NULL || new == NULL){
        exit(EXIT_FAILURE);
    }
    new->value = value;
    new->next = liste->head;
    liste->head = new;
}
    3. Connaître la taille

      On pourrait se passer de cette fonction mais il est toujours confortable de l’avoir. 

      int length(LinkList *liste){
    if (liste == NULL){
        exit(EXIT_FAILURE);
    }
    int len = 0;
    Link *maillon = liste->head;
    while (maillon != NULL){
        len++;
        maillon = maillon->next;
    }
    return len;
}
    4. Connaître la valeur d’un élément

      La nécessitée de cette méthode est aussi discutable mais elle nous permet aussi un confort indéniable. 

      char* value_of(LinkList *liste, int index){
    if (liste == NULL){
        exit(EXIT_FAILURE);
    }
    int maillon_to_pass;
    if (index >= 0){
        maillon_to_pass = length(liste) - index - 1;
    } else {
        maillon_to_pass = -1 * index - 1;
    }
    Link *maillon = liste->head;
    while (maillon_to_pass > 0){
        maillon = maillon->next;
        maillon_to_pass --;
    }
    return maillon->value;
}

2.1.2. DONE Couple

La dernière structure dont nous auront besoin est celle du Couple. Comme expliqué plus tôt, nous allons devoir réaliser un n-gramme. Celui est composé de clé et de liste de chaine chaîne de charactère. Nous allons donc évidemment utiliser nos Liste Chainée crées plus haut.

  1. Implémentation en C
    typedef struct Couple{ // Couple for ngram
    struct LinkList *value;
    char key[1001];
} Couple;

2.2. Programme principal

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

int random_seed = 0;


void insert_couple(Couple ngram[], char key[], LinkList *value){
    /* Insert couple(key, value) in the array ngram */
    int i = 0;
    while (ngram[i].value != NULL) {
        if (strcmp(ngram[i].key, key) == 0) {
            insert_list(ngram[i].value, value->head->value);
            return;
        }
        ++i;
    }
    strcpy(ngram[i].key, key);
    ngram[i].value = value;
}

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

int strip_str(char sequence[], char output[][1001]){
    /* Take the sequence, cut it in words and return the number of words*/
    int i = 0, j = 0;
    int i_word = 0;

    while (sequence[i] != '\0') {
        if (sequence[i] == ' ') {
            output[i_word][j] = '\0';
            ++i_word;
            j = 0;
        } else {
            output[i_word][j] = sequence[i];
            ++j;
        }
        ++i;
    }
    return i_word + 1;
}

void join(char str1[], char str2[], char output[]){
    /* Simply join 2 string in 1 in output separated by a space */
    int i = 0, j = 0;
    while (str1[i] != '\0') {
        output[i] = str1[i];
        ++i;
    }
    while (str2[j] != '\0'){
        output[i+j] = str2[j];
        ++j;
    }
    output[i+j] = '\0';
}

void n_gram(char text_list[][1001], Couple *ngram, int depth, int length){
    /* Create the n-gram of text_list in the array ngram */
    int i, j;
    char temp[1001];
    for (i=0; i<length-depth; ++i) {
        temp[0] = '\0';
        for (j = 0; j<depth; ++j) {
            strcat(temp, text_list[j + i]);
            strcat(temp, " ");
        }
        strcat(temp, "\0");
        insert_couple(ngram, temp, init(text_list[i+depth]));
    }
}


int main()
{
    char text[1001];
    char seed[1001];
    char temp[1001];

    char explode[100][1001];
    char strip_text[100][1001] = {{0}};

    Couple ngram[1001];

    int depth;
    int output_length;
    int i, j;
    int seed_length;
    int nb_words;
    int random_number;

    scanf("%[^\n]", text);
    scanf("%d", &depth);
    scanf("%d", &output_length); fgetc(stdin);
    scanf("%[^\n]", seed);

    nb_words = strip_str(text, strip_text);
    seed_length = strip_str(seed, explode); // put in explode the list of words of seed

    n_gram(strip_text, ngram, depth, nb_words);

    printf("%s", seed);
    seed[0] = '\0';
    for (i=seed_length-depth; i < seed_length; ++i){
        strcat(seed, explode[i]);
        strcat(seed, " ");
    }
    while (output_length > seed_length) {
        i = 0;
        while (strcmp(seed, ngram[i].key) != 0){
            ++i;
        }
        random_number = pick_option_index(length(ngram[i].value));
        printf(" %s", value_of(ngram[i].value, random_number));
        strip_str(seed, explode);
        temp[0] = '\0';
        for (j=1; j < depth; ++j){
            strcat(temp, explode[j]);
            strcat(temp, " ");
        }
        join(temp, value_of(ngram[i].value, random_number), seed);
        strcat(seed, " ");
        --output_length;
    }

    printf("\n");


    return 0;
}

2.3. Explication

  • On commence par récupérer le text nous servant de modèle.
  • On récupère ensuite la profondeur de n-gramme voulu.
  • On récupère la longueur du message voulu.
  • On fini par récupérer le message de départ (seed).
  • On compte le nombre de mot du modèle.
  • On fait de même pour la seed.
  • On construit le n-gramme correspondant au modèle et à la profondeur donnée.
  • On affiche la seed puis on garde de celle-ci que les profondeur derniers mots.
  • Tant que le message renvoyé ne fait pas taille voulu :
    • On cherche la liste des mots ascossié à la nouvelle seed dans le n-gramme.
    • On en affiche une au hasard et on l’ajoute à la seed.
    • On supprime le premier mot de la seed.

2.4. Tests

Procédont maintenant à quelques tests.

2.4.1. Test de l’exemple

— INPUT — 

one fish is good but no fish is bad and that is it
2
4
fish is

— OUTPUT — 

fish is bad and

2.4.2. Test de avec une base plus longue

— INPUT — 

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

— OUTPUT — 

stop dorothy had a dog named toto stop dorothy lived

3. Solution de la communauté

Footnotes:

1

source : Google search prediction - How it works ?

2

source : Wikipédia - N Grammes

3

source : Wikipédia - Markov Chain

Author: Arthur Barraux

Created: 2024-04-17 mer. 12:32