Levenshteini kaugus

Levenshteini kaugus ehk Levenshteini teisenduskaugus on kahe sõne vaheline teisenduskaugus, mis näitab vähimat arvu üksikuid redigeerimistoiminguid, millega saab ühe sõne teiseks muuta. Klassikalises Levenshteini kauguses on lubatud ühe sümboli lisamine, kustutamine ja asendamine teise sümboliga ning iga toimingu maksumus on 1.^[1]

Mõõdik on nimetatud Nõukogude Liidu matemaatiku Vladimir Levenshteini järgi, kes kirjeldas seda tüüpi kaugust 1965. aastal veaparanduskoodide kontekstis.^[2] Levenshteini kaugust kasutatakse muu hulgas õigekirja automaatses parandamises, ligikaudses sõnevastenduses, tekstide normaliseerimises ja teistes loomuliku keele töötluse ülesannetes.^[3]

Definitsioon

Olgu $a=a_{1}a_{2}\ldots a_{m}$ ja $b=b_{1}b_{2}\ldots b_{n}$ kaks sõne. Tähistagu $D(i,j)$ Levenshteini kaugust sõne $a$ esimese $i$ sümboli ja sõne $b$ esimese $j$ sümboli vahel. Ääretingimused on

D(i,0)=i

D(0,j)=j.

Kui $i>0$ ja $j>0$ , siis

D(i,j)=\min {\begin{cases}D(i-1,j)+1,\\D(i,j-1)+1,\\D(i-1,j-1)+c(i,j),\end{cases}}

kus

c(i,j)={\begin{cases}0,&a_{i}=b_{j},\\1,&a_{i}\neq b_{j}.\end{cases}}

Kolm võimalust vastavad vastavalt kustutamisele, lisamisele ning kas sümbolite kokkulangevusele või asendamisele. Kahe täieliku sõne Levenshteini kaugus on $D(m,n)$ .^[4]

Näide

Sõnede maru ja karud Levenshteini kaugus on 2. Üks optimaalne teisendusjada on

maru → karu – m asendatakse tähega k;
karu → karud – lõppu lisatakse d.

Vähem kui kahe klassikalise redigeerimistoiminguga ei ole võimalik esimest sõne teiseks muuta.

Arvutamine ja keerukus

Levenshteini kaugust arvutatakse tavaliselt dünaamilise programmeerimisega. Wagneri–Fischeri meetodis täidetakse $(m+1)\times (n+1)$ tabel, kus iga lahter sõltub vasakpoolsest, ülemisest ja vasakust ülemisest lahtrist.^[4]

Lihtsustatud pseudokood on järgmine:

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]

Täieliku tabeli arvutamise ajakeerukus on $\Theta (mn)$ .^[1]^[4] Kui kogu tabel säilitatakse, on mälukasutus $\Theta (mn)$ . Kui vaja on ainult kauguse väärtust, mitte optimaalset redigeerimisjada, saab mälukasutuse vähendada väärtuseni $O(\min(m,n))$ , säilitades korraga ainult arvutuseks vajalikud read.^[5]

Kui otsitavale kaugusele on teada väike ülempiir, ei ole alati vaja kogu tabelit arvutada. Ukkonen kirjeldas algoritme, mille aja- ja mälukasutus võib sõltuda tegelikust redigeerimiskaugusest või etteantud lävest.^[5]

Omadused

Klassikaliste ühikkulude korral on Levenshteini kaugus meetrika: see on mittenegatiivne ja sümmeetriline, võrdub nulliga parajasti identsete sõnede korral ning rahuldab kolmnurga võrratust.^[3]

Kui sõnede pikkused on $m$ ja $n$ , siis kehtib

|m-n|\leq d_{L}(a,b)\leq \max(m,n).

Alumine piir tuleneb sellest, et pikkuste erinevuse tasandamiseks on vaja vähemalt $|m-n|$ lisamist või kustutamist. Ülemise piiri saab saavutada, asendades esmalt vajalikud sümbolid ning seejärel lisades või kustutades ülejäänud sümbolid.

Kui sõned on ühepikkused, on Hammingu kaugus Levenshteini kauguse ülempiir:

d_{L}(a,b)\leq d_{H}(a,b).

Võrdus ei kehti üldjuhul. Hammingu kaugus loendab erinevaid positsioone ja vastab olukorrale, kus kasutatakse ainult asendamisi, samal ajal kui Levenshteini kaugus lubab ka lisamisi ja kustutamisi.^[3]

Kaalutud kaugus ja seotud mõõdikud

