18
我在回答你自己的問題的精神發佈這個。如何在Delphi中實現Levenshtein距離?
我的問題是:如何在Delphi中實現用於計算兩個字符串之間編輯距離的Levenshtein算法,如described here?
只是關於性能的說明: 這件事情非常快。在我的桌面上(2.33 Ghz雙核,2GB內存,WinXP),我可以在不到一秒的時間內運行100K字符串。
我在回答你自己的問題的精神發佈這個。如何在Delphi中實現Levenshtein距離?
我的問題是:如何在Delphi中實現用於計算兩個字符串之間編輯距離的Levenshtein算法,如described here?
只是關於性能的說明: 這件事情非常快。在我的桌面上(2.33 Ghz雙核,2GB內存,WinXP),我可以在不到一秒的時間內運行100K字符串。
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;
清理部分不需要,甚至可能會損害性能。當函數退出時,動態數組將被Delphi解除分配。 – kobik 2012-05-14 10:20:19
傑夫已經鼓勵他回答自己的問題。這不僅是一個查詢平臺,而且是一個尋找答案的平臺。他們來自誰 - 誰在乎。做得好。 – 2008-09-11 05:18:07