Ver Mensaje Individual
  #1  
Antiguo 26-07-2007
Avatar de Héctor Randolph
[Héctor Randolph] Héctor Randolph is offline
Miembro Premium
 
Registrado: dic 2004
Posts: 882
Reputación: 20
Héctor Randolph Va por buen camino
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')]);
Responder Con Cita