Accueil > > > LEVENSHTEIN (DISTANCE DE), ALGORITHME
 LEVENSHTEIN (DISTANCE DE), ALGORITHME
 Information sur la source
 Description
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
- 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 !
 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
 Sources de la même categorie
 Commentaires et avis
 Discussions en rapport avec ce code source dans le forum
Les Fonctions de traitement de chaîne [ par DrChal ]
DrChalBonjour,Vous allez dire que je suis très null, normal je débutte en c #.Qui peux me donner les correspondances entre VB et C# sur les différents
Recherche de Caractère dans une chaîne [ par DrChal ]
DrChalSalut ,Je cherche le moyen de rechercher un mot dans une chaîne de caractère.En VB, on avait la fonction InStr, existe t-elle en C#?Pouvez vous
Je comprends pas cette algorithme [ par kaiwoo ]
private bool AUneVirgule (double nb){long tmp = (long)nb;if (tmp == nb)return false;elsereturn true;}Pour info, il a été fait par un super membre du f
Besoin d'aide : Bureau a distance [ par dczh ]
Bonjour a tous, je suis tout nouveau sur le forum, exusez d'avance les us et coutumes non respectées.Voila, je cherche a creer un prog qui fait : "bur
installation à distance [ par flogalea ]
bonjour,je voudrais savoir s'il y a un moyen d'installer un programme sur une machine B à partir d'une machine A ? Et cela sans avoir au prealable ins
Algorithme de placement [ par oberown ]
Je cherche des noms d'algorithmes ou des idées, pour résoudre ce genre de problème.On a trois jours, et chaque jours 2 personnes peut se présenter. On
Algorithme Mot Caché [ par nuns ]
Salut tout le monde,Je voudrais savoir si il y a quelqu ' un qui aurait un générateur de mot Caché, le jeux, avec les grille ou il faut chercher les m
algorithme génétique programmé en c# [ par johelle ]
slt,je veux savoir si'il ya quelqu'un dans ce forum qui a un programme d'un algorithme génétique en c#et merci.
Focus... [ par vxr888 ]
Salut à tous,J'ai commencé à créer un application permettant d'entrer une chaîne de caractères prédéfinie
utilisation a distance de internet explorer [ par rvmartin ]
SalutJe debute en C#.Je voudrais savoir comment recuperer les composants (boutons, zone de texte) d'une page HTML. La page se trouve dans&nb
|
Derniers Blogs
 [RIA SERVICES] INCLUDE ET DOMAINDATASOURCE[RIA SERVICES] INCLUDE ET DOMAINDATASOURCE par Audrey
Dans un de mes articles précédents , j'avais parlé des DomainDataSource avec RIA Services dans le cas d'une interface Maître - Détail. Dans le même principe, je vais parler d'une autre manière de mettre en forme ce cas d'interface avec RIA Services. Et po...
Cliquez pour lire la suite de l'article par Audrey ZUNE : VERSION ZUNE SOFTWARE V 4.2 ET LA SOCIALISATIONZUNE : VERSION ZUNE SOFTWARE V 4.2 ET LA SOCIALISATION par ROMELARD Fabrice
Une des nouveautés de la version V 3.0 était l'apparition de l'onglet Social qui ne fonctionnait que si le MarketPlace était activé sur son poste. Cela limitait donc son intérêt, car hors du cadre commercial USA-CANADA, peu de monde trouva...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice PRATIQUE DE SILVERLIGHT PAR ERIC AMBROSIPRATIQUE DE SILVERLIGHT PAR ERIC AMBROSI par MPOWARE
Je viens de finir la lecture du dernier livre d'
Eric Ambrosi
éditions PEARSON
Son livre donne une approche pratique de Silverlight qui sera aussi bien comprise par le développeur que par le designeur.
Tous les aspects du développement RIA sont abor...
Cliquez pour lire la suite de l'article par MPOWARE APPRENDRE à DéVELOPPER POUR LES MOBILES AVEC LA NOUVELLE GéNéRATION .NETAPPRENDRE à DéVELOPPER POUR LES MOBILES AVEC LA NOUVELLE GéNéRATION .NET par odewit
2 déclinaisons de Silverlight et 2 déclinaisons de Mono permettent dorénavant (ou permettront prochainement) de développer des applications .NET mobiles pour les principales plates-formes du marché :
Silverlight pour Symbian, basé sur Silverlight 2...
Cliquez pour lire la suite de l'article par odewit ZUNE : NOUVELLE VERSION DU ZUNE SOFTWARE - V 4.2ZUNE : NOUVELLE VERSION DU ZUNE SOFTWARE - V 4.2 par ROMELARD Fabrice
Avec la dernière génération du lecteur MP3 de Microsoft, le ZUNE HD, Microsoft a publié une nouvelle version du logiciel pour PC. Ainsi, je me suis décidé à installer celle-ci sur mon Tablet PC ACER, comme toujours le logiciel est donc tél...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice
Logiciels
 Academy System (10.9.4.0)ACADEMY SYSTEM (10.9.4.0)Logiciel de gestion des établissements.
- élèves/étudiants (inscription, dossier, absence...)
-... Cliquez pour télécharger Academy System Xilisoft Convertisseur Vidéo Ultimate (5.1.39.0305)XILISOFT CONVERTISSEUR VIDéO ULTIMATE (5.1.39.0305)Xilisoft Convertisseur Vidéo Ultimate est un outil puissant de conversion vidéo, facile à utilise... Cliquez pour télécharger Xilisoft Convertisseur Vidéo Ultimate Xilisoft DVD Ripper Ultimate (5.0.64.0304)XILISOFT DVD RIPPER ULTIMATE (5.0.64.0304)Xilisoft DVD Ripper Ultimate est un logiciel excellent pour copier et convertir DVD vers presque ... Cliquez pour télécharger Xilisoft DVD Ripper Ultimate Rigs of Rods (63.3)RIGS OF RODS (63.3)c'est un jeu de multi-simulation camions,autobus voitures, avions, bateaux, hélicoptère avec défo... Cliquez pour télécharger Rigs of Rods
|