Distancia entre palabras (Algoritmo de Levenshtein)

[[Héctor Randolph]]

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,     // costo de borrar,
                   Min(d[i, j-1] + 1, // costo de insertar
                       d[i-1, j-1] + cost));   // costo de sustituir                            
    end;
  Result:=d[Len1,Len2];
end;

Ejemplo de uso:

Código Delphi [-]
  ShowMessageFmt('La distancia entre kitten y sitting es : %d',[DistanciaLevenshtein('kitten','sitting')]);