Klassikalises Levenshteini kauguses maksavad kõik lisamised, kustutamised ja asendamised ühe ühiku. Kaalutud teisenduskauguses võib toimingu maksumus sõltuda toimingu liigist või muudetavatest sümbolitest. Selline lähenemine on kasulik näiteks keelerakendustes, kus teatud kirjapildi- või häälikumuutusi peetakse teistest tõenäolisemaks. Suvaliselt valitud kaalud ei pruugi säilitada kõiki klassikalise Levenshteini kauguse meetrilisi omadusi.

Damerau–Levenshteini kaugus on seotud mõõdik, mis lubab lisaks kahe kõrvuti asuva sümboli transpositsiooni ühe redigeerimistoiminguna. Seetõttu ei ole see sama mõõdik mis klassikaline Levenshteini kaugus, mille põhioperatsioonid on lisamine, kustutamine ja asendamine.^[3]

Kasutusalad

Õigekirja kontroll ja ligikaudne vastendus

Õigekirja kontrollis saab tundmatut või vigaselt kirjutatud sõna võrrelda sõnastiku sõnadega ning eelistada väikese teisenduskaugusega kandidaate. Levenshteini kaugus üksi ei määra siiski alati keeleliselt parimat parandust, sest sama väikese kaugusega võib leiduda mitu erinevat kandidaati. Seetõttu kombineeritakse praktilistes süsteemides teisenduskaugust sageli sageduse, konteksti või morfoloogilise teabega.^[3]

Ligikaudses vastenduses saab sama põhimõtte abil leida sõnesid, mis erinevad päringust kuni etteantud arvu redigeerimistoimingute võrra.^[5]

Eesti ajalooliste tekstide normaliseerimine

Levenshteini teisenduskaugust on kasutatud Eesti ajalooliste tekstide normaliseerimise uurimisel. Gerth Jaanimäe kirjeldas 2021. aastal Eesti Rakenduslingvistika Ühingu aastaraamatus Levenshteini teisenduskaugust ühe meetodina 19. sajandi eestikeelsete tekstide vanade kirjapiltide sidumiseks tänapäevaste vormidega.^[6]

Näiteks on ajaloolise vormi pesnu ja tänapäevasema vormi peksnud teisenduskaugus 2, sest lisada tuleb tähed k ja d. Uurimus toob esile ka meetodi piirangu: ühele vanale sõnavormile võib leiduda mitu sama kaugusega tänapäevast vastet. Selliste erinevuste modelleerimiseks saab kasutada kaalutud teisenduskaugust, kus ajalooliselt või keeleliselt tõenäolistele muutustele antakse väiksem kaal.^[6]

OCR-tekstide parandused DIGARis

Eesti Rahvusraamatukogu Digilabi OCR-tekstiparanduste andmestikus kasutatakse suhtelist Levenshteini kaugust ühe kriteeriumina algse OCR-teksti ja kasutaja parandatud teksti paaride filtreerimisel. Andmestik põhineb DIGARi ühisloome käigus tehtud parandustel; Digilabi kirjelduse järgi on ligi 500 kasutajat parandanud kokku üle 800 000 tekstirea.^[7]

Andmestikku kaasatavate paaride puhul peab parandatud tekst muu hulgas sisaldama vähemalt 80% tähestikulisi tähemärke, teksti pikkuste erinevus ei tohi ületada 5% ning kahe teksti suhteline Levenshteini kaugus peab olema vähemalt 0,1.^[7] Selles kasutuses ei ole kaugus lõplik kvaliteedihinnang, vaid osa andmete eeltöötlusest ja filtreerimisest.

Kirjete vastendamine Eesti avalikus sektoris

Levenshteini kaugust on käsitletud ka Eesti avaliku sektori kirjete vastendamise lahendustes. Siseministeeriumi tellitud 2023. aasta analüüsi järgi sisaldas üks varasem lahendusvisioon esmalt täpse vaste otsimist ning seejärel sarnase vaste otsimist Levenshteini kauguse ja kattuvuslävendi abil.^[8]

Sama analüüs rõhutab meetodi piirangut: Levenshteini kaugus mõõdab tekstilise esituse erinevust, kuid ei arvesta erinevuse semantikat. Seetõttu on kirjete vastendamisel vaja kasutada seda koos teiste tunnuste ja otsustusreeglitega.^[8]

Unicode ja võrdlusühik

Levenshteini kaugus on defineeritud sümbolijadadele, mistõttu sõltub tarkvaras saadud tulemus sellest, mida käsitletakse ühe sümbolina. Unicode-tekstis võib sama kasutaja tajutav märk olla esitatud ühe koodipunktina või mitme koodipunkti kanoniliselt ekvivalentse jadana.

