Tüm Platformlar için Hızlı Uygulama Geliştirme --->    Kitabımız...      Delphi

Konuyu Paylaş : facebook gplus twitter

Konuyu Oyla:
  • Derecelendirme: 5/5 - 1 oy
  • 1
  • 2
  • 3
  • 4
  • 5
Levenshtein Distance Algoritması (string karşılaştırma)
#1
İ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.
Levenshtein.jpg

Konu ile ilgili detaylı bilgi:
Linkleri Görebilmeniz İçin Giriş yap veya Üye Ol


Levenshtein Distance Algoritmasının Delphi için uyarlanmış hali: 
Linkleri Görebilmeniz İçin Giriş yap veya Üye Ol

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:
 Linkleri Görebilmeniz İçin Giriş yap veya Üye Ol
 Linkleri Görebilmeniz İçin Giriş yap veya Üye Ol
 }

 //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:
1f2cc296a5.png
Cevapla

Konuyu Paylaş : facebook gplus twitter





Konuyu Okuyanlar: 1 Ziyaretçi