Le but de ce TP est de programmer un filtre capable de classer des textes en deux catégories: les textes intéressants et les spams. On utilisera une méthode statistique inspirée des filtres Bayesiens proposés par Paul Graham (actuellement utilisés dans de nombreux filtres anti-spams pour e-mail).
La méthode se base sur une comparaison de la fréquence d'apparition des mots dans trois fichiers: le texte à classer, un corpus de textes non-spam et un corpus de textes spam.
Intuitivement, un mot qui apparaît fréquemment dans le corpus spam mais rarement dans le corpus non-spam constituera un bon critère de sélection. Si un tel mot apparaît également fréquemment dans le texte à classer, cela fait pencher la balance en faveur du spam. Par contre, si le texte à classer contient des mots rencontrés fréquemment dans le corpus non-spam et rarement dans le corpus spam, cela fait pencher la balance dans l'autre sens. La puissance de la méthode provient justement de la prise en compte de critères dans les deux sens.
Voici des exemples de corpus que vous pouvez utiliser. Il s'agit de copies locales d'archives de courriers électroniques (publiques) en anglais:
Les corpus étant fixes et relativement gros, on souhaite les examiner qu'une seule fois. On écrira donc un premier programme creetable qui lit uniquement les deux corpus, les découpe en mots et calcule le nombre d'apparition de chaque mot. creetable stockera le résultat sous forme d'une table dans un fichier table.txt. Le fichier pourra être relu et exploité par le programme de classement. Il sera ainsi possible de classer de nombreux textes sans avoir à appeler creetable à chaque fois.
On propose le format suivant pour le fichier table.txt:
Note: un mot donné ne peut apparaître que dans une seule entrée. Le nombre d'entrées dans la table correspond donc au nombre total de mots des deux corpus sans doublon. Pour obtenir le nombre total de mots dans un corpus, en comptant les doublons, il suffit de faire la somme des nombres sur une colonne de la table.
Indice: l'exécution de creetable devrait produire un fichier ressemblant à celui-ci.
On considérera comme un mot toute suite contiguë de lettres majuscules ou minuscules.
On ne fera pas de statistique sur les chiffres, espaces, ponctuations, etc. Ils serviront uniquement de délimiteurs. Ainsi, Porte-manteaux comptera pour deux mots: Porte et manteaux.
De plus, on distinguera les majuscules des minuscules: Toto, toto et ToTO sont trois mots différents.
Enfin, on ignorera les mots trop longs (par exemple, de plus de 30 lettres).
Un deuxième programme classe prend en entrée le fichier table.txt et un texte à classer.
La première étape consiste à charger entièrement la table table.txt en mémoire dans des variables car on y accédera souvent par la suite.
Ensuite, le programme va attribuer au texte à classer deux scores: la ressemblance du texte à du spam et la ressemblance du texte à du non-spam. Au départ, ces deux scores valent zéro. Chaque mot du texte à classer est alors examiné. Si ce mot n'apparaît pas dans la table, les scores sont inchangés. Si ce mot apparaît dans la table, on ajoute au score spam la fréquence d'apparition du mot dans le corpus spam et au score non-spam la fréquence d'apparition du mot dans le corpus non-spam. Attention: afin d'obtenir un score cohérent, il est important d'additionner des fréquences (nombre d'occurrences d'un mot dans un corpus divisé par le nombre total de mots dans le corpus en comptant les doublons) et non les occurrences.
À la fin, les deux scores sont comparés. Si le score spam est plus grand, le texte est considéré comme spam. Sinon, il est considéré comme du texte intéressant. On peut aussi vérifier que le résultat est significatif en regardant si les deux scores sont suffisamment éloignés.
Nous proposons ici quelques conseils pour programmer creetable et classe. Libre à vous de les suivre ou non.
Il est nécessaire d'allouer une grande quantité de mémoire dans creetable et classe pour stocker tous les mots des deux corpus. Comme on ne sait pas a priori le nombre de mots ni leur taille, on est obligé de se fixer une taille assez grande et de vérifier à chaque ajout dans les tableaux qu'on ne dépasse pas de cette taille. (Ces limitations seront levées dans le cours sur l'allocation dynamique.) Les tailles sont fixées par les constantes symboliques suivantes:
La table est alors représentée en mémoire par l'ensemble suivant de variables globales:
Sur les NB_MOTS entrées prévue dans la table, on indique dans la variable nb_mots le nombre d'entrées effectivement remplies. L'entrée d'indice i (où i varie de 0 et nb_mots-1) se lit de la manière suivante: le mot mots[i] apparaît nombre_ok[i] fois dans le corpus non-spam et nombre_spam[i] fois dans le corpus spam.
Il est alors facile de chercher un mot dans la table (en parcourant les indices de 0 à nb_mots-1), d'ajouter une entrée dans la table (en incrémentant nb_mots), de mettre à jour le nombre d'occurrence d'un mot (en modifiant nombre_ok[i] ou nombre_spam[i] où i est l'indice tel que la chaîne mots[i] soit égale au mot), etc.
De même qu'il est plus facile de résoudre un problème complexe en le décomposant en plusieurs sous-problèmes plus simples, le découpage d'un programme en fonctions élémentaires facilite grandement son écriture. De plus, certaines fonctions prévues pour un programme pourront être réutilisable dans un autre. (Ce sujet sera développé plus en détail dans le cours sur la compilation séparée.)
On propose une première fonction de prototype:
qui cherche mot dans la table en le comparant à mots[i] pour tous les i de 0 à nb_mots-1 (la fonction strcmp sera utile). La fonction retourne l'indice i correspondant. Si le mot n'apparaît pas dans la table, une nouvelle entrée avec occurrences zéro est ajoutée en fin de table: on initialisera mots[nb_mots] (strcpy sera utile ici), nombre_ok[nb_mots] et nombre_spam[nb_mots]; on incrémentera nb_mots et on retournera comme indice la valeur de nb_mots avant incrémentation.
Solution: cherche_mot.c
Une deuxième fonction:
s'assure que mot est dans la table (en l'ajoutant si nécessaire) puis ajoute 1 au nombre d'occurrences de mot dans le tableau nombre_spam ou nombre_ok, selon la valeur de est_du_spam. On commencera par appeler cherche_mot...
Solution: ajoute_mot.c
Les deux fonctions:
vont respectivement sauvegarder la table dans et charger la table depuis un fichier texte de nom fichier. On utilisera pour cela fprintf et fscanf.
Solutions: sauve_table.c et charge_table.c.
La fonction:
lit dans fichier (préalablement ouvert grâce à fopen par l'appelant) un mot et le stocke dans le tableau pointé par mot. (N'oubliez pas d'ajouter un caractère nul final.) On utilisera pour cela getc. On suppose qu'il y a la place pour TAILLE_MOTS caractères dans mot (en comptant le caractère nul à ajouter). Si un mot lu dépasse de cette taille, lit_mot doit l'ignorer et essayer le mot suivant. La fonction doit retourner 1 si un mot a pu être lu et 0 si on est en fin de fichier.
Solution: lit_mot.c
La fonction:
ouvre le fichier nommé nom_de_ficher et ajoute tous ses mots à la table nombre_spam ou nombre_ok, selon la valeur de est_du_spam. Il suffit essentiellement d'appeler lit_mot et ajoute_mot en boucle.
Solution: lit_corpus.c
Grâce à toutes ces fonctions, la fonction principale du programme creetable s'écrit très simplement:
Je vous laisse programmer classe...
La technique présentée ici est une simplification extrême des approches utilisées en pratiques. Pour plus d'informations, vous pouvez consulter l'article A Plan for Spam.
Un autre inconvénient de l'approche proposée dans ce TP est sa lenteur.
Le facteur limitant est le coût des appels à la fonction cherche_mot.
En effet, à chaque appel, il est nécessaire
d'examiner toutes les cases du tableau mots, de l'indice
0 à nb_mots-1.
Il existe des structures de données plus complexes
(comme les tables de hachages) permettant de réduire considérablement
le nombre de cases à examiner.
Comme ces structures de données ne sont pas supportées nativement par le
C et sont complexes à programmer, on n'en dira pas plus.