Levenshtein-distanse er et mål på forskjellen mellom to strenger. I den klassiske definisjonen er avstanden det minste antallet enkeltoperasjoner som kreves for å gjøre den ene strengen om til den andre, når de tillatte operasjonene er innsetting av ett tegn, sletting av ett tegn og erstatning av ett tegn med et annet. Hver operasjon har kostnad 1.Paul E. Black (red.): «Levenshtein distance», Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology. Oppdatert 15. mai 2019. Besøkt 10. september 2026.
Avstanden er oppkalt etter den sovjetiske matematikeren Vladimir Levenshtein, som beskrev denne typen redigeringsavstand i forbindelse med feilkorrigerende koder i 1965.V. I. Levenshtein: «Binary codes capable of correcting deletions, insertions, and reversals», Soviet Physics Doklady, 10(8), 1966, s. 707–710. Russisk original publisert i 1965. Levenshtein-distansen brukes blant annet i stavekontroll, omtrentlig strengmatching og språkteknologi. Den kan også brukes som en enkel komponent i analyser av biologiske sekvenser, men praktisk sekvenssammenstilling bruker ofte rikere modeller for substitusjoner og gap enn klassisk Levenshtein-distanse.Gonzalo Navarro: «A Guided Tour to Approximate String Matching», ACM Computing Surveys, 33(1), 2001, s. 31–88. doi:10.1145/375360.375365.
Definisjon La og være to strenger. La være Levenshtein-distansen mellom prefikset og prefikset . Randbetingelsene er
For og er
der
De tre uttrykkene svarer til henholdsvis sletting, innsetting og enten samsvar eller erstatning. Levenshtein-distansen mellom de to fullstendige strengene er .Robert A. Wagner og Michael J. Fischer: «The String-to-String Correction Problem», Journal of the ACM, 21(1), 1974, s. 168–173. doi:10.1145/321796.321811.
Eksempel Levenshtein-distansen mellom katt og hatt er 1, fordi én erstatning er tilstrekkelig:
katt → hatt.
Et eksempel med innsetting er bok → boka, som har avstand 1 dersom a settes inn til slutt.
For lengre strenger kan flere forskjellige sekvenser av redigeringsoperasjoner ha samme minimale kostnad. Dersom hele beregningstabellen lagres, kan en optimal redigeringssekvens rekonstrueres ved å følge optimale forgjengere bakover fra .
Algoritme og kompleksitet Den vanlige algoritmen bruker dynamisk programmering. En tabell med verdier fylles fra kortere prefikser til lengre. Hver celle avhenger bare av cellen over, cellen til venstre og cellen diagonalt over til venstre.
En enkel pseudokode er:
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]
Tidskompleksiteten til den fulle tabellalgoritmen er . Dersom hele tabellen lagres, er plassforbruket . Hvis bare selve avstanden er nødvendig, og ikke redigeringssekvensen, kan beregningen gjøres med bare de radene som trengs fortløpende. Da kan plassforbruket reduseres til .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.
Når en liten øvre grense for den tillatte avstanden er kjent, finnes det algoritmer som unngår å beregne hele tabellen. Ukkonen beskrev slike metoder der kjøretid og minnebruk kan avhenge av den faktiske redigeringsavstanden eller en terskel, i stedet for bare av produktet .
Egenskaper Med klassiske enhetskostnader er Levenshtein-distansen en metrikk. Den er ikke-negativ og symmetrisk, er null nøyaktig når strengene er identiske, og oppfyller trekantulikheten.
Hvis strengene har lengde og , gjelder
Den nedre grensen følger av at minst innsettinger eller slettinger må til for å utjevne lengdeforskjellen. Den øvre grensen kan oppnås ved først å erstatte så mange tegn som mulig og deretter sette inn eller slette resten.
For strenger med samme lengde er Hamming-avstanden en øvre grense for Levenshtein-distansen:
De to avstandene er ikke generelt like. Hamming-avstand teller posisjoner med ulike tegn og tillater ikke at en forskyvning av tegn håndteres ved en sletting og en innsetting, mens Levenshtein-distansen gjør det.
Vektede avstander og beslektede mål I klassisk Levenshtein-distanse har alle innsettinger, slettinger og erstatninger kostnad 1. I vektede varianter kan kostnaden avhenge av typen operasjon eller av hvilke symboler som berøres. Slike modeller kan være nyttige når enkelte feil eller lydlige forskjeller skal regnes som mindre enn andre. Vilkårlig valgte vekter kan imidlertid endre de matematiske egenskapene til avstanden.
Damerau–Levenshtein-distanse utvider operasjonssettet med transponering av to nabotegn som én redigeringsoperasjon. Det er derfor et annet mål enn klassisk Levenshtein-distanse, som bare har innsetting, sletting og erstatning som primitive operasjoner.
Anvendelser Stavekontroll og omtrentlig søk Ved stavekontroll kan et ukjent ord sammenlignes med ord i en ordliste, og kandidater med liten redigeringsavstand kan prioriteres. I praktiske systemer er Levenshtein-distansen ofte bare én del av vurderingen; frekvens, kontekst, morfologi og en modell av sannsynlige skrivefeil kan også være viktige.
I omtrentlig søk kan samme prinsipp brukes til å finne strenger som ligger innenfor en bestemt redigeringsavstand fra en forespørsel. Dette gjør det mulig å finne relevante treff selv når teksten inneholder små skrivefeil eller variasjoner.
Norske dialekter Levenshtein-metoden har en særlig dokumentert anvendelse i forskning på norske dialekter. Charlotte Gooskens og Wilbert Heeringa sammenlignet i 2004 Levenshtein-baserte avstander mellom 15 norske dialekter med avstander vurdert av norske lyttere. Studien undersøkte dermed hvor godt et automatisk mål basert på fonetiske transkripsjoner samsvarte med språkbrukernes egen oppfatning av dialektforskjeller.Charlotte Gooskens og Wilbert Heeringa: «Perceptive evaluation of Levenshtein dialect distance measurements using Norwegian dialect data», Language Variation and Change, 16(3), 2004, s. 189–207. doi:10.1017/S0954394504163023.
En nyere studie av Janne Bondi Johannessen, Andre Kåsen, Kristin Hagen, Anders Nøklestad og Joel Priestley sammenlignet Levenshtein-metoden med en nevralt basert autoenkodermetode for å måle dialektlikhet i norsk. Resultatene ble visualisert som dialektkart og sammenlignet med etablerte klassifikasjoner i norsk dialektlitteratur.Janne Bondi Johannessen, Andre Kåsen, Kristin Hagen, Anders Nøklestad og Joel Priestley: «Comparing Methods for Measuring Dialect Similarity in Norwegian», Proceedings of the Twelfth Language Resources and Evaluation Conference, 2020, s. 5343–5350.
Slike anvendelser viser også en begrensning: en Levenshtein-basert dialektavstand måler forskjeller i den valgte representasjonen av uttale eller tekst. Prosodi, sosial variasjon og andre språklige egenskaper inngår ikke automatisk i målet.
Talegjenkjenning og Stortinget Nasjonalbibliotekets Språkbank har brukt Levenshtein-distanse i behandlingsløpet for Norwegian Parliamentary Speech Corpus (NPSC), et talekorpus basert på opptak fra Stortinget.Nasjonalbiblioteket, Språkbanken: Norwegian Parliamentary Speech Corpus version 2.0, dokumentasjon, 2023. Besøkt 10. september 2026.
I forbehandlingen blir en automatisk Bokmål-transkripsjon sammenlignet med teksten i Stortingets referater. Et skript søker etter ordsekvenser med høy likhet ved hjelp av Levenshtein-distanse. Når sekvenser ligner sterkt, men ikke er identiske, kan ord fra referatet brukes til å forbedre den automatiske transkripsjonen. Dokumentasjonen beskriver også at referatene kan være skrevet på både bokmål og nynorsk, slik at denne prosessen i enkelte tilfeller erstatter bokmålsformer fra den automatiske talegjenkjenningen med nynorskformer.
Dette er et konkret norsk eksempel på at Levenshtein-distanse ikke bare brukes til enkeltord, men også som en del av en større prosesseringskjede for tale, tekst og ortografisk normalisering.
Unicode og sammenligningsenhet Levenshtein-distanse er definert for sekvenser av symboler. I programvare må det derfor bestemmes hva som skal regnes som ett symbol. I Unicode kan et tegn som brukeren oppfatter som ett skrifttegn, representeres av én eller flere kodepunkter.
Den norske bokstaven å kan for eksempel representeres som kodepunktet U+00E5 eller som a etterfulgt av det kombinerende ringtegnet U+030A. Representasjonene er kanonisk ekvivalente, men kodepunktsekvensene er forskjellige. Unicode definerer normaliseringsformene NFC og NFD for å håndtere slike representasjonsforskjeller.Unicode Consortium: Unicode Standard Annex #15: Unicode Normalization Forms. Besøkt 10. september 2026.
Hvis Levenshtein-distansen beregnes direkte på kodepunkter uten at tekstene først behandles på en konsistent måte, kan kanonisk ekvivalente strenger derfor få en uventet ikke-null avstand. I anvendelser der brukeropplevde tegn er relevante, kan det også være nødvendig å sammenligne grafemklynger i stedet for enkeltkodepunkter.Unicode Consortium: Unicode Standard Annex #29: Unicode Text Segmentation. Besøkt 10. september 2026.
Referanser
Eksterne lenker NIST Dictionary of Algorithms and Data Structures: Levenshtein distance Edit Distance Algorithm Demonstration, University of New Mexico levenshtein.net
Kategori:Informasjonsteori Kategori:Algoritmer