Levenshteinetäisyys

Levenshteinetäisyys määritellään kahden merkkijonon välisenä pienimmän määrän yksittäisiä muokkauksia, joita tarvitaan toisen merkkijonon muuttamiseksi toiseen. Sallitut muokkaukset ovat merkin lisäys, poistaminen ja korvaaminen; kustannukset ovat tavallisesti yhtä suuret. Nimi juontaa Vladimir Levenshineen, joka julkaisi menetelmän vuonna 1965.

Käytännön laskenta tapahtuu dynaamisella ohjelmoinnilla. Tehtävä muodostetaan (n+1) × (m+1) -matriisiksi, jossa n ja m ovat merkkijonojen pituudet. Esimerkkitaso: D[0][j] = j ja D[i][0] = i. Rekurenssi on D[i][j] = min(D[i−1][j] + 1, D[i][j−1] + 1, D[i−1][j−1] + (s1[i−1] == s2[j−1] ? 0 : 1)). Tuloksena on D[n][m], pienin määrä muokkauksia.

Variantteja ovat Damerau–Levenshtein-etäisyys, joka sallii kahden peräkkäisen merkin vaihdon yhdessä muokkauksessa, sekä painotettu Levenshtein, jossa eri muokkauksille voi määritellä erilaiset kustannukset. Levenshtein-etäisyys eroaa Hamming-etäisyydestä, joka rajoittuu saman mittaisiin merkkijonoihin ja sallii vain substituutiot.

Sovellukset kattavat oikeinkirjoituksen tarkistuksen, fuzzy-hakujen ja ehdotusten generoinnin, OCR-virheiden korjaamisen sekä geneettisten sekvenssien tai muiden tekstipohjaisten tietojen vertailun. Tehottomin perusmalli on O(nm) sekä ajassa että tilassa; tilaa voi vähentää käyttämällä vain kaksi riviä. Käytännössä Levenshteinetäisyyttä tarjotaan useissa ohjelmointikirjastoissa, mikä tekee siitä yleisen työkalun epävarmojen merkkijonojen vertailuun.