11

2 つの文字列の異なるレベルを計算する関数を Delphi で作成したいと考えています。2 つの文字列が等しい (大文字と小文字を区別しない) 場合は 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
4

2 に答える 2

15

高速でコンパクトな実装。

通常の文字列を使用した smasher の実装よりも約 3 倍高速です。文字列の 1 つが空の場合、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) にコンパイルする場合、インライン化によって実際には少し遅くなります。

于 2012-05-15T03:30:27.653 に答える
9

必要なものは、レーベンシュタイン距離(ある文字列を別の文字列に変換するための編集の最小数であり、編集は文字の挿入、文字の削除、または文字の置換のいずれかです) として知られています。ウィキペディア サイトには、疑似コードの実装があります。

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;
于 2012-05-14T09:01:42.127 に答える