De Levenshteinafstand is een afstandsmetriek voor het meten van het verschil tussen twee tekenreeksen of, algemener, twee eindige reeksen symbolen. In de klassieke definitie is de afstand gelijk aan het kleinste aantal elementaire bewerkingen dat nodig is om de ene reeks in de andere om te zetten. De toegestane bewerkingen zijn het invoegen van één symbool, het verwijderen van één symbool en het vervangen van één symbool door een ander; iedere bewerking heeft kost 1.V. I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals”, Doklady Akademii Nauk SSSR, 163(4), 845–848, 1965. Engelse vertaling in Soviet Physics Doklady, 10(8), 707–710, 1966. Math-Net.
De maat is genoemd naar de Sovjet-wiskundige Vladimir Levensjtein, die haar in 1965 introduceerde in de context van foutcorrigerende codes. De Levenshteinafstand is een klassieke vorm van bewerkingsafstand (edit distance). De term bewerkingsafstand wordt ook in ruimere zin gebruikt voor modellen waarin andere bewerkingen zijn toegestaan of waarin de bewerkingen verschillende kosten hebben.Gonzalo Navarro, “A guided tour to approximate string matching”, ACM Computing Surveys, 33(1), 31–88, 2001. doi:10.1145/375360.375365.
De Levenshteinafstand wordt onder meer toegepast bij spellingscorrectie, zoekmethoden die kleine schrijfafwijkingen toelaten, dialectometrie, OCR-evaluatie, record linkage en het vergelijken van biologische sequenties.
Definitie
Zij
en
twee reeksen. Definieer als de Levenshteinafstand tussen het prefix en het prefix .
Voor de lege reeks gelden de randvoorwaarden
Voor en geldt
waarbij
De drie mogelijkheden komen respectievelijk overeen met het verwijderen van een symbool uit de bronreeks, het invoegen van een symbool uit de doelreeks en het behouden of vervangen van het laatste symbool van beide prefixen.Robert A. Wagner en Michael J. Fischer, “The String-to-String Correction Problem”, Journal of the ACM, 21(1), 168–173, 1974. doi:10.1145/321796.321811.
De afstand tussen de volledige reeksen is .
Voorbeelden
De Levenshteinafstand tussen water en wetend is 3. Een optimale reeks bewerkingen is bijvoorbeeld:
water → weter: vervang a door e; weter → weten: vervang r door n; weten → wetend: voeg d toe.
Een ander veelgebruikt voorbeeld is kitten → sitting. Daarvoor zijn twee vervangingen en één invoeging nodig, zodat de afstand 3 is.
Eigenschappen en grenzen
Bij eenheidskosten voor invoegen, verwijderen en vervangen is de Levenshteinafstand een metriek: zij is niet-negatief, is alleen nul voor twee gelijke reeksen, is symmetrisch en voldoet aan de driehoeksongelijkheid.
Voor reeksen met lengten en geldt
De ondergrens volgt uit het feit dat één invoeging of verwijdering de lengte slechts met één verandert. De bovengrens kan worden bereikt door eerst symbolen in het gemeenschappelijke lengtegedeelte te vervangen en daarna de resterende symbolen in te voegen of te verwijderen.
Als beide reeksen dezelfde lengte hebben, is de Hammingafstand een bovengrens voor de Levenshteinafstand:
De Hammingafstand telt alleen vervangingen en is rechtstreeks gedefinieerd voor reeksen van gelijke lengte.
Wanneer vervangingen niet zijn toegestaan en alleen invoegingen en verwijderingen mogen worden gebruikt, is de minimale bewerkingsafstand
waarbij de lengte is van een langste gemeenschappelijke deelreeks. Deze formule geldt niet ongewijzigd voor de klassieke Levenshteinafstand, omdat één vervanging daar kost 1 heeft, terwijl verwijderen gevolgd door invoegen samen kost 2 heeft.
Berekening
Dynamisch programmeren
De klassieke berekening gebruikt dynamisch programmeren. Een matrix van cellen bevat de afstanden tussen alle paren prefixen.
functie LevenshteinAfstand(s[1..m], t[1..n]): maak d[0..m, 0..n]
voor i van 0 tot m: d[i,0] = i
voor j van 0 tot n: d[0,j] = j
voor i van 1 tot m: voor j van 1 tot n: als s[i] = t[j]: kost = 0 anders: kost = 1
d[i,j] = minimum( d[i-1,j] + 1, // verwijderen van s[i] d[i,j-1] + 1, // invoegen van t[j] d[i-1,j-1] + kost // overeenkomst of vervanging )
geef d[m,n] terug
De invariant is dat d[i,j] het kleinste aantal bewerkingen bevat waarmee de eerste i symbolen van s in de eerste j symbolen van t kunnen worden omgezet.
Het vullen van de volledige matrix vergt tijd en geheugen.
Geheugenreductie
Als alleen de afstandswaarde nodig is, hoeft niet de volledige matrix te worden bewaard. Een rij hangt alleen af van de vorige rij en de reeds berekende waarden in de huidige rij. Door de kortste reeks als opgeslagen dimensie te gebruiken kan het werkgeheugen worden teruggebracht tot .Esko Ukkonen, “Algorithms for approximate string matching”, Information and Control, 64(1–3), 100–118, 1985. doi:10.1016/S0019-9958(85)80046-2.
Terugvinden van de bewerkingen
Wanneer de volledige matrix wordt bewaard, kan vanaf worden teruggelopen naar voorgangercellen die de huidige minimumwaarde verklaren. Zo kan een optimale reeks invoegingen, verwijderingen en vervangingen worden gereconstrueerd. Er kunnen meerdere optimale paden bestaan met dezelfde totale kost.
Afstandsafhankelijke algoritmen
Wanneer de werkelijke bewerkingsafstand klein is ten opzichte van de lengten van de reeksen, hoeft niet noodzakelijk de volledige matrix te worden onderzocht. Ukkonen ontwikkelde exacte algoritmen die het onderzochte gebied tot een relevante band rond de hoofddiagonaal beperken en waarvan de rekentijd afhangt van de werkelijke of toegestane afstand.
Het woord approximatief in approximate string matching betekent hierbij dat niet-identieke tekenreeksen als overeenkomst kunnen worden aanvaard; het betekent niet noodzakelijk dat de numerieke afstand zelf slechts bij benadering wordt berekend.
Bitparallelle methoden
Myers beschreef in 1999 een bitvectoralgoritme voor approximatieve patroonvergelijking. Daarbij worden meerdere toestanden van de dynamische programmering tegelijk in de bits van een machinewoord opgeslagen en met bitbewerkingen bijgewerkt.Gene Myers, “A fast bit-vector algorithm for approximate string matching based on dynamic programming”, Journal of the ACM, 46(3), 395–415, 1999. doi:10.1145/316542.316550.
Deze en andere gespecialiseerde methoden betekenen dat de praktische berekening niet kan worden samengevat met de stelling dat alle verbeteringen noodzakelijk hetzelfde kwadratische gedrag als de volledige matrix behouden.
Varianten en verwante afstanden
Gewogen bewerkingsafstand
Bij een gewogen bewerkingsafstand kunnen invoegingen, verwijderingen en vervangingen verschillende kosten krijgen; een vervangingskost kan bovendien afhangen van het specifieke paar symbolen. Willekeurige kosten behouden niet automatisch alle metrieke eigenschappen. Asymmetrische kosten kunnen bijvoorbeeld de symmetrie verbreken.
Een bekende verwante maat is de Damerau-Levenshteinafstand, waarbij ook het verwisselen van twee aangrenzende symbolen als elementaire bewerking wordt toegestaan.
Langste gemeenschappelijke deelreeks
De lengte van de langste gemeenschappelijke deelreeks is zelf geen bewerkingsafstand. Wanneer echter alleen invoegingen en verwijderingen zijn toegestaan, bepaalt die lengte de minimale bewerkingsafstand via . Dit onderscheid is van belang omdat een vervanging in de klassieke Levenshteinafstand slechts één bewerking kost.
Normalisatie
De ruwe afstand kan grotere waarden aannemen naarmate de reeksen langer zijn. Daarom worden in sommige toepassingen genormaliseerde varianten gebruikt. Er bestaat geen enkele universele definitie van een “genormaliseerde Levenshteinafstand”.
Een eenvoudige veelgebruikte normalisatie is
met als overeenkomstige similariteit bijvoorbeeld
Andere normalisaties zijn mogelijk en behouden niet automatisch de metrieke eigenschappen. Li en Liu beschreven in 2007 een specifieke genormaliseerde editafstand die onder voorwaarden wel een metriek is.Li Yujian en Liu Bo, “A Normalized Levenshtein Distance Metric”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(6), 1091–1095, 2007. doi:10.1109/TPAMI.2007.1078.
Toepassingen
Spellingscorrectie en approximatief zoeken
Bij spellingscorrectie kan de Levenshteinafstand worden gebruikt om woorden te vinden die met weinig bewerkingen van een onbekend of fout gespeld woord verschillen. In grote woordenlijsten en tekstcollecties wordt de afstand vaak gecombineerd met filters, indexstructuren, q-grammen of andere technieken om te voorkomen dat elk mogelijk kandidatenpaar volledig wordt vergeleken.
In onderzoek aan de Universiteit Antwerpen naar contextgevoelige correctie van Nederlandse klinische vrije tekst werden kandidaten onder meer met de nauw verwante Damerau-Levenshteinafstand uit een lexicon geselecteerd en vervolgens op contextuele geschiktheid gerangschikt. Het onderzoek gebruikte handmatig geannoteerde Nederlandse klinische gegevens van het Universitair Ziekenhuis Antwerpen.Pieter Fivez, Simon Šuster en Walter Daelemans, “Unsupervised Context-Sensitive Spelling Correction of English and Dutch Clinical Free-Text with Word and Character N-Gram Embeddings”, Computational Linguistics in the Netherlands Journal, 7, 39–52, 2017. CLIN Journal.
Dit laat ook een beperking van eenvoudige tekenreeksafstand zien: een kleine editafstand kan geschikte kandidaten opleveren, maar de tekstuele context is nodig om tussen meerdere plausibele woorden te kiezen.
Dialectometrie van Nederlandse taalvariëteiten
Een belangrijke toepassing in het Nederlandse taalgebied is de kwantitatieve vergelijking van dialectuitspraak. Wilbert Heeringa ontwikkelde in zijn proefschrift aan de Rijksuniversiteit Groningen methoden om uitspraakverschillen met Levenshteinafstanden te meten.Wilbert Jan Heeringa, Measuring Dialect Pronunciation Differences using Levenshtein Distance, proefschrift, Rijksuniversiteit Groningen, 2004. Rijksuniversiteit Groningen.
In dit soort dialectometrie worden fonetische transcripties vergeleken. Varianten kunnen gewichten gebruiken waarbij fonetisch sterk vergelijkbare klanken een lagere vervangingskost krijgen dan sterk verschillende klanken. Heeringa en medewerkers pasten dergelijke methoden onder meer toe op honderden Nederlandse dialecten.Wilbert Heeringa en Angelika Braun, “The use of the Almeida-Braun system in the measurement of Dutch dialect distances”. Rijksuniversiteit Groningen.
Het Instituut voor de Nederlandse Taal stelt bovendien de gedigitaliseerde RND Woordenlijsten beschikbaar, gebaseerd op fonetische transcripties uit de Reeks Nederlandse Dialectatlassen voor plaatsen in Nederland en Vlaanderen; de documentatie verwijst expliciet naar Heeringa's werk met Levenshteinafstand.Instituut voor de Nederlandse Taal, “RND Woordenlijsten”, versie 1.1, 2021. INT Taalmaterialen.
Ook recenter onderzoek naar Friese en Nedersaksische dialectgroepen in Noord-Nederland gebruikt een multidimensionale variant van de Levenshteinafstand om fonetische verandering tussen 1990 en 2010 te kwantificeren.Raoul Buurke, Hedwig G. Sekeres, Wilbert Heeringa, Remco Knooihuizen en Martijn Wieling, “Estimating the level and direction of aggregated sound change of dialects in the Northern Netherlands”, Taal en Tongval, 74(2), 183–214, 2022. doi:10.5117/TET2022.2.002.BUUR.
OCR en Nederlandse digitale collecties
Bij optische tekenherkenning kan de kwaliteit van herkende tekst worden beoordeeld door de OCR-uitvoer met een gecontroleerde referentietekst te vergelijken. De Koninklijke Bibliotheek onderzocht de invloed van OCR-kwaliteit op Nederlandse kranten-, tijdschrift- en boekcollecties en noemt tekstafstandsmetingen zoals Levenshtein expliciet als een manier om OCR-kwaliteit te beoordelen.Koninklijke Bibliotheek, “Is your OCR good enough? A comprehensive assessment of the impact of OCR quality on downstream tasks”, KB LAB, 2020. KB LAB.