Foros Club Delphi - Algoritmo que compara cadenas de texto

Foros Club Delphi (https://www.clubdelphi.com/foros/index.php)

- Varios (https://www.clubdelphi.com/foros/forumdisplay.php?f=11)

- - Algoritmo que compara cadenas de texto (https://www.clubdelphi.com/foros/showthread.php?t=68395)

Faust

11-06-2010 01:06:50

Algoritmo que compara cadenas de texto

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:

Código Delphi [-]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

11-06-2010 08:38:38

Hoooola!!

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

Código:

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

11-06-2010 16:42:32

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. :)

La franja horaria es GMT +2. Ahora son las 08:10:10.