Levenštejnova vzdálenost je metrika pro měření rozdílu mezi dvěma textovými řetězci nebo obecněji mezi dvěma konečnými posloupnostmi symbolů. V klasické definici je rovna nejmenšímu počtu jednoznakových operací vložení, smazání a záměny, které jsou nutné k převedení jedné posloupnosti na druhou; každá z těchto operací má cenu 1.V. I. Levenshtein: “Binary codes capable of correcting deletions, insertions, and reversals”. Doklady Akademii Nauk SSSR, 163(4), 845–848, 1965; anglický překlad Soviet Physics Doklady, 10(8), 707–710, 1966. Math-Net.
Vzdálenost je pojmenována po sovětském matematikovi Vladimiru Iosifoviči Levenštejnovi, který ji zavedl v roce 1965 v souvislosti s kódy opravujícími chyby vznikající vkládáním a mazáním symbolů. Levenštejnova vzdálenost je klasickým typem editační vzdálenosti. Pojem editační vzdálenost je však širší a zahrnuje i modely s jinou množinou povolených operací nebo s různými cenami jednotlivých operací.Gonzalo Navarro: “A guided tour to approximate string matching”. ACM Computing Surveys, 33(1), 31–88, 2001. doi:10.1145/375360.375365.
Levenštejnova vzdálenost se používá mimo jiné při opravě překlepů, přibližném vyhledávání, zpracování přirozeného jazyka, porovnávání jmen a záznamů, vyhodnocování rozpoznávání textu a řeči a při porovnávání biologických sekvencí.
Definice Nechť
a
jsou dvě posloupnosti. Označme Levenštejnovu vzdálenost mezi prefixem a prefixem .
Pro prázdnou posloupnost platí okrajové podmínky
Pro a potom platí
kde
Jednotlivé členy odpovídají smazání symbolu ze zdrojové posloupnosti, vložení symbolu z cílové posloupnosti a shodě nebo záměně posledního symbolu obou prefixů.Robert A. Wagner, Michael J. Fischer: “The String-to-String Correction Problem”. Journal of the ACM, 21(1), 168–173, 1974. doi:10.1145/321796.321811.
Výsledná vzdálenost celých posloupností je .
Příklady Několik jednoduchých příkladů:
Řetězec 1 Řetězec 2 Vzdálenost Jedna možná interpretace aaa abc 2 dvě záměny aaa aaaa 1 jedno vložení hodinky holinky 1 jedna záměna
Klasickým příkladem je také kitten → sitting. Převod lze provést dvěma záměnami a jedním vložením, takže
Vlastnosti a meze Při jednotkových cenách vložení, smazání a záměny je Levenštejnova vzdálenost metrikou: je nezáporná, je nulová právě tehdy, když jsou obě posloupnosti stejné, je symetrická a splňuje trojúhelníkovou nerovnost.
Pro posloupnosti délek a platí
Dolní mez plyne z toho, že jediná operace vložení nebo smazání změní délku nejvýše o jedna. Horní mez lze získat záměnami ve společné části řetězců a následným vložením nebo smazáním zbývajících symbolů.
Mají-li oba řetězce stejnou délku, je Hammingova vzdálenost horní mezí Levenštejnovy vzdálenosti:
Rovnost nemusí platit, protože Levenštejnova vzdálenost na rozdíl od Hammingovy připouští také vložení a smazání.
Jestliže se záměna nepovolí a lze používat pouze vložení a smazání, je minimální počet operací
kde je délka nejdelší společné podposloupnosti. Tato rovnost neplatí beze změny pro klasickou Levenštejnovu vzdálenost, protože jedna záměna v ní stojí 1, zatímco smazání následované vložením stojí 2.
Výpočet
Dynamické programování Naivní rekurzivní výpočet opakovaně řeší stejné podproblémy a může mít exponenciální časovou složitost. Standardní efektivní řešení proto používá dynamické programování. V matici rozměru se ukládají vzdálenosti mezi všemi dvojicemi prefixů.
funkce LevenstejnovaVzdalenost(s[1..m], t[1..n]): vytvoř d[0..m, 0..n]
pro i = 0..m: d[i,0] = i
pro j = 0..n: d[0,j] = j
pro i = 1..m: pro j = 1..n: pokud s[i] = t[j]: cena = 0 jinak: cena = 1
d[i,j] = minimum( d[i-1,j] + 1, // smazání s[i] d[i,j-1] + 1, // vložení t[j] d[i-1,j-1] + cena // shoda nebo záměna )
vrať d[m,n]
Buňka d[i,j] tedy vždy představuje minimální cenu převodu prvních i symbolů řetězce s na prvních j symbolů řetězce t.
Vyplnění celé matice vyžaduje čas a paměť .
Úspora paměti Je-li zapotřebí pouze hodnota vzdálenosti, není nutné uchovávat celou matici. Pro výpočet nové řádky postačuje předchozí řádka a již spočtená část řádky aktuální. Pokud se jako uložený rozměr použije kratší z řetězců, lze pracovní paměť snížit na .Esko Ukkonen: “Algorithms for approximate string matching”. Information and Control, 64(1–3), 100–118, 1985. doi:10.1016/S0019-9958(85)80046-2.
Rekonstrukce editačních operací Při zachování celé matice lze zpětným průchodem od rekonstruovat jednu optimální posloupnost operací. Pokud stejné minimum poskytuje více předchůdců, může pro stejnou dvojici řetězců existovat více různých optimálních editačních cest se stejnou celkovou cenou.
Algoritmy závislé na vzdálenosti Je-li skutečná editační vzdálenost malá vzhledem k délkám řetězců nebo je-li předem určen maximální přípustný práh, není vždy nutné vyplňovat celou matici. Ukkonen popsal přesné algoritmy, které omezují výpočet na relevantní pás matice a jejichž náročnost závisí na skutečné nebo povolené vzdálenosti.
Pojem approximate string matching v tomto kontextu znamená vyhledávání s povolenými odchylkami; neznamená nutně, že samotná hodnota vzdálenosti je pouze aproximována.
Bitově paralelní metody Gene Myers v roce 1999 popsal bitově vektorový algoritmus pro přibližné porovnávání vzorů. Více stavů dynamického programování je v něm reprezentováno současně bity strojového slova a aktualizováno bitovými operacemi.Gene Myers: “A fast bit-vector algorithm for approximate string matching based on dynamic programming”. Journal of the ACM, 46(3), 395–415, 1999. doi:10.1145/316542.316550.
Varianty a příbuzné míry
Vážená editační vzdálenost Ve vážené editační vzdálenosti mohou mít vložení, smazání a záměny různé ceny a cena záměny může záviset na konkrétní dvojici symbolů. Libovolná volba cen automaticky nezaručuje všechny vlastnosti metriky; například asymetrické ceny mohou porušit symetrii.
Damerauova–Levenštejnova vzdálenost rozšiřuje základní operace také o transpozici dvou sousedních symbolů.
= Normalizace
Protože nezpracovaná vzdálenost může s délkou řetězců růst, používají některé aplikace normalizované varianty. Neexistuje však jediná univerzální definice „normalizované Levenštejnovy vzdálenosti“.
Jednou z jednoduchých možností je
a odpovídající podobnost lze například vyjádřit jako
Jiné normalizace mohou mít jiné matematické vlastnosti; použitou definici je proto nutné uvést spolu s výsledkem.
Použití
Kontrola pravopisu a doplňování diakritiky v češtině Levenštejnova a obecnější editační vzdálenost se používají při vytváření kandidátů pro opravu překlepů. Český systém Korektor vyvinutý na Ústavu formální a aplikované lingvistiky Matematicko-fyzikální fakulty Univerzity Karlovy kombinuje kandidátní model, chybový model a jazykové modely a byl navržen pro kontextovou kontrolu pravopisu a doplňování diakritiky v češtině.Michal Richter, Pavel Straňák, Alexandr Rosen: “Korektor – A System for Contextual Spell-Checking and Diacritics Completion”. Proceedings of COLING 2012: Posters, 1019–1028, 2012. ACL Anthology.
Dokumentace českého modelu Korektoru omezuje vyhledávání kandidátů maximální editační vzdáleností a umožňuje samostatně nastavit operace záměny, vložení, smazání, změny velikosti písmen a prohození sousedních znaků. Při čistém doplňování či odstraňování diakritiky může mít taková operace v kandidátním modelu editační vzdálenost 0.ÚFAL MFF UK: “Korektor Model Creation”. Ústav formální a aplikované lingvistiky.
Tento příklad zároveň ukazuje, že samotná vzdálenost znaků neurčuje správnou opravu: mezi více kandidáty rozhodují také slovník, morfologie a kontextový jazykový model.
Jazykové porovnávání a slovanské jazyky V jazykových aplikacích lze cenu záměn upravit podle fonetických nebo pravopisných vztahů mezi jazyky. Feldmanová, Hana a Brew použili normalizovanou editační vzdálenost při automatickém hledání českých a ruských kognátů pro přenos morfologické anotace. Náklady záměn přitom upravovali podle známých česko-ruských foneticko-pravopisných vztahů, například vztahu českého h k ruskému g nebo rozdílného značení délky samohlásek.Anna Feldman, Jirka Hana, Chris Brew: “Experiments in Cross-Language Morphological Annotation Transfer”. In: Computational Linguistics and Intelligent Text Processing, LNCS 3878, 41–50, Springer, 2006. doi:10.1007/11671299_4.
Podobný princip se používá i při vytváření hrubých česko-ruských slovníků ve výuce výpočetní morfologie na ÚFAL, kde se ceny editací přizpůsobují vlastnostem češtiny a ruštiny.ÚFAL MFF UK: “HW2 – Edit distance”, kurz Computational Morphology. výukový materiál.
Takové vážení není součástí klasické jednotkové Levenštejnovy vzdálenosti; jde o jazykově přizpůsobenou variantu editační vzdálenosti.
Rozpoznávání české řeči Editační vzdálenost se používá také při hodnocení systémů rozpoznávání řeči. Ve výuce hlubokého učení na ÚFAL se úloha rozpoznávání české řeči nad českou částí datasetu Common Voice hodnotí normalizovanou editační vzdáleností mezi předpovězenou a referenční posloupností písmen.ÚFAL MFF UK: “Deep Learning – Summer 2024/25”, úloha rozpoznávání české řeči. ÚFAL.
Taková normalizovaná chybová míra je odvozena z editačního zarovnání, není však totožná s původní symetrickou funkcí Levenštejnovy vzdálenosti bez normalizace.
Přibližné vyhledávání V rozsáhlých slovnících a textových kolekcích může být Levenštejnova vzdálenost použita k hledání řetězců, které se od dotazu liší malým počtem úprav. V praxi se často kombinuje s filtry, indexy, q-gramy nebo jinými metodami, aby nebylo nutné počítat plnou vzdálenost ke každému kandidátu.
Bioinformatika V bioinformatice je editační vzdálenost úzce spojena s porovnáváním a zarovnáváním biologických sekvencí. Vložení, smazání a záměny představují jednoduchý model rozdílů mezi sekvencemi DNA nebo proteinů, ale praktické algoritmy zarovnání zpravidla používají bohatší substituční matice a penalizace mezer než klasická Levenštejnova vzdálenost s jednotkovými cenami.Bonnie Berger, Michael S. Waterman, Yun William Yu: “Levenshtein Distance, Sequence Comparison and Biological Database Search”. IEEE Transactions on Information Theory, 67(6), 3287–3294, 2021. doi:10.1109/TIT.2020.2996543.
Unicode a jednotka porovnání Matematická definice pracuje s posloupnostmi symbolů a sama neurčuje, co má program považovat za jeden „znak“. U textu v Unicode lze porovnávat například bajty, kódové jednotky, kódové body Unicode nebo rozšířené grafémové klastry. Tyto volby mohou vést k různým hodnotám vzdálenosti.
To je významné i pro češtinu. Například znak č (U+010D) má kanonický rozklad na c (U+0063) a kombinující háček U+030C; obdobně lze kanonicky rozložit řadu dalších českých písmen s diakritikou.Unicode Consortium: “Latin Extended-A”. Unicode.
Unicode Standard Annex #15 definuje normalizační formy NFC, NFD, NFKC a NFKD pro práci s kanonicky a kompatibilně ekvivalentními reprezentacemi.Unicode Consortium: “Unicode Standard Annex #15: Unicode Normalization Forms”. Unicode. Unicode Standard Annex #29 definuje extended grapheme clusters jako algoritmickou aproximaci znaků vnímaných uživatelem.Unicode Consortium: “Unicode Standard Annex #29: Unicode Text Segmentation”. Unicode.
Normalizace Unicode není totéž jako odstranění české diakritiky. Převod č na c, ř na r nebo ě na e je jazykově či aplikačně definovaná transformace, nikoli standardní kanonická normalizace. Aplikace proto musí uvést, jaká jednotka porovnání a jaké předzpracování byly použity.
Omezení Levenštejnova vzdálenost měří minimální cenu editace, nikoli významovou podobnost. Dvě významově nesouvisející slova mohou mít malou znakovou vzdálenost, zatímco synonyma mohou být pravopisně zcela odlišná.
Klasická varianta navíc dává všem záměnám stejnou cenu. Sama tedy nezohledňuje fonetickou podobnost, morfologii, slovotvorné vztahy, četnost slov ani kontext. Český Korektor proto kombinuje editaci s morfologickými a jazykovými modely, zatímco česko-ruské experimenty používají jazykově specifické vážené náklady.