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

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
Salut Warny et merci pour la réponse.
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...
cs_Warny Messages postés 473 Date d'inscription mercredi 7 août 2002 Statut Membre Dernière intervention 10 juin 2015
25 sept. 2008 à 14:17
Salut DroleDeCerfeuil,
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.
DroleDeCerfeuil Messages postés 2 Date d'inscription mercredi 24 septembre 2008 Statut Membre Dernière intervention 30 septembre 2008
25 sept. 2008 à 14:12
Super source! Bravo.
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
helene0618 Messages postés 42 Date d'inscription mercredi 4 mars 2009 Statut Membre Dernière intervention 11 juin 2009
12 mars 2008 à 13:59
merci beaucoup
cs_Bidou Messages postés 5486 Date d'inscription dimanche 4 août 2002 Statut Membre Dernière intervention 20 juin 2013 61
10 mars 2008 à 23:21
Bonsoir,
C'est le rapport entre la distance de Levenshtein et la taille du plus grand string.
Voir la property ErrorPercent dans le code.
helene0618 Messages postés 42 Date d'inscription mercredi 4 mars 2009 Statut Membre Dernière intervention 11 juin 2009
10 mars 2008 à 19:31
je voudrais savoir comment vous alculer le pourcentage ?
gdkenny Messages postés 3 Date d'inscription mercredi 11 juin 2003 Statut Membre Dernière intervention 3 septembre 2007
3 sept. 2007 à 15:20
Merci pour cette classe utile
cs_Bidou Messages postés 5486 Date d'inscription dimanche 4 août 2002 Statut Membre Dernière intervention 20 juin 2013 61
5 sept. 2006 à 12:58
Oui, je me suis amusé à faire un petit soundex (et soundex2) pour la langue Française (chaque langue a une implémentation différente) : http://www.csharpfr.com/codes/ALGORITHME-SOUNDEX_39423.aspx
cs_Warny Messages postés 473 Date d'inscription mercredi 7 août 2002 Statut Membre Dernière intervention 10 juin 2015
30 août 2006 à 08:41
Il y a d'autres algorithme de comparaison de chaînes : par exemple le SOUNDEX utilisé par les pages jaunes. Word utilise entre autre la distance de Levenshtein.

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.
cs_Bidou Messages postés 5486 Date d'inscription dimanche 4 août 2002 Statut Membre Dernière intervention 20 juin 2013 61
29 août 2006 à 22:52
Sebmafate> Y'a de fortes chances que ça soit le cas oui! J'ai pas réussi à trouver la confirmation dans des articles.

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.
cs_badrbadr Messages postés 475 Date d'inscription jeudi 19 juin 2003 Statut Membre Dernière intervention 3 novembre 2008 1
29 août 2006 à 21:07
Interessant, ça doit être comme ça que Google me corrige tout le temps !
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?
sebmafate Messages postés 4936 Date d'inscription lundi 17 février 2003 Statut Membre Dernière intervention 14 février 2014 37
29 août 2006 à 11:59
sympa comme source...
c'est en partie l'un des principes utilisé dans les correcteurs d'orthographe. non ?
cs_Bidou Messages postés 5486 Date d'inscription dimanche 4 août 2002 Statut Membre Dernière intervention 20 juin 2013 61
28 août 2006 à 19:42
Yep, sorry j'avais un peu la tête en l'air...
C'est effectivement un peu plus rapide, je vais donc changer. Merci.
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 à 19:32
re,
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
cs_Bidou Messages postés 5486 Date d'inscription dimanche 4 août 2002 Statut Membre Dernière intervention 20 juin 2013 61
28 août 2006 à 18:57
Ben suffit d'ajouter la classe Levenshtein.cs dans le projet
iow4 Messages postés 302 Date d'inscription samedi 22 octobre 2005 Statut Membre Dernière intervention 2 novembre 2008 4
28 août 2006 à 18:56
Parcontre comment l'integrer dans un programme ou sont les variables a definir pour comparer deux chaines ?
iow4 Messages postés 302 Date d'inscription samedi 22 octobre 2005 Statut Membre Dernière intervention 2 novembre 2008 4
28 août 2006 à 18:55
a oui on fixe un taux minimum pour l'interpreter.
Tout devient clair dans mon esprit merci
cs_Bidou Messages postés 5486 Date d'inscription dimanche 4 août 2002 Statut Membre Dernière intervention 20 juin 2013 61
28 août 2006 à 18:53
Warny> hum, je ne comprends pas ce que tu dis, ta ligne retourne un booleen alors qu'il me faut un int !
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.
iow4 Messages postés 302 Date d'inscription samedi 22 octobre 2005 Statut Membre Dernière intervention 2 novembre 2008 4
28 août 2006 à 18:39
Dans exemple concret on pourait l'utiliser ?
Merci
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
ligne 18, tu devrais pouvoir utiliser cette syntaxe :

this._word1[j - 1] == this._word2[i - 1]

ça devrait optimiser
Rejoignez-nous