LEVENSHTEIN (DISTANCE DE), ALGORITHME levenshtein, distance, algorithme, chaîne, ressemblance, Source N°39298

Information sur la source

Catégorie :Maths & Algorithmes

Classé sous : levenshtein, distance, algorithme, chaîne, ressemblance Niveau : Débutant Date de création : 28/08/2006 Date de mise à jour : 06/09/2006 11:41:56 Vu / téléchargé: 8 786 / 379

Auteur : Bidou

Site perso

Ecrire un message privé

Ce membre participe au partage de revenus publicitaires

Note :

9,80 / 10

1
2
3
4
5
6
7
8
9
10

Commentaire sur cette source (17)

Ajouter un commentaire et/ou une note

Description

Cliquez pour voir la capture en taille normale

Distance de Levenshtein C# / Levenshtein Distance C#

La distance de Levenshtein (LD) mesure la similarité entre deux chaînes de caractères. Elle est égale au nombre minimal de caractères qu'il faut supprimer, insérer, ou remplacer pour passer d’une chaîne à l’autre. Son nom provient de Vladimir Levenshtein qui l'a définie en 1965. Elle est aussi connue sous le nom de distance d'édition ou encore de déformation dynamique temporelle, notamment en reconnaissance de la parole.

Cette distance est d'autant plus grande que le nombre de différences entre les deux chaînes est grand. La distance de Levenshtein peut être considérée comme une généralisation de la distance de Hamming.

Le code est très simple, j'ai en plus pris le temps de le commenter.

Source

Version Visual Basic de ce code disponible !

public int LevenshteinValue()
{
if (this._n == 0) return this._m;
else if (this._m == 0) return this._n;
else
{
List<int> lastColumn = new List<int>(this._m);
for (int i = 1; i <= this._m; i++) lastColumn.Add(i);
int lastValue = 0;
int forLastValue = 0;
// Get the minimum value
for (int j = 1; j <= this._n; j++)
{
for (int i = 0; i < this._m; i++)
{
int x = (i == 0 ? j : lastValue) + 1;
int y = lastColumn[i] + 1;
int z = (i == 0 ? j - 1 : lastColumn[i - 1]) + (this._word1[j - 1] == this._word2[i] ? 0 : 1);
forLastValue = lastValue;
lastValue = this.Min(x, y, z);
if (i > 0) lastColumn[i - 1] = forLastValue;
if (i == this._m - 1) lastColumn[i] = lastValue;
}
}
this._levenshtein = lastValue;
return this._levenshtein;
}
}

public int LevenshteinValue()
{
  if (this._n == 0) return this._m;
  else if (this._m == 0) return this._n;
  else
  {
    List<int> lastColumn = new List<int>(this._m);
    for (int i = 1; i <= this._m; i++) lastColumn.Add(i);
    int lastValue = 0;
    int forLastValue = 0;

    // Get the minimum value
    for (int j = 1; j <= this._n; j++)
    {
      for (int i = 0; i < this._m; i++)
      {
        int x = (i == 0 ? j : lastValue) + 1;
        int y = lastColumn[i] + 1;
        int z = (i == 0 ? j - 1 : lastColumn[i - 1]) + (this._word1[j - 1] == this._word2[i] ? 0 : 1);

        forLastValue = lastValue;
        lastValue = this.Min(x, y, z);

        if (i > 0) lastColumn[i - 1] = forLastValue;
        if (i == this._m - 1) lastColumn[i] = lastValue;
      }
    }
    this._levenshtein = lastValue;
    return this._levenshtein;
  }
}

Conclusion

