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 
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 
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 

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:
 
 , dat wil zeggen d is een metriek.

Bovendien:
 
 
 
 

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 .

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.

Algoritme