Calcolare distanza di Levenshtein tra due stringhe


Scommetto che sono pochissime le persone che sanno veramente di cosa sto parlando, per tutti gli altri ecco un piccolo esempio esplicativo :

Avete presente la funzione forse cercavi di google ? oppure la correzione automatica di word? Entrambe si basano sull’algoritmo di Levenshtein, questo costituisce il numero minimo di mosse necessarie per trasformare la stringa s1 nella stringa s2; le mosse consentite sono:

  • la cancellazione di un carattere
  • la sostituzione di un carattere
  • l’aggiunta di un carattere

Quindi, per esempio, la distanza tra bar e biro è 2

Per costruire un programma che assolva tale funzione basta saper utilizzare le matrici e le stringhe, andiamo a capire nel dettaglio le operazioni da svolgere !

Dopo aver letto le due stringhe da tastiera ( e letto la loro lunghezza ) dobbiamo creare una matrice di dimensione (l1 +1) * (l2+1) :

public class Distance {

/// <summary>
/// Compute Levenshtein distance
/// </summary>
/// <param name="s">String 1</param>
/// <param name="t">String 2</param>
/// <returns>Distance between the two strings.
/// The larger the number, the bigger the difference.
/// </returns>
  public int LD (string s, string t) {
  int n = s.Length; //length of s
  int m = t.Length; //length of t
  int[,] d = new int[n + 1, m + 1]; // matrix
  int cost; // cost
    // Step 1
    if(n == 0) return m;
    if(m == 0) return n;
  
    // Step 2
    for(int i = 0; i <= n; d[i, 0] = i++);
    for(int j = 0; j <= m; d[0, j] = j++);

    // Step 3
    for(int i = 1; i <= n;i++) {

      //Step 4
      for(int j = 1; j <= m;j++) {
      
      // Step 5
      cost = (t.Substring(j - 1, 1) == s.Substring(i - 1, 1) ? 0 : 1);
      
      // Step 6
      d[i, j] = System.Math.Min(System.Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                  d[i - 1, j - 1] + cost);
      }
    }
    
     // Step 7
    return d[n, m];
  }
}

Basterà richiamare la funzione in questo modo distanza(“bar”,”biro”) e sapremo la distanza tra due parole

4 thoughts on “Calcolare distanza di Levenshtein tra due stringhe

  1. Interessante, è un tema quasi per studiosi di Scrabble e giocatori automatici.
    Considerando solo parole, e non sigle, del dizionario italiano è risolvibile con un po’ di (parentesi) CIAO
    (CO)
    (CU)

    Come dire che la linguistica computazionale non cresce solo sugli alberi…

  2. Pingback: Riconoscere le parole: Levenshtein e dintorni « Zmaker's Weblog

  3. Sì ma il problema è uno, come fa google a sparare subito la stringa più vicina? dovrebbe effettuare milioni di confronti in real-time?!? sembra più plausibile che per ciascuna stringa venga associato un valore e che la query sia del tipo minrangeval < val(string) < maxrangeval.
    Che ne pensi?

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...