jump to navigation

Programmazione dinamica - Distanza di Levenshtein 13 Gennaio 2008

Posted by fripp in Algoritmi, C, Informatica, Matematica, Programmazione.
Tags: ,
add a comment

La Distanza di Levenshtein è la distanza tra due stringhe S1 ed S2, dove per distanza intendiamo il numero minimo di operazioni elementari che occorre fare per trasformare la stringa S1 nella stringa S2.

Queste operazioni elementari includono:

  • cancellazione di un carattere
  • sostituzione di un carattere con un altro
  • inserimento di un carattere

L’algoritmo di Levenshtein consente di calcolare la distanza tra una stringa di lunghezza m e una stringa di lunghezza n in tempo O(nm)

Per la definizione formale dell’algoritmo, potete consultare questa pagina.

In questi giorni ho implementato sia la versione “classica”, che fa uso di una matrice di ordine (m+1) \cdot (n+1), sia una versione più ottimizzata, che si limita ad usare due vettori di lunghezza m.

Ecco la prima versione:
(more…)