Levenshtein (distance de), algorithme

Télécharger le projet
Commenter

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 / Exemple : 


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 !
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (cs_Bidou)