Partage

[FAIT][Defis] #7 : Un correcteur orthographique efficace

21 novembre 2011 à 20:37:02

Bonsoir,

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.

Amusez-vous bien ! :)
GuilOooo


Participants



Participants Code
yoch Niveau 1
Taurre Niveaux 2 et 3
21 novembre 2011 à 22:22:22

C'est de la folie... :o 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...
21 novembre 2011 à 22:23:30

Bonsoir,

Cool cet exo ! (tous niveaux confondus) :)

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 ;) )...
21 novembre 2011 à 22:35:41

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. :p Faux :D surtout des fautes comme ça dans un sujet qui parle d'un correcteur... J'ai honte :p
22 novembre 2011 à 13:18:43

Bonjour,

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



dict.h
size_t LoadDicoLex (char* filename);
void FreeDicoLex (void);
int SearchWordLex (char* word);

size_t LoadDicoArray (char* filename);
void FreeDicoArray (void);
int SearchWordArray (char* word);


#if USE_LEXICOGRAPHIC_DICT

    #define LoadDico(f)     LoadDicoLex(f)
    #define FreeDico()      FreeDicoLex()
    #define SearchWord(w)   SearchWordLex(w)

#elif USE_ARRAY_DICT

    #define LoadDico(f)     LoadDicoArray(f)
    #define FreeDico()      FreeDicoArray()
    #define SearchWord(w)   SearchWordArray(w)

#endif


main.c
#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);
}


lexicographic.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef
struct node
{
    char c;
    struct node *filsDroit;
    struct node *filsBas;
}
Noeud;

/* Variable globale - arbre lexocographique */
static Noeud* LexicographicTree = NULL;


Noeud *InitTree (void)
{
    Noeud *tree = malloc(sizeof *tree);
    if (tree != NULL)
    {
        tree->c = 0;
        tree->filsDroit = NULL;
        tree->filsBas = NULL;
    }
    return tree;
}

void DeleteTree (Noeud *node)
{
    if (node->filsDroit != NULL)
        DeleteTree(node->filsDroit);
    if (node->filsBas != NULL)
        DeleteTree(node->filsBas);
    free(node), node = NULL;
}

void AjouteADroite (Noeud **node, char c)
{
    Noeud *new_node = malloc (sizeof *new_node);
    if (new_node != NULL)
    {
        new_node->c = c;
        new_node->filsDroit = NULL;
        new_node->filsBas = NULL;
        (*node)->filsDroit = new_node;
        *node = new_node;
    }
}

void AjouteEnBas (Noeud **node, char c)
{
    Noeud* new_node = malloc (sizeof *new_node);
    if (new_node != NULL)
    {
        new_node->c = c;
        new_node->filsDroit = NULL;
        new_node->filsBas = NULL;
        (*node)->filsBas = new_node;
        *node = new_node;
    }
}

void AddWord (Noeud* node, char* word)
{
    while (1)
    {
        while (*word != node->c && node->filsBas != NULL)
        {
            node = node->filsBas;
        }
        if (*word != node->c)
            AjouteEnBas (&node, *word);

        if (*word++)
        {
            if (node->filsDroit == NULL)
                AjouteADroite (&node, *word);
            else
                node = node->filsDroit;
         }
         else
            break;
    }
}

int SearchWordLex (char* word)
{
    Noeud* node = LexicographicTree;
    while(1)
    {
        while (*word != node->c && node->filsBas != NULL)
        {
            node = node->filsBas;
        }

        if (*word == node->c)
            node = node->filsDroit;
        else
            return 0;

        if (!*word++)
            break;
    }
    return 1;
}

size_t LoadDicoLex (char* filename)
{
    char word[256];
    size_t i = 0;
    FILE* fp = NULL;

    if ( (LexicographicTree = InitTree()) == NULL )
        return 0;

    if ( (fp = fopen(filename ,"r")) != NULL )
    {
        while ( fscanf(fp, "%s", word) == 1)
        {
            AddWord (LexicographicTree, word);
            i++;
        }

        fclose(fp);
    }
    return i;
}

void FreeDicoLex (void)
{
    DeleteTree (LexicographicTree);
    LexicographicTree = NULL;
}


22 novembre 2011 à 15:30:10

Salut,

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:


#include <locale.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <wchar.h>

#define HASH_MAX 1000
#define WORD_MAX 64

static char a_words[HASH_MAX];

static void
hash(wchar_t const *s, unsigned long *tab)
{
	unsigned long tmp;
	wchar_t const *t;

	for (tmp = 0u, t = s; *t != L'\0'; t++)
		tmp += *t;
	tab[0] = tmp % HASH_MAX;

	for (tmp = 1u, t = s; *t != L'\0'; t++)
		tmp *= *t;
	tab[1] = tmp % HASH_MAX;

	for (tmp = 0u, t = s; *t != L'\0'; t++)
		tmp ^= *t;
	tab[2] = tmp % HASH_MAX;
}


static void
delete_newline(wchar_t *s)
{
	if ((s = wcschr(s, L'\n')) != NULL)
		*s = L'\0';
}


static int
read_dictionnary(char const *file)
{
	static wchar_t word[WORD_MAX];
	FILE *fp;

	if ((fp = fopen(file, "r")) == NULL)
		return 0;

	while (fgetws(word, WORD_MAX, fp) != NULL) {
		unsigned long tab[3];

		delete_newline(word);
		hash(word, tab);
		a_words[tab[0]] = 1;
		a_words[tab[1]] = 1;
		a_words[tab[2]] = 1;
	}

	fclose(fp);
	return 1;
}


int
main(void)
{
	static wchar_t word[WORD_MAX];

	setlocale(LC_ALL, "");
	if (!read_dictionnary("dico.txt"))
		return EXIT_FAILURE;

	while (wscanf(L"%63ls", word) == 1) {
		unsigned long tab[3];
		wint_t c;

		hash(word, tab);
		if (!a_words[tab[0]] || !a_words[tab[1]] || !a_words[tab[2]])
			wprintf(L"mot incorrect: %ls\n", word);

		while ((c = getwchar()) != L'\n' && c != WEOF)
			;
	}

	return EXIT_SUCCESS;
}



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.

EDIT: remise de HASH_MAX à 1000.
22 novembre 2011 à 17:14:40

Citation : Taurre

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 **
22 novembre 2011 à 18:01:34

Citation : breizhbugs


La prise en compte des caractères larges se fait depuis bien avant la norme c99...



Oui, mais le support n'est parfois que partiel (comme sur MinGW), je préfère donc conseiller un compilateur conforme au C99.

Citation : breizhbugs


Visual studio propose depuis longtemps les wchar_t et wxxxx() et n'est pas c99



Je ne savais pas que VC disposait du support pour les caractères larges, merci pour l'information ;)
22 novembre 2011 à 18:06:00

Même GCC n'est pas conforme au C99. :-°
22 novembre 2011 à 18:19:49

Citation : Pouet_forever


Même GCC n'est pas conforme au C99. :-°



Oui, pardon, je me suis mal exprimé :honte:
Je voulais dire un compilateur supportant les fonctions de gestions des caractères larges du C99.
22 novembre 2011 à 20:41:58

quand tu cherche la doc sur une fonction standard (msdn + nomfonction sur google), il y a son équivalent unicode: par exemple printf/wprintf
http://msdn.microsoft.com/en-us/librar [...] v=vs.71).aspx
** La doc, c'est comme le PQ: ça sert à se démerder tout seul **
23 novembre 2011 à 13:52:17

Citation : Taurre

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


dict.h
size_t LoadDicoLex (char* filename);
void FreeDicoLex (void);
int SearchWordLex (char* word);

size_t LoadDicoArray (char* filename);
void FreeDicoArray (void);
int SearchWordArray (char* word);

size_t LoadDicoBloom (char* filename);
void FreeDicoBloom (void);
int SearchWordBloom (char* word);

#if USE_LEXICOGRAPHIC_DICT

    #define LoadDico(f)     LoadDicoLex(f)
    #define FreeDico()      FreeDicoLex()
    #define SearchWord(w)   SearchWordLex(w)

#elif USE_ARRAY_DICT

    #define LoadDico(f)     LoadDicoArray(f)
    #define FreeDico()      FreeDicoArray()
    #define SearchWord(w)   SearchWordArray(w)

#elif USE_BLOOMFILTER_DICT

    #define LoadDico(f)     LoadDicoBloom(f)
    #define FreeDico()      FreeDicoBloom()
    #define SearchWord(w)   SearchWordBloom(w)

#endif


bloom_filter.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>


#define FILTER_SZ  3000000

/* Variable globale - tableau pour le filtre */
void* BloomFilter = NULL;


void set (void* ptr, size_t p)
{
    if (p >= FILTER_SZ) return;
    char* array = ptr;
    array[p / CHAR_BIT] |= 1<<(p % CHAR_BIT);
}

