Algoritmo que compara cadenas de texto

[Faust]

Saludos de nuevo amigos, llevo horas buscando un hilo antiguo y no lo encuentro ojalá ustedes puedan orientarme para llegar a él, lo que pasa es que ni siquiera me acuerdo de como se llama el algoritmo, pero no es el común para comparar cadenas de texto.

La cosa es así alguien alguna vez comentó que quería o tenía el un algoritmo que decía cuantas modificaciones había que hacer en una cadena de texto para convertirla en otra, por ejemplo:


var
Cambios: integer;
Cadena1, Cadena2: string;

Cadena1:= 'calabaza'
Cadena2:= 'calabozo'

Cambios:= Función(Cadena1, cadena2); // Cambios es igual a 2, porque solo basta hacer dos modificaciones para que sean la misma.


Saludos y gracias de antemano.

[cecam]

Hoooola!!

Si no me equivoco se llama Distancia_de_Levenshtein
http://es.wikipedia.org/wiki/Distancia_de_Levenshtein

function levenshtein(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, // deletion,
Min(d[i, j-1] + 1, // insertion
d[i-1, j-1] + cost // substitution
)
);
end;
Result:=d[Len1,Len2];
end;


Saludos!!

[Faust]

Muchísimas gracias!!!

Efectivamente es esto lo que estoy buscando... ya haciendo una búsqueda en los foros del club he encontrado algunos hilos ya antiguos...

De nuevo muchas gracias. :)