¿Cómo se implementa la distancia de Levenshtein en Delphi?

Question

Estoy publicando esto en el espíritu de responder sus propias preguntas.

La pregunta que tenía era: ¿Cómo puedo implementar el algoritmo de Levenshtein para calcular la distancia de edición entre dos cadenas, como described here, en Delphi?

Solo una nota sobre el rendimiento: Esto es muy rápido. En mi computadora de escritorio (2.33 Ghz de doble núcleo, 2 GB de ram, WinXP), puedo ejecutar una matriz de 100 mil cadenas en menos de un segundo.

Answer 1

function EditDistance(s, t: string): integer; 
var 
    d : array of array of integer; 
    i,j,cost : integer; 
begin 
    { 
    Compute the edit-distance between two strings. 
    Algorithm and description may be found at either of these two links: 
    http://en.wikipedia.org/wiki/Levenshtein_distance 
    http://www.google.com/search?q=Levenshtein+distance 
    } 

    //initialize our cost array 
    SetLength(d,Length(s)+1); 
    for i := Low(d) to High(d) do begin 
    SetLength(d[i],Length(t)+1); 
    end; 

    for i := Low(d) to High(d) do begin 
    d[i,0] := i; 
    for j := Low(d[i]) to High(d[i]) do begin 
     d[0,j] := j; 
    end; 
    end; 

    //store our costs in a 2-d grid 
    for i := Low(d)+1 to High(d) do begin 
    for j := Low(d[i])+1 to High(d[i]) do begin 
     if s[i] = t[j] then begin 
     cost := 0; 
     end 
     else begin 
     cost := 1; 
     end; 

     //to use "Min", add "Math" to your uses clause! 
     d[i,j] := Min(Min(
       d[i-1,j]+1,  //deletion 
       d[i,j-1]+1),  //insertion 
       d[i-1,j-1]+cost //substitution 
       ); 
    end; //for j 
    end; //for i 

    //now that we've stored the costs, return the final one 
    Result := d[Length(s),Length(t)]; 

    //dynamic arrays are reference counted. 
    //no need to deallocate them 
end;