Levenšteinin etäisyys on kahden merkkijonon välinen editointietäisyys eli mitta sille, kuinka monta yksittäistä muokkausoperaatiota vähintään tarvitaan toisen merkkijonon muuttamiseksi toiseksi. Klassisessa Levenšteinin etäisyydessä sallittuja operaatioita ovat yhden merkin lisääminen, poistaminen ja korvaaminen toisella merkillä, ja jokaisen operaation kustannus on 1.Paul E. Black (toim.): Levenshtein distance, Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology. Päivitetty 15.5.2019. Viitattu 10.9.2026.Ari Mustonen: Pääosin ohjaamaton sanaston poiminta rakenteettomasta tekstistä. Diplomityö, Oulun yliopisto, tietotekniikan osasto, 2014.
Etäisyys on nimetty neuvostoliittolaisen matemaatikon Vladimir Levenšteinin mukaan. Levenštein esitti vuonna 1965 kooditeoriaa käsittelevässä työssään etäisyyskäsitteen, joka ottaa huomioon symbolien poistot, lisäykset ja korvaukset.V. I. Levenshtein: Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady 10(8), 1966, s. 707–710. Venäjänkielinen alkuperäisjulkaisu 1965.
Levenšteinin etäisyyttä käytetään esimerkiksi oikeinkirjoituksen tarkistuksessa, likimääräisessä merkkijonohaussa, tekstin normalisoinnissa ja kieliteknologiassa. Se on yksi editointietäisyyksien perusmalleista; kaikki editointietäisyydet eivät kuitenkaan ole Levenšteinin etäisyyksiä.
Määritelmä Olkoon ja kaksi merkkijonoa. Merkitään :llä etäisyyttä merkkijonojen ja pituuksien ja prefiksien välillä. Reunaehdot ovat
Kun ja ,
missä
Ensimmäinen vaihtoehto vastaa merkin poistamista, toinen merkin lisäämistä ja kolmas joko saman merkin säilyttämistä tai merkin korvaamista toisella. Levenšteinin etäisyys on lopulta .Robert A. Wagner ja Michael J. Fischer: The String-to-String Correction Problem. Journal of the ACM 21(1), 1974, s. 168–173. doi:10.1145/321796.321811.
Esimerkki Merkkijonojen urheilija ja murheilta välinen Levenšteinin etäisyys on 3. Yksi optimaalinen muokkausjono on
urheilija murheilija – lisätään alkuun m murheilia – poistetaan j murheilta – korvataan toiseksi viimeinen i merkillä t.
Kolmea operaatiota vähemmällä muunnosta ei voida tehdä.
Algoritmi ja kompleksisuus Levenšteinin etäisyys voidaan laskea dynaamisella ohjelmoinnilla. Tavallinen Wagner–Fischer-menetelmä täyttää -kokoisen taulukon siten, että jokainen solu riippuu vain vasemmanpuoleisesta, yläpuolisesta ja vasemman yläkulman solusta.
Yksinkertainen pseudokoodi on seuraava:
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äyden taulukon laskeminen vie aikaa ja muistia . Jos tarvitaan vain etäisyyden arvo eikä itse muokkausjonoa, riittää säilyttää kerrallaan vain tarvittavat taulukon rivit. Tällöin muistin tarve voidaan pienentää arvoon .
Kun hyväksyttävälle etäisyydelle tunnetaan pieni yläraja, koko taulukkoa ei aina tarvitse laskea. Ukkonen esitti algoritmeja, jotka hyödyntävät tällaista rajaa likimääräisessä merkkijonohaussa.Esko Ukkonen: Algorithms for approximate string matching. Information and Control 64(1–3), 1985, s. 100–118. doi:10.1016/S0019-9958(85)80046-2.
Ominaisuuksia Klassisilla yksikkökustannuksilla Levenšteinin etäisyys on metriikka. Se on ei-negatiivinen ja symmetrinen, saa arvon nolla täsmälleen silloin kun merkkijonot ovat samat ja toteuttaa kolmioepäyhtälön.Gonzalo Navarro: A Guided Tour to Approximate String Matching. ACM Computing Surveys 33(1), 2001, s. 31–88. doi:10.1145/375360.375365.
Jos merkkijonojen pituudet ovat ja , niin
Alaraja johtuu siitä, että pituusero on poistettava vähintään lisäyksillä tai poistoilla. Yläraja saadaan esimerkiksi korvaamalla ensin mahdollisimman monta merkkiä ja lisäämällä tai poistamalla loput.
Hammingin etäisyys ei ole sama asia kuin Levenšteinin etäisyys. Hammingin etäisyydessä verrataan samanpituisia merkkijonoja paikoittain ja sallitaan käytännössä vain korvaukset. Jos kaksi merkkijonoa ovat samanpituisia, pätee
mutta yhtäsuuruus ei päde yleisesti, koska Levenšteinin etäisyys voi hyödyntää myös lisäyksiä ja poistoja.
Painotetut etäisyydet ja lähikäsitteet Klassisessa Levenšteinin etäisyydessä jokaisen lisäyksen, poiston ja korvauksen kustannus on 1. Painotetussa editointietäisyydessä kustannukset voidaan valita eri tavoin esimerkiksi sen mukaan, kuinka todennäköinen tietty kirjoitusvirhe on. Tällöin tuloksena ei enää välttämättä ole täsmälleen sama metriikka kuin klassisessa Levenšteinin etäisyydessä.
Damerau–Levenshtein-etäisyydessä sallitaan lisäksi kahden vierekkäisen merkin paikkojen vaihto yhtenä muokkausoperaationa. Siksi sitä ei pidä kuvata samaksi etäisyydeksi kuin klassista Levenšteinin etäisyyttä, jossa perusoperaatiot ovat vain lisäys, poisto ja korvaus.
Sovelluksia Oikeinkirjoituksen tarkistus ja likimääräinen haku Oikeinkirjoituksen tarkistuksessa käyttäjän kirjoittamaa sanaa voidaan verrata sanakirjan sanoihin ja etsiä pieniä editointietäisyyksiä. Pelkkä etäisyys ei kuitenkaan yleensä ratkaise, mikä ehdokas on kielellisesti paras: käytännön järjestelmissä voidaan hyödyntää myös esimerkiksi sanan yleisyyttä, asiayhteyttä ja morfologista tietoa.
Likimääräisessä haussa sama periaate mahdollistaa merkkijonojen löytämisen myös silloin, kun niissä on kirjoitusvirheitä tai muita pieniä eroja.
Suomen murteiden normalisointi Levenšteinin etäisyyttä ja siihen liittyviä merkkikohdistusmenetelmiä on käytetty suomen murteiden ja yleiskielen muotojen vertailussa. Yves Scherrer vertasi vuonna 2023 useita merkkikohdistusmenetelmiä suomen, norjan ja sveitsinsaksan murreaineistoilla. Yksinkertainen Levenštein-kohdistus toimi tutkimuksessa vertailukohtana, ja koulutettujen kohdistusmenetelmien hyöty siihen nähden jäi osassa arviointia pieneksi.Yves Scherrer: Character Alignment Methods for Dialect-to-Standard Normalization. Proceedings of the 20th SIGMORPHON Workshop on Computational Research in Phonetics, Phonology, and Morphology, 2023.
Suomen murteiden automaattinen normalisointi on muutenkin tärkeä kieliteknologinen tehtävä, koska murteellinen ja puhekielinen aineisto poikkeaa yleiskielestä. Helsingin yliopiston tutkijat ovat esimerkiksi tutkineet 23 suomalaisen murrevariantin normalisointia yleiskieliseksi tekstiksi.Niko Partanen, Mika Hämäläinen ja Khalid Alnajjar: Dialect Text Normalization to Normative Standard Finnish. Proceedings of the 5th Workshop on Noisy User-generated Text, 2019, s. 141–146. doi:10.18653/v1/D19-5519.
Suomen ja viron kielellinen vertailu Levenšteinin etäisyyttä on käytetty myös suomen ja viron muoto-opillisen samankaltaisuuden tutkimuksessa. Annekatrin Kaivapalu ja Maisa Martin vertasivat vuonna 2017 Levenšteinin etäisyydellä mitattua merkkijonojen pintamuotojen etäisyyttä puhujien kokemaan samankaltaisuuteen. Tutkimuksessa tarkasteltiin 48 suomen- ja vironkielisten taivutusmuotojen paria.Annekatrin Kaivapalu ja Maisa Martin: Perceived similarity between written Estonian and Finnish: Strings of letters or morphological units?. Nordic Journal of Linguistics 40(2), 2017, s. 149–174. doi:10.1017/S0332586517000142.
Tutkimus havainnollistaa samalla Levenšteinin etäisyyden rajoitusta kielitieteessä: pieni merkkijonoetäisyys kuvaa pintamuotojen samankaltaisuutta, mutta ei yksinään kielellistä rakennetta, merkitystä tai puhujan kokemaa samankaltaisuutta.Annekatrin Kaivapalu ja Maisa Martin: Perceived similarity between written Estonian and Finnish: Strings of letters or morphological units?. Jyväskylän yliopiston JYX-julkaisuarkisto, 2017.
Unicode ja vertailuyksikkö Levenšteinin etäisyys määritellään symbolijonoille, joten ohjelmiston on ratkaistava, mitä yksi vertailtava symboli tarkoittaa. Unicode-tekstissä sama käyttäjän havaitsema kirjain voi joissakin tapauksissa koostua yhdestä koodipisteestä tai useamman koodipisteen yhdistelmästä.
Esimerkiksi kirjain ä voidaan esittää Unicode-tekstissä valmiina koodipisteenä U+00E4 tai yhdistelmänä a + U+0308. Nämä esitykset ovat kanonisesti ekvivalentteja, mutta niiden koodipistejonot ovat erilaiset. Unicode määrittelee NFC- ja NFD-normalisointimuodot tällaisten esityserojen käsittelyyn.Unicode Standard Annex #15: Unicode Normalization Forms. Unicode Consortium. Viitattu 10.9.2026.
Jos Levenšteinin etäisyys lasketaan suoraan koodipisteistä ilman yhdenmukaista normalisointia, kanonisesti ekvivalentit tekstit voivat siksi saada odottamattoman etäisyyden. Käyttäjän näkemiä merkkejä vastaavissa sovelluksissa vertailuyksikkönä voidaan käyttää myös grafeemiklustereita, joiden oletusrajat Unicode määrittelee tekstin segmentointia koskevassa standardissaan.Unicode Standard Annex #29: Unicode Text Segmentation. Unicode Consortium. Viitattu 10.9.2026.
Katso myös Hammingin etäisyys Dynaaminen ohjelmointi
Lähteet
Aiheesta muualla NIST Dictionary of Algorithms and Data Structures: Levenshtein distance levenshtein.net
Luokka:Algoritmit