{
说明 LD(s,t:WideString):Integer 返回两个字符串的编辑长
D= 编辑长
L = 字符串中最长串的长度，当L=0时，L取1
两个字符串的相似度=1 – D / L , 区间在0~1之间，0表示不相似，1表示完全相同
}
unit LDA;
{Levenshtein Distance Algorithm}
interface
function LD(s,t:WideString):Integer;
implementation
function Minimum(a,b,c:Integer):Integer;
begin
Result:=a;
if b<Result then Result:=b;
if c<Result then Result:=c;
end;
function LD(s,t:WideString):Integer;
var
d:array of array of Integer;
n,m:Integer;
i,j:Integer;
s_i,t_j:WideChar;
cost:Integer;
begin
n:=Length(s);
m:=Length(t);
if n=0 then
begin
Result:=m;
Exit;
end;
if m=0 then
begin
Result:=n;
Exit;
end;
//数据初始化
SetLength(d,n+1);
for i:= 0 to n do SetLength(d[i],m+1);
for i:= 0 to n do d[i][0]:=i;
for j:= 0 to m do d[0][j]:=j;
//
for i:= 1 to n do
begin
s_i:=s[i];
for j:= 1 to m do
begin
t_j:=t[j];
if s_i=t_j then cost:=0
else cost:=1;
d[i][j]:=Minimum(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+cost);
end;
end;
Result:=d[n][m];
end;
end.
调用代码片断：
var
d,l:Integer;
begin
d:=LD(s.Text,t.Text);
l:=Length(s.Text);
if l<Length(t.Text) then l:=Length(t.Text);
if l=0 then l:=1;
lbResult.Caption:=IntToStr(d);//得到编辑长
lbRes.Caption:=FloatToStr(1-d/l);//计算相似度
end;
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/101189.html原文链接：https://javaforall.net
