couchot/2026_TD1_DEV51_Qualite_Algo
1
0
Fork 0
forked from menault/2026_TD1_DEV51_Qualite_Algo
Code Pull Requests Activity
Files
main
2026_TD1_DEV51_Qualite_Algo/analyseur.c
T
Nathan Couchot 7ab243f1d6 opti 2
2026-10-07 12:05:12 +02:00

534 lines
16 KiB
C
Raw Permalink Blame History

/*
* R5.A.04 - Qualité Algorithmique
* TD Profiling : analyseur de fréquence de mots
*
* Le programme génère un texte pseudo-aléatoire (toujours le même, grâce
* à une graine fixe), puis :
* 1. découpe le texte en lignes et le normalise (minuscules, ponctuation)
* 2. compte les occurrences de chaque mot (hors mots vides)
* 3. trie les mots par fréquence
* 4. calcule des statistiques sur la longueur des mots
* 5. analyse les bigrammes de lettres
* 6. génère un rapport complet dans rapport.txt
*
* L'empreinte affichée à la fin doit rester IDENTIQUE après optimisation :
* elle prouve que le résultat du programme n'a pas changé.
*
* Compilation : gcc -O0 -pg analyseur.c -o analyseur
* Exécution : ./analyseur
* Profil : gprof ./analyseur gmon.out > profil.txt
*/
#include <stdio.h>
#include <stdlib.h>
#define NB_MOTS_TEXTE 2500000
#define NB_MOTS_VOCAB 7000
#define TAILLE_MOT 32
#define MAX_MOTS_UNIQUES 20000
#define GRAINE 20261006UL
/* ------------------------------------------------------------------------ */
/* Générateur pseudo-aléatoire (identique sur toutes les machines) */
/* ------------------------------------------------------------------------ */
static unsigned long etat_alea = GRAINE;
unsigned long alea(void)
{
etat_alea = etat_alea * 6364136223846793005UL + 1442695040888963407UL;
return etat_alea >> 33;
}
/* ------------------------------------------------------------------------ */
/* Fonctions utilitaires sur les chaînes */
/* ------------------------------------------------------------------------ */
int longueur(const char *s)
{
int n = 0;
while (s[n] != '\0')
n++;
return n;
}
void copier(char *dest, const char *src)
{
int i = 0;
while (src[i] != '\0') {
dest[i] = src[i];
i++;
}
dest[i] = '\0';
}
int egales(const char *a, const char *b)
{
int i = 0;
while (a[i] != '\0' && b[i] != '\0') {
if (a[i] != b[i])
return 0;
i++;
}
return a[i] == b[i];
}
int comparer(const char *a, const char *b)
{
int i = 0;
while (a[i] != '\0' && a[i] == b[i])
i++;
return (unsigned char)a[i] - (unsigned char)b[i];
}
void ajouter(char *dest, const char *src)
{
copier(dest + longueur(dest), src);
}
char en_minuscule(char c)
{
if (c >= 'A' && c <= 'Z')
return c - 'A' + 'a';
return c;
}
int est_lettre(char c)
{
return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}
/* ------------------------------------------------------------------------ */
/* Génération du texte */
/* ------------------------------------------------------------------------ */
static const char *MOTS_VIDES[] = {
"le", "la", "les", "un", "une", "des", "du", "de", "et", "ou",
"mais", "donc", "or", "ni", "car", "que", "qui", "quoi", "dont", "ou",
"a", "au", "aux", "en", "dans", "par", "pour", "sur", "sous", "avec",
"sans", "chez", "vers", "entre", "il", "elle", "ils", "elles", "on", "nous",
"vous", "je", "tu", "se", "ce", "cet", "cette", "ces", "son", "sa",
"ses", "leur", "leurs", "mon", "ma", "mes", "ne", "pas", "plus", "est"
};
#define NB_MOTS_VIDES ((int)(sizeof(MOTS_VIDES) / sizeof(MOTS_VIDES[0])))
static const char *SYLLABES[] = {
"ba", "be", "bi", "bo", "ca", "co", "da", "de", "di", "fa", "fi", "ga",
"go", "la", "le", "li", "lo", "ma", "me", "mi", "mo", "na", "ne", "no",
"pa", "pe", "pi", "po", "ra", "re", "ri", "ro", "sa", "se", "si", "so",
"ta", "te", "ti", "to", "va", "ve", "vi", "vo", "tion", "ment", "eur", "ique"
};
#define NB_SYLLABES ((int)(sizeof(SYLLABES) / sizeof(SYLLABES[0])))
char **generer_vocabulaire(void)
{
char **vocab = malloc(NB_MOTS_VOCAB * sizeof(char *));
for (int i = 0; i < NB_MOTS_VOCAB; i++) {
vocab[i] = malloc(TAILLE_MOT);
vocab[i][0] = '\0';
int nb_syllabes = 2 + alea() % 3;
for (int j = 0; j < nb_syllabes; j++)
ajouter(vocab[i], SYLLABES[alea() % NB_SYLLABES]);
}
return vocab;
}
char *generer_texte(char **vocab, int nb_mots)
{
char *texte = malloc((size_t)nb_mots * (TAILLE_MOT + 2) + 1);
long pos = 0;
int debut_phrase = 1;
int mots_restants_phrase = 8 + alea() % 8;
for (int i = 0; i < nb_mots; i++) {
const char *mot;
if (alea() % 100 < 40) {
mot = MOTS_VIDES[alea() % NB_MOTS_VIDES];
} else {
/* distribution biaisée : certains mots sont bien plus fréquents */
unsigned long r1 = alea() % NB_MOTS_VOCAB;
unsigned long r2 = alea() % NB_MOTS_VOCAB;
mot = vocab[(r1 * r2) / NB_MOTS_VOCAB];
}
for (int j = 0; mot[j] != '\0'; j++) {
char c = mot[j];
if (debut_phrase && j == 0)
c = c - 'a' + 'A';
texte[pos++] = c;
}
debut_phrase = 0;
mots_restants_phrase--;
if (mots_restants_phrase == 0) {
texte[pos++] = '.';
texte[pos++] = '\n';
debut_phrase = 1;
mots_restants_phrase = 8 + alea() % 8;
} else if (alea() % 10 == 0) {
texte[pos++] = ',';
texte[pos++] = ' ';
} else {
texte[pos++] = ' ';
}
}
texte[pos++] = '\n';
texte[pos] = '\0';
return texte;
}
/* ------------------------------------------------------------------------ */
/* Découpage et normalisation */
/* ------------------------------------------------------------------------ */
char **decouper_lignes(const char *texte, int *nb_lignes)
{
int capacite = 1024;
char **lignes = malloc(capacite * sizeof(char *));
int n = 0;
int debut = 0;
for (int i = 0; texte[i] != '\0'; i++) {
if (texte[i] == '\n') {
int taille = i - debut;
if (n == capacite) {
capacite *= 2;
lignes = realloc(lignes, capacite * sizeof(char *));
}
lignes[n] = malloc(taille + 1);
for (int j = 0; j < taille; j++)
lignes[n][j] = texte[debut + j];
lignes[n][taille] = '\0';
n++;
debut = i + 1;
}
}
*nb_lignes = n;
return lignes;
}
void normaliser_ligne(char *ligne)
{
for (int i = 0; ligne[i] != '\0'; i++) {
if (est_lettre(ligne[i]))
ligne[i] = en_minuscule(ligne[i]);
else
ligne[i] = ' ';
}
}
/* ------------------------------------------------------------------------ */
/* Comptage des mots */
/* ------------------------------------------------------------------------ */
typedef struct {
char mot[TAILLE_MOT];
int occurrences;
int longueur_mot;
} Entree;
/* Groupes par longueur et première lettre ; indices + 1, zéro = fin. */
int est_mot_vide(const char *mot, int taille)
{
static int groupes[TAILLE_MOT][26];
static int suivants[NB_MOTS_VIDES];
static int initialise = 0;
if (!initialise) {
for (int i = 0; i < NB_MOTS_VIDES; i++) {
int n = longueur(MOTS_VIDES[i]);
int lettre = MOTS_VIDES[i][0] - 'a';
if (n > 0 && n < TAILLE_MOT && lettre >= 0 && lettre < 26) {
suivants[i] = groupes[n][lettre];
groupes[n][lettre] = i + 1;
}
}
initialise = 1;
}
if (taille <= 0 || taille >= TAILLE_MOT || mot[0] < 'a' || mot[0] > 'z')
return 0;
for (int indice = groupes[taille][mot[0] - 'a']; indice != 0;
indice = suivants[indice - 1]) {
if (egales(mot, MOTS_VIDES[indice - 1]))
return 1;
}
return 0;
}
/* Indices + 1 : zéro représente une case libre. Charge < 31 %. */
#define CAPACITE_INDEX 65536
static int index_mots[CAPACITE_INDEX];
unsigned long hacher_mot(const char *mot)
{
unsigned long h = 5381;
for (int i = 0; mot[i] != '\0'; i++)
h = h * 33 + (unsigned char)mot[i];
return h;
}
int chercher_mot(Entree *table, const char *mot, unsigned long *case_libre)
{
unsigned long position = hacher_mot(mot) % CAPACITE_INDEX;
while (index_mots[position] != 0) {
int indice = index_mots[position] - 1;
if (egales(table[indice].mot, mot))
return indice;
position = (position + 1) % CAPACITE_INDEX;
}
*case_libre = position;
return -1;
}
void compter_mot(Entree *table, int *nb_entrees, const char *mot, int longueur_mot)
{
/* Réinitialisation possible pour un nouveau comptage. */
if (*nb_entrees == 0)
for (int i = 0; i < CAPACITE_INDEX; i++)
index_mots[i] = 0;
unsigned long position;
int indice = chercher_mot(table, mot, &position);
if (indice >= 0) {
table[indice].occurrences++;
} else {
if (*nb_entrees == MAX_MOTS_UNIQUES) {
fputs("Trop de mots distincts\n", stderr);
exit(EXIT_FAILURE);
}
copier(table[*nb_entrees].mot, mot);
table[*nb_entrees].occurrences = 1;
table[*nb_entrees].longueur_mot = longueur_mot;
index_mots[position] = *nb_entrees + 1;
(*nb_entrees)++;
}
}
void compter_mots_ligne(Entree *table, int *nb_entrees, const char *ligne,
long *nb_mots_total)
{
char mot[TAILLE_MOT];
int i = 0;
while (ligne[i] != '\0') {
while (ligne[i] == ' ')
i++;
int k = 0;
while (ligne[i] != '\0' && ligne[i] != ' ') {
if (k < TAILLE_MOT - 1)
mot[k++] = ligne[i];
i++;
}
mot[k] = '\0';
if (k > 0) {
(*nb_mots_total)++;
if (!est_mot_vide(mot, k))
compter_mot(table, nb_entrees, mot, k);
}
}
}
/* ------------------------------------------------------------------------ */
/* Tri : par nombre d'occurrences décroissant, puis ordre alphabétique */
/* ------------------------------------------------------------------------ */
int doit_echanger(const Entree *a, const Entree *b)
{
if (a->occurrences != b->occurrences)
return a->occurrences < b->occurrences;
return comparer(a->mot, b->mot) > 0;
}
/* Tri fusion : même ordre total, O(n log n), mémoire O(n). */
void fusionner_entrees(Entree *table, Entree *tampon, int debut, int fin)
{
if (fin - debut < 2)
return;
int milieu = debut + (fin - debut) / 2;
fusionner_entrees(table, tampon, debut, milieu);
fusionner_entrees(table, tampon, milieu, fin);
int gauche = debut, droite = milieu;
for (int k = debut; k < fin; k++) {
if (gauche < milieu && (droite == fin ||
!doit_echanger(&table[gauche], &table[droite])))
tampon[k] = table[gauche++];
else
tampon[k] = table[droite++];
}
for (int k = debut; k < fin; k++)
table[k] = tampon[k];
}
void trier_entrees(Entree *table, int n)
{
if (n < 2)
return;
Entree *tampon = malloc((size_t)n * sizeof(*tampon));
if (tampon == NULL) {
perror("malloc tri");
exit(EXIT_FAILURE);
}
fusionner_entrees(table, tampon, 0, n);
free(tampon);
}
/* ------------------------------------------------------------------------ */
/* Statistiques */
/* ------------------------------------------------------------------------ */
double longueur_moyenne(const Entree *table, int n)
{
long total = 0;
for (int i = 0; i < n; i++)
total += table[i].longueur_mot;
return (double)total / n;
}
double ecart_type_longueur(const Entree *table, int n, double moyenne)
{
double somme = 0.0;
for (int i = 0; i < n; i++) {
double ecart = table[i].longueur_mot - moyenne;
somme += ecart * ecart;
}
return somme / n; /* variance ; la racine est prise dans main */
}
/* Recherche du bigramme de lettres le plus fréquent, avec en bonus la
* troisième lettre qui le suit le plus souvent. */
void analyser_bigrammes(char **lignes, int nb_lignes,
char *meilleur, int *occ_meilleur)
{
static int trigrammes[26][26][26];
for (int l = 0; l < nb_lignes; l++) {
const char *s = lignes[l];
for (int i = 0; s[i] != '\0' && s[i + 1] != '\0' && s[i + 2] != '\0'; i++) {
if (est_lettre(s[i]) && est_lettre(s[i + 1]) && est_lettre(s[i + 2]))
trigrammes[s[i] - 'a'][s[i + 1] - 'a'][s[i + 2] - 'a']++;
}
}
*occ_meilleur = -1;
for (int a = 0; a < 26; a++) {
for (int b = 0; b < 26; b++) {
int total = 0;
for (int c = 0; c < 26; c++)
total += trigrammes[a][b][c];
if (total > *occ_meilleur) {
*occ_meilleur = total;
int meilleur_c = 0;
for (int c = 1; c < 26; c++)
if (trigrammes[a][b][c] > trigrammes[a][b][meilleur_c])
meilleur_c = c;
meilleur[0] = 'a' + a;
meilleur[1] = 'a' + b;
meilleur[2] = 'a' + meilleur_c;
meilleur[3] = '\0';
}
}
}
}
/* ------------------------------------------------------------------------ */
/* Rapport */
/* ------------------------------------------------------------------------ */
char *construire_rapport(const Entree *table, int n)
{
size_t capacite = (size_t)n * 64 + 256;
char *rapport = malloc(capacite);
if (rapport == NULL) {
perror("malloc rapport");
exit(EXIT_FAILURE);
}
size_t position = (size_t)snprintf(rapport, capacite, "rang;mot;occurrences\n");
for (int i = 0; i < n; i++) {
int taille = snprintf(rapport + position, capacite - position,
"%d;%s;%d\n", i + 1, table[i].mot, table[i].occurrences);
if (taille < 0 || (size_t)taille >= capacite - position) {
fputs("Rapport trop long\n", stderr);
free(rapport);
exit(EXIT_FAILURE);
}
position += (size_t)taille;
}
return rapport;
}
unsigned long empreinte(const char *s)
{
unsigned long h = 1469598103934665603UL;
for (int i = 0; s[i] != '\0'; i++) {
h ^= (unsigned char)s[i];
h *= 1099511628211UL;
}
return h;
}
/* ------------------------------------------------------------------------ */
double racine(double x)
{
double r = x > 1.0 ? x : 1.0;
for (int i = 0; i < 50; i++)
r = 0.5 * (r + x / r);
return r;
}
int main(void)
{
char **vocab = generer_vocabulaire();
char *texte = generer_texte(vocab, NB_MOTS_TEXTE);
int nb_lignes;
char **lignes = decouper_lignes(texte, &nb_lignes);
for (int i = 0; i < nb_lignes; i++)
normaliser_ligne(lignes[i]);
Entree *table = malloc(MAX_MOTS_UNIQUES * sizeof(Entree));
int nb_entrees = 0;
long nb_mots_total = 0;
for (int i = 0; i < nb_lignes; i++)
compter_mots_ligne(table, &nb_entrees, lignes[i], &nb_mots_total);
trier_entrees(table, nb_entrees);
double moyenne = longueur_moyenne(table, nb_entrees);
double ecart_type = racine(ecart_type_longueur(table, nb_entrees, moyenne));
char trigramme[4];
int occ_trigramme;
analyser_bigrammes(lignes, nb_lignes, trigramme, &occ_trigramme);
char *rapport = construire_rapport(table, nb_entrees);
FILE *f = fopen("rapport.txt", "w");
if (f != NULL) {
fputs(rapport, f);
fclose(f);
}
printf("Lignes analysées : %d\n", nb_lignes);
printf("Mots au total : %ld\n", nb_mots_total);
printf("Mots distincts : %d\n", nb_entrees);
printf("Longueur moyenne : %.3f (écart-type %.3f)\n", moyenne, ecart_type);
printf("Bigramme le + courant : \"%c%c\" (%d fois, souvent suivi de '%c')\n",
trigramme[0], trigramme[1], occ_trigramme, trigramme[2]);
printf("\nTop 10 :\n");
for (int i = 0; i < 10 && i < nb_entrees; i++)
printf(" %2d. %-16s %d\n", i + 1, table[i].mot, table[i].occurrences);
printf("\nEmpreinte du rapport : %016lx\n", empreinte(rapport));
free(rapport);
free(table);
for (int i = 0; i < nb_lignes; i++)
free(lignes[i]);
free(lignes);
free(texte);
for (int i = 0; i < NB_MOTS_VOCAB; i++)
free(vocab[i]);
free(vocab);
return 0;
}
View Git Blame Copy Permalink