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.

Voorbeeld bewerken

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

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

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.

Varianten bewerken

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

Eigenschappen bewerken

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 bewerken

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 bewerken

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.