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

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

快速而紧凑的实现。

大约是使用普通字符串的粉碎机实现速度的 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)，内联实际上会稍微慢一点。