Odległość Levenshteina
Z Wikipedii
Odległość Levenshteina, zwana też odległością edycyjną – miara odmienności napisów (skończonych ciągów znaków), zaproponowana w 1965 roku przez Vladimira Levenshteina.
Formalnie jest to metryka w przestrzeni ciągów znaków, zdefiniowana następująco:
-
- działaniem prostym na napisie nazwiemy:
- wstawienie nowego znaku do napisu
- usunięcie znaku z napisu
- zamianę znaku w napisie na inny znak
- odległością pomiędzy dwoma napisami jest najmniejsza liczba działań prostych, przeprowadzających jeden napis na drugi.
- działaniem prostym na napisie nazwiemy:
Miara ta znajduje zastosowanie w przetwarzaniu informacji, danych w postaci ciągów symboli: w maszynowym rozpoznawaniu mowy, analizie DNA, rozpoznawaniu plagiatów, korekcie pisowni (np. wyszukiwanie w spisie telefonicznym błędnie podanego nazwiska), itp.
Przykłady
Odległość Levenshteina pomiędzy napisami identycznymi, np.
pies pies
jest zerowa – skoro są identyczne, to potrzeba zero działań, by jeden z nich przeprowadzić na drugi.
Odległość Levenshteina pomiędzy napisami:
granat granit
wynosi 1, ponieważ do przeprowadzenia pierwszego na drugi wystarcza jedno działanie: zamiana litery a na i.
Odległość pomiędzy napisami:
orczyk oracz
równa jest 3, ponieważ do przeprowadzenia pierwszego napisu na drugi potrzeba trzech działań: usunięcia liter y i k oraz wstawienia litery a.
Odległość pomiędzy napisami:
marka ariada
wynosi 4, ponieważ potrzeba co najmniej czterech działań, np.: usunięcia litery m, zamiany k na i oraz dodania d i a.
Odległość Levenshteina jest uogólnieniem odległości Hamminga; sama też ma swoje uogólnienia, oparte na rozszerzaniu zestawu działań uważanych za proste. Podstawowym rozszerzeniem jest uznanie za działanie proste zamiany miejscami dwu sąsiednich znaków. Innym spotykanym jest dopuszczenie wstawiania, usuwania i zastępowania spójnych ciągów znaków (bloków, nieprzerwanych fragmentów napisu). Jest to szczególnie pożyteczne przy przetwarzaniu ciągów danych o wyróżnionych mniejszych fragmentach, jak wyrazy w zdaniu.
Tak zdefiniowane miary nazywa się odległością transformacyjną, jednak czasem są również nazywane odległościami edycyjnymi. Z tego powodu użycie określenia odległość edycyjna należy zawsze uściślić, podając na jakim zestawie działań opiera się używana miara.
