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