I- Présentation du problème

A) Les entrées

B) Le but du jeu

On doit construire une chaîne de Markov classique à partir d’un exemple de texte. Pour expliquer facilement ce concept, utilisons un exemple. Étant donné les paramètres suivants:

char t[]="one fish is good and no fish is bad and that is it";
int d=2;
int l=4;
char s[]="fish is"; 

On sait donc que la graine a une longueur de 2 mots (d), on va donc former tous les n-grammes de 2 mots possibles et l’associer au mot qui suit.

Pour créer du texte, il suffit donc de prendre les d derniers mots ici les deux derniers mots de la graine ou du texte déjà créé puis écrire celui qui correspond. Si plusieurs choix son possible tel que pour fish is, on tire alétoirement un nombre pour déterminer le mot qui va suivre. Nous pouvons donc maintenant générer du texte. Pour une phrase de longueur de 4 (l) commençant par la graine (s) nous pouvons par exemple créer la phrase:

char phrase[]="fish is bad and"

C) La sortie

On doit renvoyer un texte de longueur l mots commençant par la graine s.

II- Ma méthode de résolution

A) Approche synoptique

Au départ je m’étais lancé dans l’idée d’implémenter un programme permettant de regrouper dans un tableau les n-grammes de mots et celui qui suit, néanmoins, je trouvais que cela prennait trop de mémoire, alors j’ai travaillé avec les indices des mots et plusieurs tableaux avec les mots, etc… Finalement, je résout le problème exactement comme dans l’exemple ci dessus.

B) Approche algorithmique et explication de mon programme

1.Inclusion des bibliothèques

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

2.Fonction random_seed

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

Cette fonction nous est fourni dans l’énoncé, elle permet de retourner un chiffre “aléatoire” qui ne l’est pas totalement car il est toujours le même pour permettre d’avoir une correction correcte. Finalement random_seed est une fonction mathématique que l’on applique au nombre passé en arguments.

3.Lecture des entrées (partie 1 du main)

int main()
{
    char t[1001];
    scanf("%[^\n]", t);
    int d;
    scanf("%d", &d);
    int l;
    scanf("%d", &l); fgetc(stdin);
    char s[1001];
    scanf("%[^\n]", s);
    

Cette partie du code permet de récupérer les différentes entrées qui vont nous servir par la suite. On récupère notamment le texte total dans t, puis la longueur des n-grammes de mots à former dans d, ensuite on récupère le nombre de mot de la chaine de caractère s dans la variable l et enfin on récupère la chaine de caractères s qui correspond au début de la phrase a afficher à la fin.

4.Initialisation de variables et remplissage des indices des espaces (partie 2 du main)

    int debut[1000][100];
    int indice[100][10];
    int espace[1000];
    espace[0]=0;
    char couple[1000][1000];
    int longueurEntree=strlen(t);
    int i,j,k,m,n,o,p;
    int indiceDebutMot=1;
    int nbEspace,soustraireIndice=0;
    for(i=0;i<longueurEntree;i++){
        if(t[i]==' '){
            espace[indiceDebutMot]=i+1;
            indiceDebutMot++;
        }
    }
    

Nous retrons ensuite dans une boucle for qui parcourt la chaine de caractère t du début (0) à la fin (longueurEntree-1) par pas de 1. A l’intérieur de cette dernière on regarde si l’indice actuel est un espace ou non, si oui, on va venir enregister l’indice du début du mot dans le tableau d’entier espace au travers de la ligne: espace[indiceDebutMot]=i+1, puis on vient incrémenter indiceDebutMot pour le mot suivant.

5. Remplissage des tableaux couple, indice, debut (partie 3 du main)

    for(j=0;j<=indiceDebutMot-d;j++){
        nbEspace=0;
        char chaineEnCours[1000]={0};
        for(k=espace[j],m=0;nbEspace<d;k++,m++){
            if(t[k]==' ' && nbEspace<d-1){
                nbEspace++;
                chaineEnCours[m]=t[k];
            }
            else if(t[k]==' ' && nbEspace==d-1){
                nbEspace++;
            }
            else{
                chaineEnCours[m]=t[k];
            }
        }
        chaineEnCours[m+1]='\0';
        if(j==0){
            strcat(couple[j],chaineEnCours);
            debut[j][0]=espace[j];
            debut[j][1]=1;
            indice[j][0]=espace[j+d];
        }
        else{
            int present=0,lieu=0;
            for(n=0;n<j-soustraireIndice;n++){
                if(strcmp(chaineEnCours,couple[n])==0){
                    present=1;
                    lieu=n;           
                }
            }
            if(present==1){
                soustraireIndice++;
                indice[lieu][debut[lieu][1]]=espace[j+d];
                debut[lieu][1]+=1;
            }
            else{
                debut[j-soustraireIndice][0]=espace[j];
                debut[j-soustraireIndice][1]=1;
                indice[j-soustraireIndice][0]=espace[j+d];
                strcat(couple[j-soustraireIndice],chaineEnCours);
            }
        }
    }
    

Cette partie du programme va donc dans un premier temps, parcourir la chaine de caractère t pour déterminer le premier n-grammes que l’on stocke dans le tableau chaineEnCours lettre par lettre jusqu’à ce que la variable nbEspace est atteint la valeur de d (nombre de mots du n-grammes). Ce n-grammes va être ajouté au tableau couple grâce à: strcat(couple[j],chaineEnCours.

Si c’est le premier n-grammes, on ajoute à début l’indice du début du premier mot du n-grammes par: debut[j][1]=espace[j] puis on ajoute à début le fait qu’il n’y a pour l’instant qu’une seule possibilité pour le mot suivant le n-grammes par: debut[j][1]=1. Pour finir on rempli le tableau indice en indiquant l’indice du mot suivant après ce n-grammes par l’intermédiaire de: indice[j][0]=espace[j+d].

Ensuite on répète cela jusqu’au dernier n-grammes pouvant être suivi d’un mot. Lorsqu’on a dépassé le premier n-grammes, on va vérifier si le n-grammes est déja présent dans le tableau couple grâce à la boucle for dont le compteur est n. Si le n-grammes est présent, on vient passer la variable present (initialement à 0) à 1 puis on stocke le rang auquel il a était trouvé.

Après cela, on a deux possibilités, soit le n-grammes est déjà présent, dans ce cas là, on incrémente soustraireIndice, on indique un nouveau début de mot suivant le n-grammes dans le tableau indice par: indice[lieu][debut[lieu][1]]=espace[j+d], on finit par incrémenter le nombre de possibilité de mot suivant ce n-grammes par: date[lieu][1]+=1. Le second cas est que le n-grammes n’est pas présent dans le tableu couple, dans ce cas la on fait similairement la même chose que pour le cas où on étuide le premier n-grammes de t, simplement, on soustrait soustraireIndice à j pour ne pas laisser de case vide entre le n-grammes précédent et l’actuel s’il y a eu des répétitions de n-grammes plus tôt.

6. Travail sur la graine (partie 4 du main)

    char chaineMots[100][10]={0};
    int indiceMots[100]={0};
    int indiceActuel=0;
    indiceMots[indiceActuel]=0;
    indiceActuel++;
    int q,r;
    for(q=0;q<strlen(s);q++){
        if(s[q]==' '){
            indiceMots[indiceActuel]=q+1;
            indiceActuel++;
        }
    }
    
    int indiceParcourt=0;
    
    for(r=0;r<indiceActuel;r++){
        int u;
        for(u=indiceParcourt;s[u]!=' ' && s[u]!='\0';u++){
            chaineMots[r][u-indiceParcourt]=s[u];
        }
        u++;
        chaineMots[r][u]='\0';
        indiceParcourt=u;
    }
    

On parcourt donc d’abord toute la chaine de caractère s pour déterminer le déterminer l’indice auquel débute les mots, puis on stocke cette valeur au fur et à mesure dans indiceMots avec: indiceMots[indiceActuel] puis on incrémente de 1 le compte indiceActuel pour traiter le prochain mot etc…

Ensuite on rentre dans la boucle suivante qui permet tout simplement de stocker mot par mot le contenu de la graine s dans le tableau chaineMots. Le premier mot est stocké à l’indice 0, le deuxième à l’indice suivant, etc….

7. Générration du texte (partie 5 du main)

    int v;
    for(v=0;v<l-d;v++){
        char chaineEnCours2[100]={0};
        int w;
        for(w=d-1;w>=0;w--){
            strcat(chaineEnCours2,chaineMots[indiceActuel-w-1]);
            if(w!=0){
                strcat(chaineEnCours2," ");
            }
        }
        
        int y=0;
        while(strcmp(couple[y],chaineEnCours2)!=0){
            y++;
        }
        int aleatoire=function_pick_option_index(debut[y][1]);
        int z;
        int Debutz=indice[y][aleatoire];
        for(z=indice[y][aleatoire];t[z]!=' ' && t[z]!='\0';z++){
            chaineMots[r+v][z-Debutz]=t[z];
        }
        chaineMots[r+v][z+1-Debutz]='\0';
        indiceActuel++;
    }
    

Cette partie du code permet de générer le texte en suivant le principe des chaines de Markov. On rentre dans la première boucle for et on y reste pendant l-d itérations pour compléter la graine et arriver au nombre de mot voulu. On va ensuite rentrer dans une seconde boucle for permettant de sélectionner les d derniers mots du tableau chaineMots et de les concaténer dans un tableau chaineEnCours2

Pour connaitre quel est le n-grammes qui correspond à la nouvelle graine, on rentre dans la boucle while permettant de déterminer l’indice de ce n-grammes, la valeur est stockée dans la variable y. On appelle ensuite la fonction function-pick-option-index avec comme argument debut[y][1] qui correspond au nombre de possibilité de mot suivant ce n-grammes. La valeur retourné étant stockée dans la variable aleatoire, on peut connaitre l’indice du début du mot et le stocker avec: int Debutz=indice[y][aleatoire]

Pour finir on ajoute le mot commençant par la lettre à l’indice Debutz au tableau 2D chaineMots.

Toutes ces opérations sont ensuite répétées jusqu’à obtenir le nombre de mots souhaité.

8. Affichage du texte généré (fin du main)

    int a;
    for(a=0;a<indiceActuel && a<l;a++){
        printf("%s",chaineMots[a]);
        if(a!=indiceActuel-1 && a!=l-1){
            printf(" ");
        }
    }
    return 0;
}

On finit par un boucle for des plus basique pour afficher le texte obtenu en n’oubliant pas d’ajouter des espaces entre les mots contenu dans le tableau 2D chaineMots.

III- Un autre programme

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

int choisir_option(int num,int nd_option){
    return num%nd_option;
}

int nombre_mot_chaine(char chaine[]){
    int i;
    int nb=1;
    for (i=0;i<strlen(chaine);i++){
        if (chaine[i]==' '){
            nb++;
        }
    }
    return nb;
}

int main(){
    char t[1001];
    scanf("%[^\n]", t);
    int d;
    scanf("%d", &d);
    int l;
    scanf("%d", &l); fgetc(stdin);
    char s[1001];
    scanf("%[^\n]", s);

    int i=1;
    int j=1;
    int nb_source=nombre_mot_chaine(s);
    int nb_phrase=nombre_mot_chaine(t);
    char *mot[500];
    mot[0]=strtok(t," ");    
    while(mot[i]!=NULL || i==1){        // On décompose en mot le texte
        mot[i]=strtok(NULL," ");
        i++;
    }

    char *n_gramm[nb_phrase][10]; // On définit le n_gramm
    for (i=0;i<(nb_phrase-d);i++){
        for(j=0;j<d+1;j++){
            n_gramm[i][j]=mot[j+i];
        }
    }   
    
    printf("%s ",s);
    int z=1;
    char *mot_cible[nb_source];
    mot_cible[0]=strtok(s," ");
    
    while(z!=nb_source && nb_source!=1){
        mot_cible[z]=strtok(NULL," ");
        z++;
    }
    int mot_phrase=nb_source;
    int deb_source=nb_source-d;
    int correlation=0;
    int random_seed=0;

    while(mot_phrase!=l){ //affichage des textes
        int affiche=0;
        int nb_option=0;
        int option[100]={0};
        int last_seed=0;
        for (i=0;i<(nb_phrase-d);i++){
            for(j=0;j<d;j++){
                if(*n_gramm[i][j]==*mot_cible[j+deb_source]){                    
                    correlation++;
                }
            }             
            if (correlation==d){
                option[nb_option]=i;
                last_seed=i+1;
                nb_option++;               
            }
            correlation=0;   
        }
        mot_phrase++;
        random_seed+=7;
        affiche=option[choisir_option(random_seed,nb_option)]; 
                
        if (mot_phrase==l){
            printf("%s",n_gramm[affiche][d]);
        }
        else{
            printf("%s ",n_gramm[affiche][d]);
        }
        for(i=0;i<d;i++){
            mot_cible[i+deb_source]=n_gramm[affiche][i+1];
        }
        
    }
    return 0;
}

Ce programme utilise à quelques détails près la même méthode que moi pour résoudre le problème, cependant il l’implémente différemment certaine fois. Déjà il s’est créé une fonction nombre-mot-chaine permettant de déterminer le nombre de mot que possède une chaine. Il utilise aussi l’opérateur strtok pour découper ces chaines de caractères en se basant sur les espaces. Le reste du programme est donc similaire ca ril va ajouter au fur et à mesure les mots à une chaine de caractère et il appelle la foncction aléatoire fourni pour déterminer quel mot il doit choisir uand il y a plusieurs options.