Archivio per la categoria ‘Algoritmi’

Edit Distance o Levenshtein Distance: un algoritmo di similarità tra stringhe

In questo posto vedremo l’algoritmo di Editi Distance [1] detto anche di Levenshtein Distance. La edit distance, o distanza di Levenshtein, tra due stringhe s1 e s2 il minimo numero di sostituzioni, cancellazioni o inserimenti che occorre effettuare per ottenere s1 da s2. Ad esempio, la distanza tra gtgcca e ggcga è 2 (bisogna inserire una t nella seconda stringa e sostituire la penultima g con c per ottenere la prima stringa).

elettronica