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. De afstandsmaat is genoemd naar Vladimir Levenshtein, die hem in 1965 uitvond.
De verzameling geldige bewerkingen is afhankelijk van de precieze toepassing, maar meestal worden op zijn minst de bewerkingen insertie (teken invoegen), deletie (teken verwijderen) en alteratie (teken veranderen in een ander teken) gebruikt, en soms een operatie die twee tekens verwisselt (wat anders minstens twee operaties zou kosten). 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:
- 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)
De Levenshteinafstand kan gezien worden als een vervanger voor de Hammingafstand, die slechts woorden met dezelfde lengte kan verwerken, en maar 1 operatie kent (alteratie).
[bewerk] Het Algoritme
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]