Couplé avec un algorithme soundex (http://www.csharpfr.com/codes/ALGORITHME-SOUNDEX_39423.aspx) on arrive à faire des recherches assez pertinentes. Les utilisations sont multiples !

Fichier Zip

Pour les "Membres Club", vous pouvez télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Levenshtein
- Levenshtein
  - Properties
    - AssemblyInfo.cs 1 280 octets
  - Levenshtein.cs 5 131 octets
  - Levenshtein.csproj 1 998 octets
  - Program.cs 616 octets
- Levenshtein.sln 922 octets
- Levenshtein.suo11 264 octets

Télécharger le zip

Historique

28 août 2006 11:03:28 :: Algo un peu plus rapide. Mise en page.
28 août 2006 11:10:54 :: Re mise en page
28 août 2006 19:43:15 :: Petite amélioration (cf. remarque dans les commentaires)
30 août 2006 12:35:41 :: Modification de l'algorithme (~3x plus rapide d'après mes tests) : On ne calcul plus toute la matrice mais uniquement le dernier vecteur.
04 septembre 2006 16:33:26 :: Ajout de l'annotation finale
06 septembre 2006 11:41:56 :: Après quelques utilisations de cette classe, je me suis rendu compte qu'une méthode static s'imposait (souvent, on appelle que la méthode qui calcule la valeur)

Sources du même auteur

Toutes les sources de Bidou

Sources de la même categorie

Toutes les sources de la catégorie Maths & Algorithmes

Sources en rapport avec celle ci

Commentaires

Commentaire de Warny le 28/08/2006 17:22:21

ligne 18, tu devrais pouvoir utiliser cette syntaxe :

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

ça devrait optimiser
Commentaire de iow4 le 28/08/2006 18:39:15

Dans exemple concret on pourait l'utiliser ?
Merci
Commentaire de Bidou le 28/08/2006 18:53:28 administrateur CS

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.
Commentaire de iow4 le 28/08/2006 18:55:12

a oui on fixe un taux minimum pour l'interpreter.
Tout devient clair dans mon esprit merci
Commentaire de iow4 le 28/08/2006 18:56:35

Parcontre comment l'integrer dans un programme ou sont les variables a definir pour comparer deux chaines ?
Commentaire de Bidou le 28/08/2006 18:57:41 administrateur CS

Ben suffit d'ajouter la classe Levenshtein.cs dans le projet
Commentaire de Warny le 28/08/2006 19:32:45

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
Commentaire de Bidou le 28/08/2006 19:42:03 administrateur CS

Yep, sorry j'avais un peu la tête en l'air...
C'est effectivement un peu plus rapide, je vais donc changer. Merci.
Commentaire de sebmafate le 29/08/2006 11:59:57 administrateur CS

sympa comme source...
c'est en partie l'un des principes utilisé dans les correcteurs d'orthographe. non ?
Commentaire de badrbadr le 29/08/2006 21:07:22

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?
Commentaire de Bidou le 29/08/2006 22:52:18 administrateur CS

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.
Commentaire de Warny le 30/08/2006 08:41:29

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.
Commentaire de Bidou le 05/09/2006 12:58:23 administrateur CS

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
Commentaire de gdkenny le 03/09/2007 15:20:41

Merci pour cette classe utile
Commentaire de helene0618 le 10/03/2008 19:31:05

je voudrais savoir comment vous alculer le pourcentage ?
Commentaire de Bidou le 10/03/2008 23:21:33 administrateur CS

Bonsoir,
C'est le rapport entre la distance de Levenshtein et la taille du plus grand string.
Voir la property ErrorPercent dans le code.
Commentaire de helene0618 le 12/03/2008 13:59:53

merci beaucoup

Ajouter un commentaire

Discussions en rapport avec ce code source

Les Fonctions de traitement de chaîne par DrChal

Recherche de Caractère dans une chaîne par DrChal

Je comprends pas cette algorithme par kaiwoo

Besoin d'aide : Bureau a distance par dczh

installation à distance par flogalea

Algorithme de placement par oberown

Algorithme Mot Caché par nuns

algorithme génétique programmé en c# par johelle

Focus... par vxr888

utilisation a distance de internet explorer par rvmartin