LEVENSHTEIN (DISTANCE DE), ALGORITHME

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

Télécharger le zip

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)