Cette semaine, nous vont proposons de coder un correcteur orthographique de différentes manières, détaillées ci-dessous.
Si vous souhaitez plus de renseignements sur les défis, rendez vous sur le topic de recensement des défis, vous y trouverez également les règles principales.
Cet exercice a été écrit par GuilOooo, merci à lui !
Un correcteur orthographique efficace
Mise en situation
Aujourd'hui, nous allons programmer un correcteur orthographique. Il existe de nombreuses techniques pour y parvenir, nous en explorerons quelques unes au cours des trois niveaux que cet exercice propose.
Un correcteur orthographique, pour nous, sera un programme qui diposera d'un dictionnaire (liste de mots) et d'une entrée (chaîne de caractères arbitraire). Le correcteur vérifie que chaque mot de l'entrée est bien dans le dictionnaire. Les mots sont définis comme les séquences de caractères alphabétiques (minuscules ou majuscules), séparés par tout autre caractère (ponctuation, espaces, etc).
Énoncé
Écrivez un programme de correction orthographique. Le dictionnaire sera stocké dans un fichier externe, et l'entrée sera l'entrée standard (dans la console). La liste des mots incorrects rencontrés sera affichée sur la sortie standard (dans la console).
Niveau 1
Pour ce niveau, le dictionnaire sera donné sous forme d'un fichier texte, avec un mot par ligne. Allez, au boulot !
Niveau 2
Essayons un peu plus corsé. Notre correcteur actuel fonctionne correctement (enfin, il devrait ) mais n'est pas très rapide. En outre, le dictionnaire peut prendre une place assez conséquente...
Les filtres de bloom peuvent nous aider à résoudre ce problème. L'idée est la suivante : nous allons trouver un certain nombre de fonctions de hachage, qui, à chaque chaîne de caractère, renvoie un nombre entre 0 et 100. Pour cet exemple, nous coderons quatre fonctions de hachage différentes.
Notre dictionnaire prendra alors la forme d'un tableau de 100 bits, qui sera initialisé à 00000000...000. Pour ajouter le mot « ciboulette », nous le faisons passer par les fonctions de hachage ; imaginons que nous obtenions les résultats 23, 27, 48 et 62. Il suffit alors de mettre les bits numéros 23, 27, 48 et 62 à « 1 » dans notre tableau.
Pour tester si un mot donné est dans le dico, il suffit de le faire passer par les fonctions de hachage, et de vérifier que les bits correspondants sont bien à 1 dans le filtre.
La particularité du filtre de bloom est qu'il peut se tromper ! En effet, 100, 1000 ou même 1 000 000 bits d'information ne permettent pas de stocker un dictionnaire de la langue française complètement. Il arrive donc qu'un mot ait des hashs dont les bits sont tous activés par d'autres mots.
Dans la pratique, ce n'est cependant pas très grave. En effet, en prenant un filtre plus grand et en choisissant correctement le nombre et le code des fonctions de hachage, on peut minimiser la probabilité d'erreur (qu'on appelle un « faux positif »). Le choix de ces paramètres est quelque peu délicat ; nous ferons au plus simple ici.
Votre mission est donc de modifier votre correcteur orthographique pour qu'il utilise un filtre de bloom. N'oubliez pas la possibilité de stocker le filtre dans un fichier. Vous aurez aussi besoin d'un moyen de créer le filtre à partir d'une liste de mots !
Quelle fonction de hachage choisir ?
Il y en a plein ! Une chaîne de caractères est basiquement une suite de nombre. Il suffit d'effectuer une opération sur ces nombres, par exemple la somme, le produit, ou je ne sais quoi encore, puis d'appliquer un modulo. Dans notre exemple, le résultat devra subir un modulo 100. Quelques idées :
somme des codes ascii de chaque caractère ;
produit des codes ascii de chaque caractère ;
concaténation des codes (par exemple, 13 37 65 42 donnera 13037065042) ;
somme des codes ascii élevés au carré ;
puissance successive des codes ascii ;
xor (ou exclusif) des codes ascii....
Ce ne sont pas les possibilités qui manquent ! N'oubliez pas le modulo 100 à la fin.
Niveau 3
Dans ce niveau, nous allons faire quelque chose de légèrement différent.
Imaginons que nous ayons détecté un mot erroné. Nous voulons allons fournir quelques suggestions pour la bonne orthographe de ce mot.
Vous allez donc écrire un programme qui, étant donné un mot, trouve le mot du dictionnaire le plus proche de celui-ci. Bien évidemment, il faudra travailler sur le dictionnaire in extenso, un filtre de bloom ne vous permettra pas de récupérer cette information.
Toute la difficulté est donc de calculer la « distance » entre deux mots. Voici plusieurs idées possibles :
calculer la longueur du plus grand préfixe commun ;
calculer le nombre de lettres qui diffèrent dans le mot ;
calculer le nombre d'opérations (insertion/suppression/substitution) minimal nécessaires pour passer d'un mot à l'autre.
À vous de choisir celle que vous préférez. Il vous faut ensuite trouver le(s) mot(s) du dico dont la distance à votre mot est la plus petite, et les afficher.
Conclusion
Vous pourrez bien entendu réutiliser toutes ces techniques dans d'autre contexte qu'un correcteur orthographique.
C'est de la folie... Malheureusement je ne peut pas participer mais j'ai trouvé un niveau 4: inclure l'hortographe: ex je met je mangent, l'ordinateur me dit que j'ai faut...
Petite remarque: le niveau 1 sera certainement (relativement) lent s'il est codé naïvement, mais vraiment pas si lent s'il est réalisé un peu plus intelligemment (recherche d'un mot en O(log n)).
On peut aussi enregistrer l'index de chaque lettre (comme dans un vrai dico) pour accélérer encore plus la recherche.
Par ailleurs, on peut employer une méthode un peu plus exotique pour ce genre de tache, je pense a un arbre lexicographique.
Bref, il y a vraiment de quoi faire (et notamment pour le niveau 3), j’espère vraiment trouver le temps pour tout ça...
PS : au fait, il me semble bon de signaler que les caracteres accentués risquent malheureusement de compliquer la tache, a moins d'utiliser un dico sans accents...
PPS : voici un lien vers un dictionnaire français sans les accents (tiré d'ici).
Citation : gagaleboss
Malheureusement je ne peut pas participer mais j'ai trouvé un niveau 4: inclure l'hortographe: ex je met je mangent, l'ordinateur me dit que j'ai faut...
Un correcteur grammatical, donc.
En réalité, c'est très clairement au delà du cadre (et du niveau) du présent exo, donc non, c'est une fausse bonne idée (a moins que ce ne soit de l'humour )...
Non, ce n'étais pas de l'humour mais je me sent obligé de dire que quand j'ai écrit "faut" ce n'étais qu'une faute d'inattention. Faux surtout des fautes comme ça dans un sujet qui parle d'un correcteur... J'ai honte
Voici ma contribution pour le niveau 1, j'ai implémenté deux solutions, un dictionnaire par tableau ordonné, et un par arbre lexicographique (celui là est en fait une adaptation d'un vieux code). J'en ai profité pour faire quelques tests.
Résultats :
Au niveau vitesse de recherche dans la structure de données, les deux méthodes sont relativement rapides (quelques dixièmes de seconde pour tester près de 100000 mots), avec tout de même un avantage pour l'arbre lexicographique semble-il.
Au niveau utilisation mémoire, l'arbre lexicographique prends nettement plus de place en mémoire que le tableau (ça s'explique par la taille des pointeurs ajoutés [pour la version tableau, 1 mot = 1 pointeur; pour la version arbre lexicographique, 1 caractère = 1 pointeur], mais je ne m'y attendais pas vraiment, je pensais que ce serait compensé par l'économie des caractères redondants).
Code :
Au fait, je n'ai pas vraiment respecté les consignes de l'énoncé, mais bon ça ne doit pas etre bien difficile à adapter...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
/* selectionne le type de dictionnaire a employer */
//#define USE_LEXICOGRAPHIC_DICT 1
#define USE_ARRAY_DICT 1
#include "dict.h"
#define DICT "dictionnaire_fr.txt"
int main (void)
{
clock_t t;
t = clock();
size_t n = LoadDico (DICT);
printf("\tLoading '%s'... %.3fs - [%u mots]\n",
DICT, (double)(clock()-t)/CLOCKS_PER_SEC, n);
/* TEST DE PERFORMANCES :
recherche tous les mots d'un dictionnaire anglais dans le dictionnaire francais */
t = clock();
size_t founds = 0, not_founds = 0;
FILE* fp = NULL;
if ( (fp = fopen("british-english.txt" ,"r")) != NULL )
{
char english_word[256] = "";
while ( fscanf(fp, "%s", english_word) == 1)
{
int q = SearchWord(english_word);
if (q)
founds++;
else
not_founds++;
}
fclose(fp);
printf("\tSearching english words in french dictionnary in %.3fs - [%u / %u]\n",
(double)(clock()-t)/CLOCKS_PER_SEC, founds, founds+not_founds);
}
/* mini-shell. Entrez un mot à vérifier. Appuyez sur <entrée> pour quitter. */
if (n > 0)
{
char search[256] = "";
do
{
printf("> ");
fgets (search, 256, stdin);
char* occ = strchr(search, '\n');
if (occ != search && occ != NULL)
{
*occ = 0;
printf("'%s' %s\n", search, (SearchWord(search) ? "found" : "not found"));
}
}
while (*search != '\n');
}
t = clock();
FreeDico();
printf("\tFreeing '%s'... %.3fs\n",
DICT, (double)(clock()-t)/CLOCKS_PER_SEC);
return 0;
}
array.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Variables globales - tableau contenant le dico, et taille du tableau */
static char** DictArray;
static size_t DictArraySz;
typedef
struct lst
{
char* word;
struct lst* next;
}
List;
int cmp (const void* a, const void* b)
{
const char* const* s1 = a;
const char* const* s2 = b;
return strcmp(*s1, *s2);
}
List* cons (List* lst, char* word)
{
List* nelem = malloc(sizeof *nelem);
if (nelem == NULL)
return lst;
char* w = malloc(strlen(word) + 1);
if (w == NULL)
{
free(nelem);
return lst;
}
strcpy(w, word);
nelem->word = w;
nelem->next = lst;
return nelem;
}
size_t LoadDicoArray (char* filename)
{
char word[256];
size_t n = 0;
FILE* fp = NULL;
List* wordlist = NULL;
if ( (fp = fopen(filename ,"r")) == NULL )
return 0;
/* recupere les mots dans une liste */
while ( fscanf(fp, "%s", word) == 1)
{
wordlist = cons(wordlist, word);
n++;
}
fclose(fp);
/* passe la liste dans un tableau */
DictArraySz = n; // pourquoi ?
DictArray = malloc(DictArraySz * sizeof *DictArray);
List* iter = wordlist;
size_t i;
for (i=0; iter != NULL; i++)
{
DictArray[i] = iter->word;
iter = iter->next;
}
/* vide la liste */
List* tmp;
while (wordlist->next != NULL)
{
tmp = wordlist;
wordlist = wordlist->next;
free(tmp);
}
/* trie le tableau -
c'est un peu debile ce qui se passe ici :
le dictionnaire est en fait trié à la base,
puis le passage en liste inverse l'ordre,
puis on applique un tri dessus...
j'ai néanmoins préféré garder comme ca dans le cas
ou le tableau n'est pas trié à l'origine */
qsort(DictArray, DictArraySz, sizeof *DictArray, cmp);
return DictArraySz;
}
void FreeDicoArray (void)
{
size_t i;
for (i=0; i < DictArraySz; i++)
free(DictArray[i]);
free(DictArray);
DictArray = NULL, DictArraySz = 0;
}
int SearchWordArray (char* word)
{
return (bsearch(&word, DictArray, DictArraySz, sizeof *DictArray, cmp) != NULL ? 1 : 0);
}
Intéressant comme exercice
Je viens d'essayer le niveau 2 avec 3 fonctions de hashage, mais j'ai bon entrer pratiquement n'importe quoi cela ne me le signale pas comme une erreur. Je ne sais pas si j'ai bien saisit l'algorithme, mais voici mon code:
Il ne fonctionne qu'en C99 car il utilise les fonctions de gestions des caractères larges histoire d'éviter les problèmes avec les caractères accentués.
Salut,
Il ne fonctionne qu'en C99 car il utilise les fonctions de gestions des caractères larges histoire d'éviter les problèmes avec les caractères accentués.
La prise en compte des caractères larges se fait depuis bien avant la norme c99...
Visual studio propose depuis longtemps les wchar_t et wxxxx() et n'est pas c99
** La doc, c'est comme le PQ: ça sert à se démerder tout seul **
Je viens d'essayer le niveau 2 avec 3 fonctions de hashage, mais j'ai bon entrer pratiquement n'importe quoi cela ne me le signale pas comme une erreur. Je ne sais pas si j'ai bien saisit l'algorithme [...]
EDIT: remise de HASH_MAX à 1000.
Ça a résolu ton problème de passer HASH_MAX à 1000 ?
Je viens de faire le niveau 2 et l'ajouter à mon code, voici le résultat de mes expérimentations :
Pour un dico 300000 mots, avec mes fonctions de hachage, pas moyen d'avoir des résultats probants avec un filtre de moins de 1000000 bits. Les résultats sont encore à ce stade assez décevants, et il faut pousser jusqu'à 3-5 millions de bits pour avoir des résultats potables.
Ça parait beaucoup, mais en fait c'est très nettement moins que de stocker tout le dico, car la taille du filtre dépends du nombre de clés, et non pas de leur taille. 4000000 bits font approx. 0.5 Mo., alors que stocker le dictionnaire dans un tableau prendrait au minimum 2.5 Mo. (si on considère que les mots font en moyenne 4 caractères, j'imagine que c'est nettement plus en pratique).
La qualité des fonctions de hachage semble essentielle, et il semble qu'en employer trop nuit. Les deux premières que j'ai employé sont inspirées de fonctions existantes, j'en ai ajouté 2 autres de mon cru et le taux de faux-positifs à nettement augmenté...
Conclusion : je me contente pour l'instant de 2 fonctions de hachage, il est possible que l'emploi d'une ou 2 autres fonctions de hachage de qualité permettrait de réduire encore la taille nécessaire pour le filtre.
La rapidité n'est pas un argument valable ici en faveur d'un filtre de bloom, les fonctions de hash ont un certain cout, et globalement ce n'est pas plus rapide que les autres méthodes.
Enfin, j'ai trouvé sur internet ce lien qui parle justement de l'utilisation d'un filtre de bloom pour un correcteur d'orthographique. Il y a même un code C. Il semble qu'il utilise 11 fonctions de hash (!), mais je n'ai pas encore eu le temps d'approfondir.
[edit :] je viens de tester le code en question, il y avait un petit bug semble il, mais après correction de ce détail les perfs sont excellentes (taux de faux positifs très bas). La taille du filtre pour le même dico que ci dessus (320000 mots) est tout de même de 5000000 bits.
Mon code :
La base de mon code reste la même que ci-dessus, j'ai juste modifié dict.h et ajouté un nouveau fichier .c
Ça a résolu ton problème de passer HASH_MAX à 1000 ?
Non, pas du tout. Avec 100, 1000 ou 100000 j'obtiens franchement du grand n'importe quoi. C'est avec un million que cela commence à devenir potable (enfin plus ou moins). En ce qui me concerne, j'utilise un dictionnaire avec accents de 139719 mots.
Non, pas du tout. Avec 100, 1000 ou 100000 j'obtiens franchement du grand n'importe quoi. C'est avec un million que cela commence à devenir potable (enfin plus ou moins). En ce qui me concerne, j'utilise un dictionnaire avec accents de 139719 mots.
Oui, c'est bien ce qu'il me semblait. Bref, j'ai bien l'impression qu'il faut corriger ce point dans l'énoncé (GuilOooo, tu me lis ?).
J'ai aussi testé ton code, et il me semble qu'il reste pas mal de faux positifs même avec un million. Je pense que c'est dû à une mauvaise qualité des fonctions de hachage (car avec le nombre de mots de ton dico, je crois qu'on devrait avoir une précision assez bonne). Essaye de mettre d'autres fonctions (tu peux en trouver sur cette page) et de faire des tests.
Sinon, voici un article sympa en français sur le filtre de bloom et ses applications.
Taurre > J'ai regardé un peu ton programme. En fait, tes fonctions de hachage mettent tout ton tableau à 1, du coup tout mot entré est bon.
J'ai fait un test en mettant HASH_MAX à 100000000 et en ne gardant que la seconde fonction de hash, ça à l'air de fonctionner.
Il faudrait peut-être revoir les fonctions de hash.
J'ai fait une autre fonction avec la somme des carrés et ça a l'air de fonctionner aussi à peu près.
Par contre, en utilisant une seule ou deux de ces fonctions ça ne fonctionne pas forcément très bien, certains mots erronés sont considérés comme juste.
Après, je pense pas que ça soit dans l'idée du truc de faire un tableau immense.
Après, je pense pas que ça soit dans l'idée du truc de faire un tableau immense.
Comme je l'ai dit ci-dessus, on gagnera presque toujours de la place, car pour N éléments de taille moyenne M bits (M légèrement élevé), on a une complexité mémoire de O(N) pour le filtre de bloom, au lieu de O(N*M) pour une technique stockant réellement toutes les clés. Même si en pratique, on aura besoin par exemple de 10*N bits, ça reste avantageux dans la mesure ou M > 10 bits (c'est le plus souvent le cas, sachant que 10 bits < 2 octets), donc il est justifié de parler ici de O(N) vs. O(N*M).
Si tu lis le lien que j'ai donné ci-dessus, tu verras d’après leurs exemples que l'on peut facilement arriver à un taux intéressant de compression des données (exemple : facteur 15 pour le « Safe Browsing » de google).
Après, la taille du tableau va aussi dépendre du degré de précision souhaité (taux de faux positifs admis), plus on veut de la précision, plus on va devoir allouer de place, mais ça restera généralement avantageux car au delà d'une certaine taille, le gain est de toute façon négligeable (puisque tu ne pourras jamais certifier qu'il n'y ait aucune collision, à mois de disposer d'un tableau de taille infinie), donc on s’arrête à un certain moment.
Ce qui est intéressant aussi, c'est d’étudier le nombre idéal de fonctions de hachage. Il me semble évident que mettre trop de fonctions de hachage va nuire aux performance, et trouver le juste milieux n'est pas évident du point de vue théorique (ça demande certainement des connaissances poussées en math). Il serait intéressant de faire des tests à ce sujet. Ce document semble en parler, mais je n'ai pas eu la force de lire...
J'ai aussi testé ton code, et il me semble qu'il reste pas mal de faux positifs même avec un million. Je pense que c'est dû à une mauvaise qualité des fonctions de hachage (car avec le nombre de mots de ton dico, je crois qu'on devrait avoir une précision assez bonne). Essaye de mettre d'autres fonctions (tu peux en trouver sur cette page) et de faire des tests.
Oui, après test (avec HASH_MAX vallant 10000000) j'obtiens les mêmes résultat que Pouet_forever, la multiplication et la somme des carrés donnent de bien meilleur résultat que la somme ou que le xor qui laisse nettement plus de faux positifs (le xor étant le pire). Comme tu l'as dit il s'agit donc de choisir les bonnes fonctions de hashages et celles qui vont bien ensemble
Je pense que pour avoir une occupation mémoire raisonnable, il faut avoir des bonnes fonctions de hash.
Après, je pense aussi qu'un nombre élevé de fonctions de hash dégradera les performances, mais après pour un dictionnaire je pense que le temps sera assez négligeable.
Par contre, je pense que pour l'exo 3 il faudra vraiment se tourner vers de l'optimisation.
Par contre, je pense que pour l'exo 3 il faudra vraiment se tourner vers de l'optimisation.
Le niveau 3 est très intéressant, et pas trivial du tout, car n'importe quelle fonction de "distance" entre 2 chaines - si rapide soit elle - devra être appliquée sur toutes les chaines du dictionnaire en comparaison du mot inconnu, ce qui ne semble pas réaliste pour une application réelle.
Ouais, je pense qu'il y a des trucs.
J'étais parti sur la distance e levenshtein, mais appliquée à chaque mot, c'est quelque peu long...
Je pense qu'il faut plus optimiser le stockage de données (les mots du dico) histoire de faire une recherche 'similaire'.
Pour le niveau 3, une fois que l'algo qui te check tout les mots dans un temps relativement correct est codé, il doit juste rester à faire une surcouche bien spécifique à la langue en question.
Si c'est le français ça essaye de doubler les consonnes qui se trouvent entre deux voyelles (ex: corecteur, on test tout de suite correcteur et hop ça match).
Bref mais sinon je sais pas si ça déjà dit (j'ai tout lu pourtant) mais moi je stockerai bien la taille de chaque mot du dico.
Ainsi je pourrais checker si le mot fait la bonne taille avant de lancer le strcmp ou leur truc avec les pointeurs sur chaque lettre.
Ouais, je pense qu'il y a des trucs.
J'étais parti sur la distance e levenshtein, mais appliquée à chaque mot, c'est quelque peu long...
Je pense qu'il faut plus optimiser le stockage de données (les mots du dico) histoire de faire une recherche 'similaire'.
Ouais, la distance de Levinstein, c'est peut-être bien en post-traitement pour aider à trier les suggestions par pertinence, mais impensable à utiliser dans un "vrai" spell-checker : trop long. D'ailleurs, ça va être le cas aussi pour toutes les fonctions de distance, je pense.
Citation : Mr21
Pour le niveau 3, une fois que l'algo qui te check tout les mots dans un temps relativement correct est codé, il doit juste rester à faire une surcouche bien spécifique à la langue en question.
Si c'est le français ça essaye de doubler les consonnes qui se trouvent entre deux voyelles (ex: corecteur, on test tout de suite correcteur et hop ça match).
Ben oui et non, la tu entre effectivement dans la catégorie des algos spécifiques à la langue, mais justement :
- Ce n'est pas compatible avec tous les algos, par exemple un bsearch est impensable avec cette methode.
- Tu es loin de pouvoir proposer des solutions valables dans tous les cas (faute de frappe, par exemple).
Mais effectivement, ce type d'approche est indispensable en complément de toute autre, et on dit c'est l'usage d'algorithmes "intelligents" de ce type qui va faire la différence entre 2 correcteurs orthographiques.
Bref mais sinon je sais pas si ça déjà dit (j'ai tout lu pourtant) mais moi je stockerai bien la taille de chaque mot du dico.
Ainsi je pourrais checker si le mot fait la bonne taille avant de lancer le strcmp ou leur truc avec les pointeurs sur chaque lettre.
C'est effectivement une possibilité, mais ça apporte un surcout de complexité en termes de codage, pour un gain d'efficacité pas tellement important voire nul dans certains cas (enfin, il me semble, je n'ai pas fait de tests). Je serais curieux de voir des benchs sur la question. Au passage, ce n'est pas compatible avec l'arbre lexicographique.
Quelques rectifications sur ce que je t'ai répondu plus haut :
Citation : yoch
Citation : Pouet_forever
Ouais, je pense qu'il y a des trucs.
J'étais parti sur la distance e levenshtein, mais appliquée à chaque mot, c'est quelque peu long...
Je pense qu'il faut plus optimiser le stockage de données (les mots du dico) histoire de faire une recherche 'similaire'.
Ouais, la distance de Levinstein, c'est peut-être bien en post-traitement pour aider à trier les suggestions par pertinence, mais impensable à utiliser dans un "vrai" spell-checker : trop long. D'ailleurs, ça va être le cas aussi pour toutes les fonctions de distance, je pense.
J'ai fait des recherches, et il semble que la complexité temporelle peut être réduite significativement, avec plusieurs possibilités :
Si on cherche une distance bornée (genre if(d>borne)returninf;), on peut optimiser la fonction de recherche.
Utilisation d'un arbre particulier (BK-Tree) permettant d'optimiser les recherches dans un espace métrique (je sais, c'est du chinois , je vous recommande cet excellent article pour vous faire une petite idée sur le principe). L'amélioration représente approx. un facteur 5 sur la vitesse, mais avec une nette perte au niveau complexité mémoire et temps de construction de la structure.
Il existe des automates permettant d'optimiser le temps de recherche de distance de Levenstein sur un grand nombre de données. Je n'ai pas approfondi plus ce point.
Je ne sais pas si ça permettrait d'avoir des performances valable ou non pour un "vrai" logiciel.
A noter qu'en fait la proposition de Mr21 ci-dessus est l'inverse de ton approche : au lieu de calculer la distance entre chaque mot du dictionnaire et le mot inconnu, on essaye de produire toutes les variantes de ce mot à une distance convenable, puis on recherche tous ces mots dans le dico. Il serait intéressant d'effectuer un bench comparant ces deux approches.
En revanche, il faut prendre en compte que la distance de Levenstein (ou même la distance de Damereau-Levinstein, plus adaptée à un spell-checker) n'est pas suffisante pour trier les suggestions par pertinence, et c'est là que l'on doit ajouter des techniques plus intelligentes comme la distance phonétique, la probabilité d'apparition d'un mot dans un texte, la disposition du clavier (pour les fautes de frappe), etc.
Ça marche bien sauf pour les contractions types "c'est" ou "j'ai".
Il faudrait rajouter "c'" "j'" "m'" "l'" "n'" au dico, et couper une chaine en 2 chaines lorsqu'il y a une apostrophe ...
J'ai 10 minutes là, je m'y mets.
Idée débile, il y a bien plus simple, je l'ai ajouté au code, ça marche.
Pour la fonction de hashage, je ne me suis pas fait chier, j'ai pris sha1 ...
J'aurais pus prendre md5 mais bon ^^" Fallait bien faire un choix.
Le principe étant que si on veut mieux faire, il faudrait réduire un peu la taille de la fonction de hashage ... Vous la remplacez par n'importe quelle fonction de hashage potable, je l'ai prise juste pour en avoir une correcte qui ne bug pas, je suis bien conscient que pour un exo de ce type, ce n'est certainement pas la fonction à prendre ...
🍊 - Étudiant - Codeur en C | Zeste de Savoir apprenez avec une communauté | Articles- ♡ Copying is an act of love.
C'est un vieux sujet. As-tu vérifié dans les profils si les gens se connectent encore?
Le Tout est souvent plus grand que la somme de ses parties.
[FAIT][Defis] #7 : Un correcteur orthographique efficace
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
🍊 - Étudiant - Codeur en C | Zeste de Savoir apprenez avec une communauté | Articles - ♡ Copying is an act of love.
Le Tout est souvent plus grand que la somme de ses parties.