如何计算两个字符串之间的差异？ [英] How can I compute a difference between two strings?

问题描述

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

  function GetDiffStringLevel（S1，S2：string）：Integer; 
 begin 
如果SameText（S1，S2）然后Exit（0）; 
 //我想得到不同的字符数
 end 
  

示例代码： / p>

  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;或5 
  

解决方案

快速紧凑的实施。

大约是smasher实现的正常字符串的3倍。
如果其中一个字符串为空，则超过100倍。

Smasher的函数不区分大小写，这也可以是有用的。 >

 函数LevenshteinDistance（const s，t：string）：integer; inline; 
 var 
 d：整数数组的数组; 
 n，m，i，j：integer; 
 begin 
 n：= length（s）; 
 m：= length（t）; 
如果n = 0，那么Exit（m）; 
如果m = 0，那么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] +整数（s [i] t [j]））; 
 
结果：= d [n，m]; 
结束
  

注意： inline 时间在我的机器上不到70％，但只适用于win32目标平台。如果您编译为64位（Delphi XE2），则内联实际上会使其稍慢一些。

I want to create a function in Delphi that computes different levels of two strings. If two strings are equal (ignoring case), then it should return 0, but if they are not equal, it should return the number of different characters. This function can be very useful for checking spelling.

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

samples code:

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

解决方案

Fast and compact implementation.

About 3 times as fast as smasher's implementation with normal strings. More than 100 times as fast if one of the strings is empty.

Smasher's function is case insensitive though, which can be useful as well.

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;

Note: the inline directive reduces the execution time to less than 70% on my machine, but only for the win32 target platform. If you compile to 64bits (Delphi XE2), inlining actually makes it a tiny bit slower.

这篇关于如何计算两个字符串之间的差异？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！