Levenshtein Distance Algoritması (string karşılaştırma)

[delphi-x]

İki stringin dizilimini benzerlik açısından derecelendiren bir algoritmadır. Arama motorlarında ve  imla kontrolü yapan uygulamalarda (MS Word Spell Checking) bu algoritma kullanılmaktadır. Algoritma, Rus bilimadamı Vladimir Levenshtein tarafından 1965 yılında geliştirilmiştir.


Konu ile ilgili detaylı bilgi:
http://www.buraksenyurt.com/post/Levensh...tmasi.aspx


Levenshtein Distance Algoritmasının Delphi için uyarlanmış hali: 
http://stackoverflow.com/questions/54797...-in-delphi

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;

Aduncity kelimesi bir harf eksik ya da yanlış olma ihtimali sonucu tablodaki kelimelerle yakınlık dereceleri: