% Markov text generation
% Eliott ESBELIN
% 15.03.25

-----

<div class="content">

# I- Présentation du problème

## A) Les entrées
<div class="liste">
On nous fourni:

* Une chaine de caractères `t` contenant le texte;
* Un entier `d` représentant le nombre de mots dans la graine;
* Un entier `l` représentant le nombre de mot attendu à la sortie;
* Une chaine de caractère `s` contenant la graine du texte de sortie.
</div>

## 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:

```c

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.

<div class="liste">
Voici les n-grammes de 2 mots que nous avons:

* `one fish` => `is`;
* `fish is` => `good`;
* `is good` => `and`;
* `good and` => `no`;
* `and no` => `fish`;
* `no fish` => `is`;
* `fish is` => `good` ou `bad` car on  avait déjà une possibilité pour une graine égale à `fish is`;
* `is bad` => `and`;
* `bad and` => `that`;
* `and that` => `is`;
* `that is` => `it`;

</div>

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`:

```c

char phrase[]="fish is bad and"

```

<div class="liste">
Méthode:

* Etape 1: `fish is` peut être suivi de `good` ou de `bad`;
* Etape 2: on sélectionne au hazard `bad`;
* Etape 3: `is bad` est forcément suivi de `and`.

</div>

## 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

```c

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

```

### 2.Fonction random_seed

```c

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)

```c

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)

```c
    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++;
        }
    }
    
```
<div class="liste">
On initialise un grand nombre de variable que l'on utilisera plus tard. On initialise notamment les variables:

* `int espace[1000]` qui va permettre de garder en mémoire l'indice du début des différents mots de la chaine de caractère `t`;
* `int longueurEntree=strlen(t)` qui correspond à la longueur total du texte de base;
* `int indiceDebutMot=1` qui correspond au numéro du mot actuel lorsque l'on parcourt la chaine de caractère `t` (autrement dit la case du tableau `espace` que nous devons remplir), la case 0 du tableau espace étant déjà rempli par: `espace[0]=0` nous cherchons désormais l'indice du début du prochain mot.

</div>

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)

```c
    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);
            }
        }
    }
    
```

<div class="liste">
Dans la partie 2 du main, on a notamment initilalisé les variables suivantes:

* `int debut[1000][100]` qui va repertorier les débuts de tout les n-grammes ainsi que le nombre de possibilité de mots qui peut suivre ce n-grammes;
* `int indice[100][10]` qui va repertorier tout les indices des mots qui peuvent suivre un certain n-grammes;
* `char couple[1000][1000]` qui va repertorier tous les n-grammes;
* `int nbEspace` qui permet dans la deuxième boucle `for` ci dessus de compter le nombre d'espaces rencontrées pour s'arréter lorsqu'on a atteint le nombre `d` de mots dans le n-grammes;
* ` soustraireIndice=0` qui va servir dans la double boucle imbriquée ci dessus lorsque qu'un n-grammes est déja présent dans le tableau 2D `couple` pour permettre au prochaine n-grammes nouveau de bine l'ajouter à la suite du suivant sans laisser de case vide entre.

</div>

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)

```c
    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;
    }
    
```

<div class="liste">
Dans cette partie du main, on initialise plusieurs variables et tableaux:

* `char chaineMots[100][10]={0}` qui va contenir les mots de la graine (`s`);
* `int indiceMots[100]={0}` qui va contenir les indices du début des mots de la graine (`s`);
* `int indiceActuel=0` qui correspond au mot que nous sommmes en train de traiter

</div>

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)

```c
    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)

```c
    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

```c

#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.


</div>
<div class="zone-telechargement">
<p>Vous trouverez <a href="../telechargement.html">ici</a> la page de téléchargement du rapport en markdown.</p>
</div>
<div class="footer">
<p>&copy; 2025 ESBELIN Eliott Prep'ISIMA</p>
<div class="footer-images">
```{=html}
    <a href="https://www.uca.fr/"><img src="../Image/UCA.png" alt="Logo UCA"></a>
    <a href="https://www.isima.fr/"><img src="../Image/ISIMA.png" alt="Logo INP/ISIMA"></a>
```
</div>
</div>