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)



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:

ShowMessageFmt('La distancia entre kitten y sitting es : %d',[DistanciaLevenshtein('kitten','sitting')]);

[Delphius]

Hola Hector.
De curioso pasé por aquí para ver de que se trata, y veo que es un algoritmo relativamente sencillo... he notado que te basaste en el contenido de wikipedia.
¿Por casualidad no sabes si es válido para cualquier idioma?¿O sólo funciona para el inglés?

[roman]

No creo que dependa del idioma porque, como explica Héctor, el algoritmo sólo mide cuántas transformaciones hay que hacer para pasar de una cadena a otra, y las transformaciones son meras operaciones entre caracteres, tal como se indica en el código: borrar, insertar, sustituir.

Muy bonita esta función. Por cierto, la nomenclatura "distancia" es realmente adecuada, ya que la función cumple las tres propiedades básicas de una métrica:

1. Reflexividad: d(S, T) = 0 si y sólo si S = T
2. Simetría: d(S, T) = d(T, S)
3. Desigualdad del triángulo: d(A, B) <= d(A, C) + d(C, B)

[Héctor Randolph]

Hola Delphius, efectivamente el texto es extraído de Wikipedia, de hecho, lo que hice fue agregar en la Wikipedia el código en Delphi ya que no existía y después lo publiqué acá.

[Delphius]

Gracias por las aclaraciones roman y hector.
Buscando un poco y leyendo me doy conque lo que hace es algo similar al algoritmo Huggman (o algo así), que lo que permite es calcular la cantidad de bits que varían entre un conjunto y otro. Tengo entendido que se usa (Huggman)(o mejor dicho se usaba) para calcular y determinar si se producían errores en la transmisión de información en las redes.
Me mareaba el hecho de que la palabra usada en el ejemplo no sea castellana...