In inligtingsteorie word die Levenshteinafstand of redigeerafstand tussen twee karakterstringe gegee deur die minimum aantal bewerkings benodig om een string in 'n ander te transformeer, waar 'n bewerking 'n invoeging, skrapping, of vervanging is. Dit is vernoem na Vladimir Levenshtein, wat die afstand in 1965 oorweeg het. Dit is nuttig in toepassings wat moet bepaal hoe soortgelyk twee stringe is, soos speltoetsers en vertalingsgeheues.
Byvoorbeeld, die Levenshteinafstand tussen "kitten" en "sitting" is 3 omdat daar drie redigeerbewerkings nodig is om die een in die ander te verander, en daar is geen manier om dit in minder as drie verwerkings te doen nie:
Dit kan as 'n veralgemening van die Hammingafstand gesien word wat vir stringe van dieselfde lengte gebruik word en wat slegs vervangingsbewerkings oorweeg. Daar is ook verdere veralgemenings van die Levenshteinafstand wat byvoorbeeld omruiling van twee karakters as 'n enkele verwerking hanteer.
'n Algemene onder-na-bo dinamieseprogrammeringalgoritme vir die berekening van die Levenshteinafstand behels die gebruik van 'n (n + 1) × (m + 1) matriks, waar n en m die lengtes van die twee stringe is. Hier is pseudokode vir 'n funksie Levenshteinafstand wat twee stringe neem, strA met lengte lenStrA, en strB met lengte lenStrB, en die Levenshteinafstand tussen hulle bereken:
heelgetal Levenshteinafstand(karakter strA[1..lenStrA], karakter strB[1..lenStrB])
// d is 'n tabel met lenStrA+1 rye en lenStrB+1 kolomme
verklaar int d[0..lenStrA, 0..lenStrB]
// i en j word vir iterasie oor strA en strB gebruik
verklaar heelgetal i, j, koste
vir i vanaf 0 tot lenStrA
d[i, 0] := i
vir j vanaf 0 tot lenStrB
d[0, j] := j
vir i vanaf 1 tot lenStrA
vir j vanaf 1 tot lenStrB
as strA[i] = strB[j] dan koste := 0
anders koste := 1
d[i, j] := minimum(
d[i-1, j ] + 1, // skrapping
d[i , j-1] + 1, // invoeging
d[i-1, j-1] + koste // vervanging
)
raporteer d[lenStrA, lenStrB]
Die invariant wat deurgaans in die algoritme behoue bly is dat ons die aanvanklike segment str1[1..i] in str2[1..j] kan transformeer deur 'n minimum van d[i,j] verwerkings te gebruik. Aan die einde bevat die regter onderste element van die skikking die antwoord.
Moontlike verbeteringe aan die algoritme sluit in:
j is, afsonderlik stoor.d[i,0] kan na binne die hoof buite lus geskuif word.cost, kan egter in parallel bereken word en die algoritme kan aangepas word om die minimum funksie in fases uit te voer om afhanklikhede te elimineer.Soos vroeër genoem, is die invariant dat ons die aanvanklike segment s[1..i] in t[1..j] kan transformeer deur 'n minimum d[i,j] verwerkings te gebruik. Die invariant geld aangesien:
s[1..i] in die leë string t[1..0] getransformeer kan word deur eenvoudig al i karakters te laat gaan. Op soortgelyke manier kan ons s[1..0] na t[1..j] , transformeer deur eenvoudig al j karakters op te tel.s[1..i] na t[1..j-1] in k verwerkings kan transformeer dan kan ons t[j] na die tyd optel om t[1..j] in k+1 verwerkings te kry.s[1..i-1] na t[1..j] in k verwerkings kan transformeer, dan kan ons dieselfde verwerkings doen op s[1..i] en dan die oorspronklike s[i] teen die einde in k+1 verwerkings verwyder.s[1..i-1] na t[1..j-1] in k verwerkings kan transformeer, kan ons dieselfde doen aan s[1..i] en dan 'n vervanging van t[j] vir die oorspronklike s[i] teen die einde indien nodig wat k+cost verwerkings benodig.s[1..n] in t[1..m] te transformeer is natuurlik die aantal benodig om al s in alle t te transformeer, en dus d[n,m] geld ons resultaat.Die bewys slaag nie daarin om te bevestig dat die getal geplaas in d[i,j] inderdaad minimaal is nie; dit is moeiliker om aan te toon, en behels 'n argument by contradiction waarin ons aanneem dat d[i,j] kleiner is as die minimum van drie, en dit dan gebruik om te wys dat een van die drie nie minimaal is nie.
Die bronkode vir voorbeeld implementasies in verskillende rekenaartale kan gevind word by Wikisource Geargiveer 28 Junie 2006 op Wayback Machine.
Die Levenshteinafstand het verskillende bo- en onder-grense wat nuttig is in toepassings wat baie daarvan moet bereken en vergelyk. Dit sluit in:
s en t genoem word is die aantal karakters (sonder om duplikate te tel) in s wat nie in in t gevind word nie 'n onder-grens.