Levenshteinafstand

In de informatica is de Levenshteinafstand of bewerkingsafstand tussen twee strings (tekenreeksen) de minimale hoeveelheid bewerkingen die nodig is om de ene string in de andere te veranderen, waarbij de mogelijke bewerkingen zijn:

• verwijderen van een teken
• invoegen van een teken
• vervanging van een teken door een ander

Deze afstandsmetriek is genoemd naar Vladimir Levenshtein, die er in 1965 een artikel aan wijdde.

De term bewerkingsafstand wordt ook wel gebruikt voor dergelijke afstandsmaten in het algemeen. Er wordt dan een bepaalde verzameling toegestane bewerkingen op tekenreeksen gegeven en eventueel een kostenfunctie voor elke bewerking. De Levenshteinafstand is een van de mogelijkheden; andere zijn bijvoorbeeld

• de lengte van de grootste gemeenschappelijke deelreeks: daarbij is vervanging van een teken twee keer zo duur als verwijdering of toevoeging
• de Levenshtein-Damerau-afstand: daarbij is verwisseling van twee aangrenzende tekens even duur als de andere bewerkingen
• de Hammingafstand: daarbij is vervanging van een teken door een ander de enige toegestane bewerking

Een goed voorbeeld van software die functies gebruikt die hierop gebaseerd zijn, is spellingscontrole-software. Door de Levenshteinafstand van een woord naar enkele andere te berekenen, is snel een aantal alternatieven voor een woord te geven.

Een voorbeeld, de Levenshteinafstand tussen water en wetend is 3 en kan als volgt weergegeven worden:

1. water → weter (de a wordt vervangen door de e)
2. weter → weten (de r wordt vervangen door de n)
3. weten → wetend (de d wordt aan het einde van de string toegevoegd)

Eigenschappen

Noteer, gegeven strings s en t, hun concatenatie als s.t en hun Levenshteinafstand als d(s,t). Noteer de lengte van een string s als |s|.

Dan geldt:

• $\forall s,t:||s|-|t||\leq d(s,t)\leq max(|s|,|t|)$
• $\forall s,t,u:d(s,t)+d(t,u)\geq d(s,u)$, dat wil zeggen d is een metriek.

Bovendien:

• $\forall s,t:d(s,t)=d(t,s)$
• $\forall s,t:|t|=0\Rightarrow d(s,t)=|s|$
• $\forall s,t,u,v:|u|=1\wedge |v|=1\wedge u=v\Rightarrow d(s.u,t.v)=d(s,t)$
• $\forall s,t,u,v:|u|=1\wedge |v|=1\wedge u\not =v\Rightarrow d(s.u,t.v)=min(d(s,t),d(s.u,t),d(s,t.v))+1$

Dat betekent dat als we ons een matrix voorstellen waarin de Levenshteinafstand tussen alle prefixen van twee strings staat genoteerd, we die afstanden kunnen uitrekenen door de matrix te vullen met een floodfill-algoritme. Zo kan uiteindelijk de afstand tussen de twee strings worden bepaald.

Het basisalgoritme voor de berekening van de Levenshteinafstand

Hieronder een stukje pseudocode waarop functies voor andere programmeertalen kunnen worden gebaseerd.

int LevenshteinAfstand(char str1[1..lenStr1], char str2[1..lenStr2])
   // d is een tabel met lenStr1+1 rijen and lenStr2+1 kolommen
   declare int d[0..lenStr1, 0..lenStr2]
   // i en j worden gebruikt om in str1 en str2 te tellen
   declare int i, j, cost
 
   for i from 0 to lenStr1
       d[i, 0] := i
   for j from 0 to lenStr2
       d[0, j] := j
 
   for i from 1 to lenStr1
       for j from 1 to lenStr2
           if str1[i] = str2[j] then cost := 0
                                else cost := 1
           d[i, j] := minimum(
                                d[i-1, j] + 1,     // deletie
                                d[i, j-1] + 1,     // insertie
                                d[i-1, j-1] + cost   // alteratie
                            )
 
   return d[lenStr1, lenStr2]

Complexiteit

De kosten van deze methode zijn $O(|s|.|t|)$.

Op dit basisidee zijn wel verbeteringen gepubliceerd, maar die houden allemaal het kwadratische karakter.

Dit verklaart waarom bij de vergelijking van lange strings (zoals bij DNA-sequencing) geen exacte, maar heuristische algoritmen worden gebruikt.