算法 – 如何在Delphi中实现Levenshtein距离?
发布时间:2020-12-15 10:15:18 所属栏目:大数据 来源:网络整理
导读:我本着回答自己的问题的精神发贴。 我的问题是:如何在Delphi中实现Levenshtein算法来计算两个字符串之间的编辑距离,如described here? 只是一个关于表演的笔记: 这件事非常快。在我的桌面(2.33 Ghz双核,2GB RAM,WinXP)上,我可以在不到一秒钟内运行一
我本着回答自己的问题的精神发贴。
我的问题是:如何在Delphi中实现Levenshtein算法来计算两个字符串之间的编辑距离,如described here? 只是一个关于表演的笔记: 解决方法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; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |