Recherche lexicographique en C ?

[Dumoria]

Bonjour à tous !

Pour un projet en C, j'ai besoin de faire une recherche approchée sur ce que saisit un utilisateur.

Exemple pour que ce soit plus clair : l'utilisateur saisit "Mateau". J'ai en mémoire un dictionnaire de mots (sous forme de liste chainée ou tableau de pointeurs, peu importe), et j'aimerais que mon logiciel retourne "Marteau", qui sera probablement le plus proche. Une fonction de correction, en somme.

J'avais pensé faire un truc du genre : mon programme recherche lettre par lettre le nombre ,la taille et l'ordre des "motifs" communs trouvés. Dans mon exemple il trouverait "Ma" et "teau", de tailles 2 et 4, et dans l'ordre, et ca lui suffirait pour décider que "Marteau" est le plus proche.

Avez vous de meilleures idées ? L'un d'entre vous a-t-il déjà eu besoin de faire un tel truc ? Il y a surement des sources sur le net qui font déjà ca, mais c'est pas très facile à trouver.... Et ma solution me semble pas très optimisée et un peu usine à gaz...

Si quelqu'un pouvait éclairer ma lanterne ce serait super cool !
A+

 

[thrips]

Salut, j'ai eu besoin de faire un programme très semblable à ça dans mes cours cet automne, je te files l'adresse de l'énoncé du programme, tu pourra mieux comprendre.

Vous devez être connecté pour voir les liens.

Si tu as des questions, n'hésite pas à les poser vu que j'ai fait le travail et il semblait fonctionner.

 

[Dumoria]

La méthode de distance d'edition a l'air pas mal, je vais essayer de l'implanter, je reviendrai poster si j'ai des soucis. Merci bien pour ton aide !

 

[Dumoria]

Euh par contre j'ai eu du mal avec l'algorithme de Levenshtein, il est un peu tordu quand même. En fait, je vois bien intuitivement qu'on va bien avoir la distance au final,
mais si il fallait que je démontre que la distance qu'on va obtenir ainsi est bien la bonne dans tous les cas, ca va être plus dur...
Tu l'avais bien compris ?
Enfin peu importe, je vais la coder dans mon projet, je te tiendrai au courant de si c'est bon.
A+