int test (void* ptr, size_t p)
{
    if (p >= FILTER_SZ) return 0;
    char* array = ptr;
    return array[p / CHAR_BIT] & (1<<(p % CHAR_BIT));
}

unsigned hash1(const char* word)
{
    unsigned h = 0;
    char c;
    while ( (c = *word++) )
        h = 31 * h + c;
    return h % FILTER_SZ;
}

unsigned hash2(const char* word)
{
    unsigned h = 0;
    char c;
    while ( (c = *word++) )
        h = (1000003 * h) ^ c;
    return h % FILTER_SZ;
}

unsigned (*tabHashs[])(const char*) = {  hash1, hash2  };

size_t LoadDicoBloom (char* filename)
{
    char word[256];
    size_t n = 0;
    FILE* fp = NULL;

    if ( (fp = fopen(filename ,"r")) == NULL )
        return 0;

    if ( (BloomFilter = calloc(FILTER_SZ/CHAR_BIT + 1, sizeof *BloomFilter)) != NULL )
    {
        while ( fscanf(fp, "%s", word) == 1)
        {
            size_t i;
            unsigned hash;
            for (i=0; i<2; i++)
            {
                hash = tabHashs[i](word);
                set(BloomFilter, hash);
            }
            n++;
        }
    }

    fclose(fp);

    return n;
}

void FreeDicoBloom (void)
{
    free(BloomFilter);
    BloomFilter = NULL;
}

int SearchWordBloom (char* word)
{
    size_t i;
    unsigned hash;
    for (i=0; i<2; i++)
    {
        hash = tabHashs[i](word);
        if ( !test(BloomFilter, hash) )
            return 0;
    }
    return 1;
}



23 novembre 2011 à 15:06:03

Citation : yoch


Ç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.
23 novembre 2011 à 17:58:33

Citation : Taurre

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.
23 novembre 2011 à 19:35:24

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. :-°
23 novembre 2011 à 20:21:14

Citation : Pouet_forever

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... :-°
23 novembre 2011 à 20:39:08

Citation : yoch


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 :)
23 novembre 2011 à 22:04:09

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. ^^
23 novembre 2011 à 22:56:36

Citation : Pouet_forever

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.

Il faut donc trouver une astuce, apparemment...
23 novembre 2011 à 23:31:30

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'.
24 novembre 2011 à 2:02:05

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.
24 novembre 2011 à 9:17:07

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.

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.

Quelques liens sur le sujet en général :
http://en.wikipedia.org/wiki/Approximate_string_matching
http://en.wikipedia.org/wiki/Spelling_suggestion
http://stackoverflow.com/questions/229 [...] spell-checker
http://www.java.net/external?url=http: [...] rary/j-jazzy/
http://norvig.com/spell-correct.html


Citation : Mr21

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.
25 novembre 2011 à 13:54:17

@Pouet_forever :

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) return inf;), 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.
25 novembre 2011 à 22:30:49

Ca a l'air intéressant, je regarderai tout ce que tu as proposé. :)
28 mai 2012 à 8:07:07

Bon ...
Juste parce-que je voulais vraiment le faire ce défi donc voila mon code :
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <ctype.h>

#define ERROR(x) do puts(x), exit(1); while( 0 )


#define ROT_L(x, n)   ( (((x) << n) & 0xFFFFFFFF ) | ((x) >> (32 - n)) )


#define K0_19          0x5A827999U
#define K20_39         0x6ED9EBA1U
#define K40_59         0x8F1BBCDCU
#define K60_79         0xCA62C1D6U

#define H0             0x67452301U
#define H1             0xEFCDAB89U
#define H2             0x98BADCFEU
#define H3             0x10325476U
#define H4             0xC3D2E1F0U


