Foros Club Delphi

Foros Club Delphi (https://www.clubdelphi.com/foros/index.php)
-   Trucos (https://www.clubdelphi.com/foros/forumdisplay.php?f=52)
-   -   Distancia entre palabras (Algoritmo de Levenshtein) (https://www.clubdelphi.com/foros/showthread.php?t=80821)

Héctor Randolph 26-07-2007 19:54:06

Distancia entre palabras (Algoritmo de Levenshtein)
 
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')]);

Delphius 27-07-2007 01:51:06

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 27-07-2007 07:53:23

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 27-07-2007 18:38:22

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 27-07-2007 23:28:34

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


La franja horaria es GMT +2. Ahora son las 17:43:07.

Powered by vBulletin® Version 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Traducción al castellano por el equipo de moderadores del Club Delphi