mehiri/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
Ryad Mehiri 872935c3a2 Filtrer les mots vides sur la première lettre avant de comparer 
est_mot_vide appelait egales sur les 60 mots vides pour chacun des
250 000 mots : 12 millions d'appels. On ne fait la comparaison complète
que si la première lettre correspond (873 000 appels à egales au total).

Temps : 0,20 s → 0,15 s (médiane, bruit de mesure de l'ordre de 0,05 s).
Empreinte inchangée (1d53de903efd2b7c).

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
2026-10-14 14:01:55 +02:00

461 lines
14 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 -g -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 250000
#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++) { /* sans recalculer la longueur à chaque tour */
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;
} Entree;
int est_mot_vide(const char *mot)
{
for (int i = 0; i < NB_MOTS_VIDES; i++) {
/* comparaison complète seulement si la première lettre correspond */
if (MOTS_VIDES[i][0] == mot[0] && egales(mot, MOTS_VIDES[i]))
return 1;
}
return 0;
}
/* Table de hachage à adressage ouvert : chaque case contient l'indice + 1
* d'un mot de la table, ou 0 si elle est vide. Sa taille est une puissance
* de 2 nettement supérieure à MAX_MOTS_UNIQUES pour garder des sondages courts. */
#define TAILLE_HACHAGE 32768
static int index_mots[TAILLE_HACHAGE];
unsigned long empreinte(const char *s);
/* Renvoie la case de index_mots qui contient mot, ou la case vide où l'ajouter. */
unsigned long chercher_mot(const Entree *table, const char *mot)
{
unsigned long h = empreinte(mot) & (TAILLE_HACHAGE - 1);
while (index_mots[h] != 0 && !egales(table[index_mots[h] - 1].mot, mot))
h = (h + 1) & (TAILLE_HACHAGE - 1);
return h;
}
void compter_mot(Entree *table, int *nb_entrees, const char *mot)
{
unsigned long h = chercher_mot(table, mot);
if (index_mots[h] != 0) {
table[index_mots[h] - 1].occurrences++;
} else {
copier(table[*nb_entrees].mot, mot);
table[*nb_entrees].occurrences = 1;
(*nb_entrees)++;
index_mots[h] = *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))
compter_mot(table, nb_entrees, mot);
}
}
}
/* ------------------------------------------------------------------------ */
/* Tri : par nombre d'occurrences décroissant, puis ordre alphabétique */
/* ------------------------------------------------------------------------ */
/* Les mots de la table sont tous distincts : cet ordre est total, donc qsort
* (pourtant non stable) donne exactement le même résultat que le tri à bulles. */
int comparer_entrees(const void *pa, const void *pb)
{
const Entree *a = pa, *b = pb;
if (a->occurrences != b->occurrences)
return b->occurrences - a->occurrences;
return comparer(a->mot, b->mot);
}
void trier_entrees(Entree *table, int n)
{
qsort(table, n, sizeof(Entree), comparer_entrees);
}
/* ------------------------------------------------------------------------ */
/* Statistiques */
/* ------------------------------------------------------------------------ */
double longueur_moyenne(const Entree *table, int n)
{
long total = 0;
for (int i = 0; i < n; i++)
total += longueur(table[i].mot);
return (double)total / n;
}
double ecart_type_longueur(const Entree *table, int n)
{
double moyenne = longueur_moyenne(table, n); /* calculée une seule fois */
double somme = 0.0;
for (int i = 0; i < n; i++) {
double ecart = longueur(table[i].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)
{
char *rapport = malloc((size_t)n * 64 + 256);
char *fin = rapport; /* position du '\0' final : on écrit directement à la suite */
fin += sprintf(fin, "rang;mot;occurrences\n");
for (int i = 0; i < n; i++)
fin += sprintf(fin, "%d;%s;%d\n", i + 1, table[i].mot, table[i].occurrences);
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));
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