uint32_t f(uint32_t x, uint32_t y, uint32_t z, uint32_t t)
{
  switch (t / 20) {
  case 0:
    return ((uint32_t)(x & y) | ((~x) & z));
    // Complement à 1 ou à 2 ?
  case 2:
    return (x & y) | (x & z) | (y & z);

  case 1:
  case 3:
    return x ^ y ^ z;

  }
}
void sha1Block512(unsigned char *block, uint32_t * H)
{
    uint32_t W[80] = {0};
    uint32_t t, a = 0, b = 0, c = 0, d = 0, e = 0;
    for(t = 0; t < 16; ++t)
        W[t]  = ((uint32_t) block[t * 4]) << 24,
        W[t] |= ((uint32_t) block[t * 4 + 1]) << 16,
        W[t] |= ((uint32_t) block[t * 4 + 2]) << 8,
        W[t] |= ((uint32_t) block[t * 4 + 3]);
        
    for (t = 16; t < 80; ++t)
      W[t] = ROT_L(W[t - 3] ^ W[t - 8] ^ W[t - 14] ^ W[t - 16], 1);
    a = H[0], b = H[1], c = H[2], d = H[3], e = H[4];
    for (t = 0; t < 80; ++t)
    {
      uint32_t T = ROT_L(a, 5) + f(b, c, d, t) + e +
                  ((uint32_t[]){ K0_19, K20_39, K40_59, K60_79 })[t / 20] + W[t];
      T &= 0xFFFFFFFF;
      e = d;
      d = c;
      c = ROT_L(b, 30);
      b = a;
      a = T;
    }
    H[0] += a;
    H[1] += b;
    H[2] += c;
    H[3] += d;
    H[4] += e;
  
}
void sha1Hash(unsigned char *src, uint64_t l, uint32_t * dst)
{
  unsigned char block[64] = { 0 }, *src_ = src, is_1 = 0;
  uint32_t H[5] = { H0, H1, H2, H3, H4 }, i;
  uint64_t s = l;

  while (s / 56)
  {
    unsigned char block[64] = { 0 }, i;
    for (i = 0; i < 64 && s; ++i, ++src_, --s)
      block[i] = *src_;
    if (!s && i < 64)
      block[i] = 1 << 7, is_1 = 1;
    sha1Block512(block, H);
  }
  {
    unsigned char block[64] = { 0 }, i;
    for (i = 0; i < 64 && s; ++i, ++src_, --s)
      block[i] = *src_;
    if (!is_1)
      block[i] = 1 << 7;
    for (l <<= 3, i = 0; i < 8 && l; ++i, l >>= 8)
      block[63-i] = l & 0xFF;
    sha1Block512(block, H);
  }

  for(int i = 0 ; i < 5 ;++i)
    dst[i] = H[i];
}
char* getString(void)
{
  int i = 1, c = 0;
  char* str = malloc( i+1 );
  if( !str )
      goto err;
  
  while( (c = getchar()) != '\n' && c != EOF)
  {
    char* tmp;
    str[i++-1] = c;
    tmp = realloc(str, i+1);
    if( tmp )
      str = tmp;
    else
      goto err;
  }
  str[i-1] = '\0';
  
  return str;
err:
  free(str);
}
char isIn(uint32_t H[5], FILE *fichierH)
{
  uint32_t hashF[5];
  rewind(fichierH);
  while(fread(hashF, sizeof *hashF, 5, fichierH) )
    if( !memcmp(H, hashF, sizeof *hashF * 5) )
      return 1;
      
  return 0;
}
int main(void)
{
  size_t nbL = 0;
  FILE* fichier;
  
  start:
  
  if( fichier = fopen("dicoH.txt", "rb") )
  {
    char* string = getString(), *tmp;
    for(int i = 0; string[i] ; ++i)
      string[i] = tolower(string[i]);
    tmp = strtok(string, " ,.");
    while(tmp)
    {
      uint32_t hash[5];
      if( tmp[1] == '\'')
        if( strchr("cdjlmnpst", *tmp) )
          tmp+=2;
        else
        {
          printf("L'apostrophe n'est pas correcte. [%s]", tmp);
          fclose(fichier);
          return 0;
        }
      sha1Hash(tmp, strlen(tmp), hash);
      if( !isIn(hash, fichier) )
      {
        printf("La phrase n'est pas correcte. [%s]", tmp);
        fclose(fichier);
        return 0;
      }
      tmp = strtok (NULL, " ,.");
    }
  }
  else if( fichier = fopen("dico.txt", "r") )
  {
    FILE* fichierH = fopen("dicoH.txt", "wb");
    if( !fichierH )
      ERROR("Fichier de hash impossible à créer");
    char line[70];
    uint32_t dst[5];
    while(fgets(line, 70, fichier))
    {
      *strchr(line, '\n') = 0;
      sha1Hash(line, strlen(line), dst);
      fwrite( dst , sizeof *dst , 5 , fichierH);
      ++nbL;
    }
    fclose(fichierH);
    fclose(fichier);
    goto start;
  }
  
  puts("La phrase semble correcte");
  return 0;
}


Pour le dico, j'ai piqué celui de l'exercice en Python de yoch, le solveur de mots-croisés.

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

[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.
  • Editeur
  • Markdown