Näiteks eesti täht õ võib olla esitatud eelkoostatud märgina või tähe o ja kombineeriva tilde jadana. Unicode'i normaliseerimisvormid NFC ja NFD võimaldavad kanoniliselt ekvivalentseid tekstijadasid ühtlustada.^[9]

Kui Levenshteini kaugus arvutatakse otse koodipunktidest ilma ühesuguse normaliseerimiseta, võivad kanoniliselt ekvivalentsed sõned saada ootamatult nullist erineva kauguse. Kui rakenduse jaoks on oluline kasutaja tajutav kirjamärk, võib võrdlusühikuna olla sobivam kasutada grafeemiklastreid kui üksikuid koodipunkte.^[10]

Vaata ka

Viited

1 2 Paul E. Black (toim.): "Levenshtein distance", Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology. Uuendatud 15. mail 2019. Vaadatud 10. septembril 2026.
↑ V. I. Levenshtein: "Binary codes capable of correcting deletions, insertions, and reversals", Soviet Physics Doklady, 10(8), 1966, lk 707–710. Venekeelne originaal ilmus 1965. aastal.
1 2 3 4 5 Gonzalo Navarro: "A Guided Tour to Approximate String Matching", ACM Computing Surveys, 33(1), 2001, lk 31–88. doi:10.1145/375360.375365.
1 2 3 Robert A. Wagner ja Michael J. Fischer: "The String-to-String Correction Problem", Journal of the ACM, 21(1), 1974, lk 168–173. doi:10.1145/321796.321811.
1 2 3 Esko Ukkonen: "Algorithms for approximate string matching", Information and Control, 64(1–3), 1985, lk 100–118. doi:10.1016/S0019-9958(85)80046-2.
1 2 Gerth Jaanimäe: "Ajalooliste tekstide normaliseerimine", Eesti Rakenduslingvistika Ühingu aastaraamat / Estonian Papers in Applied Linguistics, 17, 2021, lk 47–59. doi:10.5128/ERYa17.03.
1 2 Eesti Rahvusraamatukogu Digilab: "OCR tekstiparandused". Vaadatud 10. septembril 2026.
1 2 Gofore: "Eesti isikukoodita inimestele isikukoodi väljastamise lahenduse äri- ja detailanalüüsi lõpparuanne", Siseministeerium, 16. detsember 2023, lk 75.
↑ Unicode Consortium: "Unicode Standard Annex #15: Unicode Normalization Forms". Vaadatud 10. septembril 2026.
↑ Unicode Consortium: "Unicode Standard Annex #29: Unicode Text Segmentation". Vaadatud 10. septembril 2026.

Välislingid

[NIST-1] 1 2 Paul E. Black (toim.): "Levenshtein distance", Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology. Uuendatud 15. mail 2019. Vaadatud 10. septembril 2026.

[Levenshtein-2] V. I. Levenshtein: "Binary codes capable of correcting deletions, insertions, and reversals", Soviet Physics Doklady, 10(8), 1966, lk 707–710. Venekeelne originaal ilmus 1965. aastal.

[Navarro-3] 1 2 3 4 5 Gonzalo Navarro: "A Guided Tour to Approximate String Matching", ACM Computing Surveys, 33(1), 2001, lk 31–88. doi:10.1145/375360.375365.

[WagnerFischer-4] 1 2 3 Robert A. Wagner ja Michael J. Fischer: "The String-to-String Correction Problem", Journal of the ACM, 21(1), 1974, lk 168–173. doi:10.1145/321796.321811.

[Ukkonen-5] 1 2 3 Esko Ukkonen: "Algorithms for approximate string matching", Information and Control, 64(1–3), 1985, lk 100–118. doi:10.1016/S0019-9958(85)80046-2.

[Jaanimae-6] 1 2 Gerth Jaanimäe: "Ajalooliste tekstide normaliseerimine", Eesti Rakenduslingvistika Ühingu aastaraamat / Estonian Papers in Applied Linguistics, 17, 2021, lk 47–59. doi:10.5128/ERYa17.03.

[DIGAR-7] 1 2 Eesti Rahvusraamatukogu Digilab: "OCR tekstiparandused". Vaadatud 10. septembril 2026.

[Sisemin-8] 1 2 Gofore: "Eesti isikukoodita inimestele isikukoodi väljastamise lahenduse äri- ja detailanalüüsi lõpparuanne", Siseministeerium, 16. detsember 2023, lk 75.

[UAX15-9] Unicode Consortium: "Unicode Standard Annex #15: Unicode Normalization Forms". Vaadatud 10. septembril 2026.

[UAX29-10] Unicode Consortium: "Unicode Standard Annex #29: Unicode Text Segmentation". Vaadatud 10. septembril 2026.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]