Levenshtein-távolság két sztring, általánosabban két szimbólumsorozat közötti szerkesztési távolság. A klasszikus definíció szerint annak a legkisebb számú egységköltségű szerkesztési műveletnek az összege, amellyel az egyik sorozat a másikba alakítható. Három alapművelet megengedett: egy szimbólum beszúrása, egy szimbólum törlése és egy szimbólum helyettesítése; mindegyik művelet költsége 1.
A távolság Vlagyimir Levenshtein szovjet matematikusról kapta a nevét, aki 1965-ben, törléseket, beszúrásokat és helyettesítéseket javító kódokról szóló munkájában vezette be a kapcsolódó fogalmat.V. I. Levenshtein: „Binary codes capable of correcting deletions, insertions, and reversals”, Soviet Physics Doklady, 10(8), 1966, 707–710. o. Az orosz eredeti 1965-ben jelent meg. A Levenshtein-távolság a szerkesztési távolságok egyik konkrét esete, nem az egész fogalomcsalád szinonimája. Alkalmazzák többek között közelítő karakterlánc-illesztésben, helyesírás-javításban, számítógépes nyelvészetben, fordítómemóriákban, dialektometriában és más sorozat-összehasonlítási feladatokban.Gonzalo Navarro: „A Guided Tour to Approximate String Matching”, ACM Computing Surveys, 33(1), 2001, 31–88. o. doi:10.1145/375360.375365.
A magyar szakirodalomban a „Levenshtein-távolság” elnevezés bevett. Tikk Domonkos és szerzőtársai Szövegbányászat című tankönyve a szerkesztési távolságon alapuló egyik legismertebb sztringmetrikaként tárgyalja, és ugyanazt a törlés–beszúrás–csere felbontást használja.Tikk Domonkos (szerk.): Szövegbányászat, Typotex Kiadó, Budapest, 2007, 76–77. o. .
Definíció Legyen és két sztring. Jelölje az első és a első szimbóluma által alkotott prefixek Levenshtein-távolságát. A peremfeltételek:
Ha és , akkor
ahol
Az első tag egy törlésnek, a második egy beszúrásnak, a harmadik pedig egyezésnek vagy helyettesítésnek felel meg. A két teljes sztring Levenshtein-távolsága .Robert A. Wagner és Michael J. Fischer: „The String-to-String Correction Problem”, Journal of the ACM, 21(1), 1974, 168–173. o. doi:10.1145/321796.321811.
A formális definíció nem követeli meg, hogy a sorozat elemei feltétlenül karakterek legyenek. A műveletek alkalmazhatók például szavak, morfológiai címkék vagy más diszkrét jelek sorozatára is, ha egyértelműen rögzített, mi számít egy beszúrásnak, törlésnek és helyettesítésnek. Ezért a módszer karakter-, szó- vagy más reprezentációs szinten is használható.Hodász Gábor: „Nyelvi hasonlóságon alapuló intelligens keresés fordítómemóriában”, II. Magyar Számítógépes Nyelvészeti Konferencia, Szeged, 2004, 108–116. o.
Példa Tikk Domonkos Szövegbányászat című könyvében a gyors és gyros szavak Levenshtein-távolsága 2. Egy optimális szerkesztési sorozat például:
gyors → gyrrs — a harmadik karaktert, o-t, r-re cseréljük; gyrrs → gyros — a negyedik karaktert, r-t, o-ra cseréljük.
A példa egyben azt is mutatja, hogy a klasszikus Levenshtein-modell nem tartalmaz külön „szomszédos felcserélés” műveletet. Ha az ilyen transzpozíciót egyetlen műveletként akarjuk számolni, másik szerkesztési modellt, például Damerau–Levenshtein-távolságot kell használni.
Dinamikus programozási algoritmus A Levenshtein-távolság klasszikus kiszámítási módja dinamikus programozáson alapul. Wagner és Fischer olyan táblázatos algoritmust írt le, amely a két sztring egyre hosszabb prefixeinek távolságait számolja ki, és minden részprobléma eredményét csak egyszer használja fel.
Egy egyszerű pszeudokód:
function LevenshteinDistance(a, b): m := length(a) n := length(b) create D[0..m, 0..n]
for i := 0..m: D[i, 0] := i for j := 0..n: D[0, j] := j
for i := 1..m: for j := 1..n: if a[i] = b[j]: cost := 0 else: cost := 1
D[i, j] := min( D[i-1, j] + 1, D[i, j-1] + 1, D[i-1, j-1] + cost )
return D[m, n]
A teljes mátrix megtartása esetén nemcsak a távolság számszerű értéke, hanem egy optimális szerkesztési út is visszafejthető. A jobb alsó cellából visszafelé haladva azok a megelőző cellák követhetők, amelyek az adott minimumot létrehozhatták. Ha több megelőző cella is ugyanazt az optimális értéket adja, több különböző, azonos költségű optimális szerkesztési sorozat is létezhet.
Idő- és tárkomplexitás A teljes dinamikus programozási táblázat kiszámítása időt igényel. Ha az egész táblázatot tároljuk, a tárigény szintén . Ha csak a távolság értékére van szükség, és nem kell rekonstruálni az optimális szerkesztési sort, elegendő az éppen szükséges sorokat megőrizni; így a memóriaigény -re csökkenthető.Esko Ukkonen: „Algorithms for approximate string matching”, Information and Control, 64(1–3), 1985, 100–118. o. doi:10.1016/S0019-9958(85)80046-2.
Ha előre ismert egy kicsi maximálisan elfogadható távolság, nem feltétlenül szükséges az egész mátrix kiszámítása. Ukkonen olyan algoritmusokat adott, amelyek a tényleges szerkesztési távolságot vagy egy megadott küszöböt használják fel a vizsgált tartomány szűkítésére.
Bitvektoros módszerek Közelítő mintaillesztésben a dinamikus programozási állapotok bitvektorokkal is reprezentálhatók. Gene Myers 1999-es algoritmusa a processzor gépi szavain belüli párhuzamos bitműveletekkel egyszerre több állapot frissítését teszi lehetővé, ami különösen rövidebb minták és kis hibaküszöb mellett hatékony.Gene Myers: „A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming”, Journal of the ACM, 46(3), 1999, 395–415. o. doi:10.1145/316542.316550. Ez nem változtatja meg a Levenshtein-távolság definícióját; a számítás reprezentációját és végrehajtását gyorsítja.
Levenshtein-automaták Adott minta és maximális távolság mellett véges automata is konstruálható, amely pontosan azokat a szavakat fogadja el, amelyek Levenshtein-távolsága a mintától legfeljebb . Schulz és Mihov ilyen Levenshtein-automatákat alkalmazott gyors szótári javításra és hibát tűrő karakterlánc-keresésre.Klaus U. Schulz és Stoyan Mihov: „Fast string correction with Levenshtein automata”, International Journal on Document Analysis and Recognition, 5(1), 2002, 67–85. o. doi:10.1007/s10032-002-0082-8.
Elméleti alsó korlátok Az általános, pontos szerkesztési távolság számításának ismert dinamikus programozási megoldása kvadratikus jellegű azonos nagyságrendű bemeneteknél. Backurs és Indyk feltételes alsó korlátot adott: ha a pontos edit distance valamely állandó mellett időben kiszámítható lenne, az ellentmondana az erős exponenciális idő hipotézisének (SETH).Arturs Backurs és Piotr Indyk: „Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH Is False)”, SIAM Journal on Computing, 47(3), 2018, 1087–1097. o. doi:10.1137/15M1053128.
Ez feltételes, nem pedig feltétel nélküli lehetetlenségi eredmény: nem zárja ki a gyorsabb algoritmusokat speciális bemenetekre, kis távolságra, közelítő számításra vagy más korlátozott modellekre.
Tulajdonságok Az egységköltségű klasszikus Levenshtein-távolság metrika. Nemnegatív, két sztring távolsága pontosan akkor 0, ha azonosak, szimmetrikus, és teljesíti a háromszög-egyenlőtlenséget.
Ha a két sztring hossza , illetve , akkor
Az alsó korlát abból adódik, hogy a hosszúságkülönbség megszüntetéséhez legalább beszúrás vagy törlés szükséges. A felső korlát elérhető megfelelő számú helyettesítéssel, majd a maradék karakterek beszúrásával vagy törlésével.
Kapcsolat a Hamming-távolsággal Azonos hosszúságú sztringeknél a Hamming-távolság a Levenshtein-távolság felső korlátja:
A két érték nem szükségképpen egyenlő. A Hamming-távolság a megfelelő pozíciók eltéréseit számolja, tehát csak helyettesítésekkel dolgozik, míg a Levenshtein-távolság beszúrásokat és törléseket is engedélyezhet olcsóbb szerkesztési útként.
Kapcsolat a leghosszabb közös részsorozattal Ha a helyettesítés nem megengedett, és csak beszúrásokat és törléseket használunk, akkor két, és hosszú sztring közötti szerkesztési költség
ahol a leghosszabb közös részsorozat hossza. A kapcsolat abból következik, hogy a közös részsorozaton kívüli elemeket az egyik oldalon törölni, a másikon beszúrni kell.
Súlyozott változatok és rokon távolságok A klasszikus Levenshtein-távolságban a beszúrás, törlés és helyettesítés költsége egységesen 1. Súlyozott szerkesztési távolság esetén a költségek függhetnek a művelet típusától vagy az érintett szimbólumoktól. Ilyen modell hasznos lehet például fonetikai összehasonlításban vagy olyan helyesírás-javításban, ahol bizonyos tévesztések valószínűbbek másoknál. Tetszőlegesen választott súlyok mellett azonban a klasszikus Levenshtein-távolság minden metrikus tulajdonsága nem feltétlenül marad meg.
A Damerau–Levenshtein-távolság olyan rokon szerkesztési modell, amely a beszúrás, törlés és helyettesítés mellett két szomszédos szimbólum felcserélését is egyetlen műveletként engedi. Emiatt nem azonos a klasszikus Levenshtein-távolsággal.
Alkalmazások Helyesírás-javítás és közelítő keresés Helyesírás-javításban egy ismeretlen vagy hibásan leírt szót össze lehet vetni egy szótár elemeivel, és a kis Levenshtein-távolságú alakokat javítási jelöltként lehet kezelni. Önmagában a távolság nem mondja meg, melyik jelölt a nyelvileg legvalószínűbb; gyakorlati rendszerekben ezért gyakorisági, morfológiai, fonetikai vagy kontextuális információval kombinálható.
Közelítő keresésben egy lekérdezéshez azokat a sztringeket lehet megtalálni, amelyek távolsága egy adott küszöb alatt marad. Ez lehetővé teszi kisebb gépelési hibák, hiányzó vagy többletkarakterek tolerálását.
Fordítómemóriák magyar nyelvi feldolgozásban Hodász Gábor a 2004-es Magyar Számítógépes Nyelvészeti Konferencián olyan intelligens keresési módszert mutatott be fordítómemóriákhoz, amely több nyelvi szinten Levenshtein-távolságra építette a hasonlóság mérését. A rendszer három párhuzamos reprezentációt használt: a szavak felszíni alakját, tövesített alakját és szófaji címkéjét. Két mondat hasonlóságát így nem egyetlen karakterlánc-távolság, hanem három, különböző nyelvi szinteken számított távolság együtt írta le.
Ez a megközelítés jól szemlélteti, hogy a Levenshtein-elv a karaktereken túl más szimbólumsorozatokra is alkalmazható. A távolság ebben az esetben a fordítómemória keresési komponense, nem önmagában teljes fordítási modell.
Magyar nyelvjárások dialektometriája A Levenshtein-algoritmust magyar dialektometriai kutatásokban is használják nyelvjárási adatok automatikus összehasonlítására. Az Akadémiai Kiadó 2023-as Általános Nyelvészeti Tanulmányok XXXIV. kötetének dialektometriai fejezete a módszer alapjaként Levenshtein karakterlánc-összehasonlító algoritmusát jelöli meg, és a magyar nyelvatlasz-adatokból nyelvi hasonlósági mátrixokat képez vele.Mády Katalin és Markó Alexandra (szerk.): „Dialektometria”, Általános Nyelvészeti Tanulmányok XXXIV. – Fonetikai tanulmányok, Akadémiai Kiadó, 2023. doi:10.1556/9789634548645.
A módszertani részben a magánhangzók és mássalhangzók hatását külön is vizsgálják: az adatokat úgy alakítják át, hogy az összehasonlításban csak a vokalizmus, illetve csak a konszonantizmus maradjon meg, majd a Levenshtein-algoritmussal külön hasonlósági mátrix készül.Mády Katalin és Markó Alexandra (szerk.): „Anyag és módszer”, Általános Nyelvészeti Tanulmányok XXXIV. – Fonetikai tanulmányok, Akadémiai Kiadó, 2023. doi:10.1556/9789634548645. A meggy címszó különböző nyelvjárási változatainál például külön értékelhető a magánhangzók és a szóvégi mássalhangzók térbeli változatossága.
A Bihalbocs magyar dialektológiai keretrendszerben a módszer nyelvatlaszok informatizált adatainak páronkénti összehasonlítására és a hasonlósági eredmények térképezésére is használható.
Magyar beszédfelismerő és diktálórendszerek értékelése