Levenštejnova vzdálenost

Levenštejnova vzdálenost (také nazývána editační vzdálenost) je metrika zavedená v roce 1965 ruským matematikem Vladimirem Iosifovičem Levenštejnem pro měření editační vzdálenosti v prostoru textových řetězců. Připouští tři jednoduché editační operace, totiž přidání libovolného znaku, vypuštění libovolného znaku nebo záměnu libovolného znaku za jiný libovolný. Nejmenší počet těchto operací nutný k převedení jednoho řetězce na druhý udává Levenštejnovu vzdálenost mezi nimi.

Typický příklad použití Levenštejnovy vzdálenosti je v algoritmech korektorů překlepů.

Reference

V tomto článku byl použit překlad textu z článku Levenshtein-Distanz na německé Wikipedii.