Levenshteinavstånd är inom informationsteorin och datavetenskapen ett specifikt redigeringsavstånd mellan två strängar eller andra sekvenser av symboler. I den klassiska formen är avståndet det minsta antalet enskilda infogningar, raderingar och substitutioner som krävs för att omvandla den ena strängen till den andra, där varje operation har kostnaden 1.Paul E. Black (red.), "Levenshtein distance", Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology, uppdaterad 15 maj 2019. Läst 10 september 2026. Avståndet har fått sitt namn efter Vladimir Levensjtejn, som beskrev problemet i samband med felkorrigerande koder 1965.В. И. Левенштейн (1965), "Двоичные коды с исправлением выпадений, вставок и замещений символов", Доклады Академии Наук СССР, 163(4):845–848.
Levenshteinavstånd används bland annat i stavningskontroll, ungefärlig strängmatchning, textsökning och språkteknologi. Det förekommer också i språkvetenskapliga tillämpningar där stavnings- eller uttalsformer jämförs kvantitativt.
Definition och beräkning Låt och vara två strängar. Låt beteckna Levenshteinavståndet mellan prefixen och . Randvillkoren är
och för och gäller
där om symbolerna är lika och annars. De tre termerna motsvarar i tur och ordning radering, infogning samt matchning eller substitution. Det sökta avståndet är .Robert A. Wagner och Michael J. Fischer (1974), "The String-to-String Correction Problem", Journal of the ACM, 21(1):168–173. doi:10.1145/321796.321811.
Beräkningen görs vanligen med dynamisk programmering. En tabell fylls från kortare prefix till längre, så att varje cell bygger på redan beräknade delproblem.
Exempel Levenshteinavståndet mellan katt och hatt är 1, eftersom en enda substitution, k → h, räcker. På samma sätt är avståndet mellan bok och bock 1, eftersom c kan infogas.
För längre strängar kan flera olika följder av redigeringsoperationer ge samma minimala kostnad. Om hela tabellen sparas kan en optimal redigeringsföljd rekonstrueras genom att följa föregångare bakåt från .
Algoritm och komplexitet Den vanliga dynamiska programmeringsalgoritmen beräknar en tabell med värden. Tidsåtgången är därför , där och är strängarnas längder.
Om hela tabellen lagras är minnesåtgången . Om endast själva avståndet behövs och ingen redigeringsföljd ska rekonstrueras räcker det att behålla den aktuella och föregående raden; minnesåtgången kan då reduceras till .Esko Ukkonen (1985), "Algorithms for approximate string matching", Information and Control, 64(1–3):100–118. doi:10.1016/S0019-9958(85)80046-2.
Det finns också algoritmer vars körtid beror på hur stort det sökta avståndet eller en given feltröskel är. Ukkonen beskrev exempelvis metoder som undviker att beräkna delar av den fullständiga tabellen när avståndet är litet i förhållande till strängarnas längd.
Egenskaper Med de klassiska enhetskostnaderna är Levenshteinavståndet ett metriskt avstånd. Det innebär bland annat att avståndet är icke-negativt, symmetriskt, noll endast för identiska strängar och uppfyller triangelolikheten.Gonzalo Navarro (2001), "A Guided Tour to Approximate String Matching", ACM Computing Surveys, 33(1):31–88. doi:10.1145/375360.375365.
För två strängar med längderna och gäller de enkla gränserna
Den undre gränsen följer av att minst infogningar eller raderingar krävs för att jämna ut längdskillnaden. Den övre gränsen kan uppnås genom att först substituera så många symboler som möjligt och därefter infoga eller radera återstående symboler.
Om två strängar har samma längd är Levenshteinavståndet högst deras Hammingavstånd, eftersom varje avvikande position kan rättas med en substitution. Likhet gäller däremot inte alltid: infogningar och raderingar kan i vissa fall ge en kortare redigeringsföljd än att substituera varje avvikande position.
Viktade avstånd och varianter Den klassiska definitionen ger alla tre operationer kostnaden 1. I viktade varianter kan kostnaden i stället bero på vilken operation som utförs eller på vilka symboler som berörs. Sådana modeller kan vara användbara när vissa typer av förändringar bedöms som mer sannolika eller språkligt närmare än andra.
Ett närliggande mått är Damerau–Levenshtein-avstånd, där även transponering av två intilliggande symboler tillåts som en enskild operation. Det är därför inte identiskt med det klassiska Levenshteinavståndet, som endast använder infogning, radering och substitution.
Tillämpningar Stavningskontroll Ett vanligt användningsområde är att jämföra ett okänt eller felstavat ord med ord i ett lexikon och rangordna kandidater efter redigeringsavstånd. I en laboration vid Linköpings universitet används minimum edit distance för att föreslå kända svenska ord som ersättning för okända ord. Underlaget omfattar bland annat ordfrekvensdata från Göteborgs-Posten och Stockholm–Umeå Corpus."Laboration 7: Rättstavning", Institutionen för datavetenskap, Linköpings universitet. Läst 10 september 2026.
Avståndet är dock bara en del av en stavningskontroll. Ordfrekvens, språklig kontext och morfologi kan behövas för att avgöra vilket av flera närliggande ord som är den mest rimliga korrigeringen.
Historisk textnormalisering Levenshteinbaserade metoder har använts för att normalisera äldre svensk stavning till modernare former. Eva Pettersson, Beáta Megyesi och Joakim Nivre beskrev 2013 en metod med kontextkänsligt viktat Levenshteinavstånd och sammansättningsdelning. Metoden utvärderades på svenska historiska texter och användes för att göra materialet mer kompatibelt med språkteknologiska verktyg tränade på modern text.Eva Pettersson, Beáta Megyesi och Joakim Nivre (2013), "Normalisation of Historical Text Using Context-Sensitive Weighted Levenshtein Distance and Compound Splitting", i Proceedings of the 19th Nordic Conference of Computational Linguistics (NODALIDA 2013), s. 163–179, Linköping University Electronic Press.
Dialektometri och nordisk språkvariation I dialektometri kan Levenshteinavstånd användas för att sammanfatta skillnader mellan många ordformer till ett numeriskt språkligt avstånd. Therese Leinonen använde 2012 Levenshteinavstånd i en analys av finlandssvenska dialekter. Materialet bestod av uttalet av 86 ord från 77 orter, och avstånden analyserades med bland annat klusteranalys och multidimensionell skalering.Therese Leinonen (2012), "Indelning av finlandssvenska dialekter med särskild hänsyn till Åboland", Folkmålsstudier, 50:155–173.
Levenshteinbaserade ortografiska avstånd har också använts för att studera ömsesidig begriplighet mellan närbesläktade nordiska språk. I en studie av skriven danska bland svenskar beräknades normaliserade Levenshteinavstånd mellan 347 danska ord och deras svenska motsvarigheter. Forskarna analyserade därefter sambandet mellan ortografiskt avstånd och hur väl de danska orden förstods av svenska deltagare.Charlotte Gooskens, Sebastian Kürschner och Vincent J. van Heuven (2022), "The role of loanwords in the intelligibility of written Danish among Swedes", Nordic Journal of Linguistics, 45(1):4–29. doi:10.1017/S0332586521000111.
Unicode och jämförelseenhet När Levenshteinavstånd beräknas på Unicode-text måste det vara tydligt vilken enhet som jämförs. Ett tecken som uppfattas som ett enda skrivtecken kan bestå av flera Unicode-kodpunkter, och kanoniskt ekvivalenta texter kan ha olika kodpunktssekvenser. Unicode definierar normaliseringsformer som NFC och NFD för att ge en konsekvent representation av kanoniskt ekvivalent text."Unicode Standard Annex #15: Unicode Normalization Forms", Unicode Consortium, version 17.0.0. Läst 10 september 2026.
Detta är relevant även för svenska bokstäver med diakritiska tecken, exempelvis å, ä och ö. Om två strängar jämförs utan en gemensam normaliseringsstrategi kan kodpunktsbaserat Levenshteinavstånd därför bli större trots att texten är kanoniskt ekvivalent. För tillämpningar som ska följa användarens uppfattning om tecken kan det dessutom vara lämpligt att segmentera texten i grafemkluster i stället för enskilda kodpunkter."Unicode Standard Annex #29: Unicode Text Segmentation", Unicode Consortium, version 17.0.0. Läst 10 september 2026.
Referenser
Externa länkar
NIST Dictionary of Algorithms and Data Structures – Levenshtein distance levenshtein.net
Kategori:Diskret matematik Kategori:Informationsteori