如何计算两个字符串之间的差异？

Question

我想在Delphi中创建一个计算不同级别的两个字符串的函数。如果两个字符串相等（忽略大小写），那么它应该返回0，但如果它们不相等，它应该返回不同字符的数量。此功能对检查拼写非常有用。

function GetDiffStringLevel(S1,S2:string):Integer; 
begin 
    if SameText(S1,S2) then Exit(0); 
    // i want get different chars count 
end 

样本代码：

Diff:=GetDiffStringLevel('Hello','Hello');// Diff:=0; 
Diff:=GetDiffStringLevel('Hello','2Hello');// Diff:=1; 
Diff:=GetDiffStringLevel('Hello','H2ello');// Diff:=1; 
Diff:=GetDiffStringLevel('Hello','Hello W');// Diff:=2; 
Diff:=GetDiffStringLevel('Hello','World');// Diff:=6; or 5 

Answer 1

快速和紧凑的实现。

使用普通字符串大约是smasher实现的3倍。 如果其中一个字符串为空，则速度会超过100倍。

虽然Smasher的函数不区分大小写，但也可以使用。

function LevenshteinDistance(const s, t: string): integer;inline; 
var 
    d : array of array of integer; 
    n, m, i, j : integer; 
begin 
    n := length(s); 
    m := length(t); 
    if n = 0 then Exit(m); 
    if m = 0 then Exit(n); 

    SetLength(d, n + 1, 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 
    for j := 1 to m do 
     d[i, j] := Min(Min(d[i-1, j]+1, d[i,j-1]+1), d[i-1,j-1]+Integer(s[i] <> t[j])); 

    Result := d[n, m]; 
end; 

注：inline指令减少了执行时间，以低于70％我的机器上，但只能用于Win32目标平台。如果你编译为64位（Delphi XE2），内联实际上会让它慢一点。

Answer 2

你想被称为编辑的Levenshtein distance（最小数目，将一个字符串转换成另一个，其中一个编辑或者是一个字符插入，字符删除什么或字符替换）。维基百科网站有一个伪代码实现。

Delphi实现：

function LevenshteinDistance(String1 : String; String2 : String) : Integer; 

var 
    Length1, Length2  : Integer; 
    WorkMatrix   : array of array of Integer; 
    I, J     : Integer; 
    Cost     : Integer; 
    Val1, Val2, Val3  : Integer; 

begin 
String1 := TCharacter.ToUpper (String1); 
String2 := TCharacter.ToUpper (String2); 
Length1 := Length (String1); 
Length2 := Length (String2); 
SetLength (WorkMatrix, Length1+1, Length2+1); 
for I := 0 to Length1 do 
    WorkMatrix [I, 0] := I; 
for J := 0 to Length2 do 
    WorkMatrix [0, J] := J; 
for I := 1 to Length1 do 
    for J := 1 to Length2 do 
    begin 
    if (String1 [I] = String2 [J]) then 
     Cost := 0 
    else 
     Cost := 1; 
    Val1 := WorkMatrix [I-1, J] + 1; 
    Val2 := WorkMatrix [I, J-1] + 1; 
    Val3 := WorkMatrix[I-1, J-1] + Cost; 
    if (Val1 < Val2) then 
     if (Val1 < Val3) then 
     WorkMatrix [I, J] := Val1 
     else 
     WorkMatrix [I, J] := Val3 
    else 
     if (Val2 < Val3) then 
     WorkMatrix [I, J] := Val2 
     else 
     WorkMatrix [I, J] := Val3; 
    end; 
Result := WorkMatrix [Length1, Length2]; 
end;