Discussion :

[Davboc]

Salut

Je suis en ce moment à la recherche d'un algo de comparaison approximative de chaîne, comme levenshtein, soundex ou autres...

En fait j'en ai trouvé quelques-uns mais j'aimerais savoir lequel est le plus efficace. Quelqu'un sait ou je pourrais trouver un comparatif (google est pas mon ami sur ce coup)

J'imagine que c'est un problème assez récurrent lorsque l'on souhaite faire une fonction de recherche un tant soit peu efficace non ?

Pourrais-je avoir vos retours d'expérience ?

Merci à vous

[pseudocode]

Pour les recheches sur notre intranet local, j'ai utilisé Damerau-Levenshtein pour les recherches de noms communs et Metaphone pour les recherches de nom propres.

Ca marche plutot pas mal.

[Davboc]

Mais metaphone n'est-il pas très orienté vers l'anglais ?

[pseudocode]

Mais metaphone n'est-il pas très orienté vers l'anglais ?

Pour les noms propres, l'algo original se débrouille pas trop mal. Et tu peux toujours lui ajouter des regles pour les phonemes francais:

G+A -> K (Garder)
G+E -> J (manGe)
G+I -> J (aGir)
G+O -> K (Gouter)
G+U -> K (lanGue)
...

[random]

je confirme que Damerau-Levenshtein donne de bons résultats

tu trouveras ici (de mémoire rubrique sql) des soundex aménagés qui peuvent donner de bons résultats

[misslyma]

Bonjour
excusez moi de vous interompre. Mais j'ai peut etre un pb un peu proche de le votre. En fait: je travail sur un projet : correcteur orthographique en c sous linux et je suis débutante.
je suis maintenant dans la phase d'algo: la conception préliminaire pour écrire une fonction en algo :
fonction MotsProches(d: Dictionnaire,motMalOrthographie : MOT)Liste<Mot>

Dictionnaire et Mot sont les deux TAD que j'ai crée.
mon problème c'est que je n'ai pas une idée pour concevoir cette fonction à savoir qu'elle doit verifier si le mot est dans le dictionnaire et donc elle l'affiche, sinon elle doit afficher la liste des mots proches et c'est la où je ne sais pas comment je dois choisir les mots proches dans le dictionnaire ..
merci de me donner une piste.

[Davboc]

Après recherche j'ai trouvé tout un tas d'algorithmes interessants.

Il y a le Sacro saint Levenshtein, son dérivé Damereau-Levenshtein, Jaro-Winkler, une version évoluée.

D'un autre côté tu trouvera par exemple TF-IDF

Sinon tu as des algos comme Soundex et Metaphone qui se basent sur la sonorité des mots et les encodant au préalable. C'est plus rapide que les autres mais l'efficacité est moindre.

Tu peux faire une recherche sur google des expressions "recherche approximative", "comparaison approximative", "approximative matching", "fuzzy matching"...

Bon courage

P.S : recherche les travaux d'un certain cohen à ce sujet ilss sont interessants