LEVENSHTEIN (DISTANCE DE), ALGORITHME
cs_Warny
Messages postés
473
Date d'inscription
mercredi 7 août 2002
Statut
Membre
Dernière intervention
10 juin 2015
-
28 août 2006 à 17:22
DroleDeCerfeuil Messages postés 2 Date d'inscription mercredi 24 septembre 2008 Statut Membre Dernière intervention 30 septembre 2008 - 30 sept. 2008 à 09:43
DroleDeCerfeuil Messages postés 2 Date d'inscription mercredi 24 septembre 2008 Statut Membre Dernière intervention 30 septembre 2008 - 30 sept. 2008 à 09:43
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/39298-levenshtein-distance-de-algorithme
https://codes-sources.commentcamarche.net/source/39298-levenshtein-distance-de-algorithme
30 sept. 2008 à 09:43
Mais je pense que ce n'est pas assez précis... Si par exemple la différence se situe su la première lettre du deuxième mot, rien ne vas plus...
J'ai trouvé une source qui associe la distance de levenshtein et un calcul via "l'algo hongrois", qui donne de bon résultats... (http://www.codeproject.com/KB/recipes/improvestringsimilarity.aspx?fid=203320&fr=1&df=90&mpp=25&noise=3&sort=Position&view=Quick#xx0xx)
Il me reste à voir comment gérer le cas où l'on peut omettre un mot dans la recherche...
25 sept. 2008 à 14:17
Il faut que tu splites ta chaîne et que tu classes les mots dans l'ordre alphabétique. Ensuite, tu reconstitues ta chaîne.
25 sept. 2008 à 14:12
Je l'ai un peu adaptée pour qu'elle ne soit pas case sensitive, ignore les accents etc.
Par contre, dans le moteur de recherche que j'implémente, il reste deux points sur lesquels je butte un peu :
Comment faire efficacement pour qu'il ne tienne pas compte de l'ordre des mots (Jean Pierre et Pierre Jean retourne la même distance de Levenshtein) et comment faire si on recherche qu'un seul mot (Jean et Jean Pierre).
Si quelqu'un a une idée... merci
12 mars 2008 à 13:59
10 mars 2008 à 23:21
C'est le rapport entre la distance de Levenshtein et la taille du plus grand string.
Voir la property ErrorPercent dans le code.
10 mars 2008 à 19:31
3 sept. 2007 à 15:20
5 sept. 2006 à 12:58
30 août 2006 à 08:41
Pour la reconnaissance de voix, il y aussi d'autres algos, le Levenshtein est visiblement assez gourmand en mémoire surtout sur des longues chaînes. Comparer deux sons peut donc devenir assez fastidueux avec cette méthode : il faudrait 8000x8000 o soit ~64Mo pour comparer 1 seconde de son à 8bits 8kHz.
29 août 2006 à 22:52
Badrbadr> Pour la reconnaissance vocale, je m'imagine bien que y'a encore d'autres aspects qui rentrent en ligne de compte et que ça complique tout de suite bien plus les choses ! L'idée de base est la même, mais l'implémentation doit être quelque peu plus complexe.
29 août 2006 à 21:07
Bravo Bidou.
Pour la reconnaissance vocale, c'est à dire déterminer si une voix apartient à tel ou tel, c'est le même principe ou encore faut-il utiliser une technique dérivée?
29 août 2006 à 11:59
c'est en partie l'un des principes utilisé dans les correcteurs d'orthographe. non ?
28 août 2006 à 19:42
C'est effectivement un peu plus rapide, je vais donc changer. Merci.
28 août 2006 à 19:32
j'avais juste remis la parie test, tu auras compris qu'en complétant la ligne tu récupère un entier
(this._word1[j - 1] == this._word2[i - 1]) ? 0 : 1
28 août 2006 à 18:57
28 août 2006 à 18:56
28 août 2006 à 18:55
Tout devient clair dans mon esprit merci
28 août 2006 à 18:53
Iow4> Y'a plusieurs principe qu'on peux mettre en oeuvre grâce à ce modèle (après évidemment, il faut éven. l'évoluer). Un qui me vient directement à l'esprit serait un bot pour un chat : Si l'utilisateur rentre Salut, salut, salu, salü voire même sallu ou autre, on peut l'interpréter comme étant la même chaîne en évaluant son taux de ressemblance.
28 août 2006 à 18:39
Merci
28 août 2006 à 17:22
this._word1[j - 1] == this._word2[i - 1]
ça devrait optimiser