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
 [TECHDAYS 2012] SESSION WEBMATRIX 2 : LE COUTEAU SUISSE GRATUIT POUR VOS DéVELOPPEMENTS WEB - SLIDES[TECHDAYS 2012] SESSION WEBMATRIX 2 : LE COUTEAU SUISSE GRATUIT POUR VOS DéVELOPPEMENTS WEB - SLIDES par gpommier
Suite à la session que j'ai présenté sur WebMatrix 2, vous pouvez trouver les slides ici, ainsi que les démos en packages nuget : démos1 et démos2 J'en profite pour remercier chaleureusement tous ceux qui sont venus très nombreux à cette sess...
Cliquez pour lire la suite de l'article par gpommier [SHAREPOINT] LES SESSIONS TECHDAYS 2012.[SHAREPOINT] LES SESSIONS TECHDAYS 2012. par Patrick Guimonet
Voici donc pour ceux qui n'ont pas pu venir, ou ceux qui n'ont pas pu toutes les suivre la liste des sessions SharePoint aux TechDays 2012, que je mettrais à jour dès que les liens des vidéo seront disponibles. Ou ici : http...
Cliquez pour lire la suite de l'article par Patrick Guimonet TECHDAYS PARIS 2012 : SESSION PLEINIèRE JOUR 3TECHDAYS PARIS 2012 : SESSION PLEINIèRE JOUR 3 par ROMELARD Fabrice
Speaker: Bernard Ourghanlian Cette session est comme chaque jour transmise en live par BrainSonic, et j'ai donc suivi cette troisième pleinière par ce moyen sur mon iPad . Elle est dédiée comme chaque année à la mise en perspective de l'é...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice MISHRA READER : UN LECTEUR RSS TRèS ZUNE STYLE EN OPEN SOURCE !MISHRA READER : UN LECTEUR RSS TRèS ZUNE STYLE EN OPEN SOURCE ! par Vko
Hier durant une session dédiée aux Techdays 2012, j'ai eu le plaisir d'annoncer la sortie de la Béta 2 de Mishra Reader. C'est quoi ? Pour les utilisateurs, c'est une vraie expérience de lecture de flux RSS sur Windows. Rien à voir avec les produit...
Cliquez pour lire la suite de l'article par Vko [FRAMEWORK 4] LES TASKS ET LE THREAD UI[FRAMEWORK 4] LES TASKS ET LE THREAD UI par fathi
Je viens de passer quelques temps au TechDay's et j'ai pu voir pas mal de session intéressante. Par contre une chose m'a un peu étonné lors de certaines de ces sessions qui abordaient les améliorations du framework .NET (donc le 4.5) : en gros, bea...
Cliquez pour lire la suite de l'article par fathi
Logiciels
 Academy System (17.2.1.0)ACADEMY SYSTEM (17.2.1.0)Logiciel de gestion des établissements.
- élèves/étudiants (inscription, dossier, absence...)
-... Cliquez pour télécharger Academy System Easy-Planning (1.0.0.1)EASY-PLANNING (1.0.0.1)Basé sur les mêmes principes que MyPlanning, Easy-Planning permet de créer des plannings sous la ... Cliquez pour télécharger Easy-Planning COLLECTOR PLUS (3.00B)COLLECTOR PLUS (3.00B)COLLECTOR PLUS version 3.00B est un logiciel utilisant une base de données alimentée par :
- L... Cliquez pour télécharger COLLECTOR PLUS PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V7.4)PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V7.4)PONAMEDIA TV DEVIENS HELLLOOO FLASH
LA TV SUR VOTRE ORDINATEUR.
Toute une plateforme Multi... Cliquez pour télécharger PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO LettresFaciles 2011 (8.0.0.1)LETTRESFACILES 2011 (8.0.0.1)LettresFaciles est un logiciel facilitant la création et la rédaction de lettres types.
Son inte... Cliquez pour télécharger LettresFaciles 2011
|