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.
Příklady:
| řetězec 1 | řetězec 2 | vzdál. | poznámka |
|---|---|---|---|
| aaa | abc | 2 | dvě záměny |
| aaa | aaaa | 1 | jedno přidání |
| aaa | abaa | 1 | jedno přidání (uvnitř) |
| xxx | yyyy | 4 | tři záměny a jedno přidání |
| hodinky | holinky | 1 | jedna záměna |
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.