Se le llama Distancia de Levenshtein o distancia de edición al número mínimo de operaciones requeridas para transformar una cadena de caracteres en otra.
Es útil en programas que determinan cuán similares son dos cadenas de caracteres, como es el caso de los correctores de ortografía.
Por ejemplo, la distancia de Levenshtein entre "kitten" y "sitting" es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro.
1. kitten ? sitten (sustitución de 'k' por 's')
2. sitten ? sittin (sustitución de 'e' por 'i')
3. sittin ? sitting (inserción de 'g' al final)
Código Delphi
[-]
function DistanciaLevenshtein(Str1, Str2: String): Integer;
var
d : array of array of Integer;
Len1, Len2 : Integer;
i, j, cost: Integer;
begin
Len1:=Length(Str1);
Len2:=Length(Str2);
SetLength(d,Len1+1);
for i := Low(d) to High(d) do
SetLength(d[i],Len2+1);
for i := 0 to Len1 do
d[i,0]:=i;
for j := 0 to Len2 do
d[0,j]:=j;
for i:= 1 to Len1 do
for j:= 1 to Len2 do
begin
if Str1[i]=Str2[j] then
cost:=0
else
cost:=1;
d[i,j]:= Min(d[i-1, j] + 1, Min(d[i, j-1] + 1, d[i-1, j-1] + cost)); end;
Result:=d[Len1,Len2];
end;
Ejemplo de uso:
Código Delphi
[-]
ShowMessageFmt('La distancia entre kitten y sitting es : %d',[DistanciaLevenshtein('kitten','sitting')]);