8

OCR で認識されたテキスト内の文字列を一致させる問題に遭遇し、間違った文字、欠落した文字、または余分な文字の任意の許容範囲がある可能性があることを考慮して、その位置を見つけました。結果は、一致する部分文字列の長さで、おそらく (必ずしもそうとは限りませんが) 最適な一致位置になるはずです。

例えば：

String: 9912, 1.What is your name?
Substring: 1. What is your name?
Tolerance: 1
Result: match on character 7

String: Where is our caat if any?
Substring: your cat
Tolerance: 2
Result: match on character 10

String: Tolerance is t0o h1gh.
Substring: Tolerance is too high;
Tolerance: 1
Result: no match

Levenstein アルゴリズムを適用しようとしましたが、部分文字列に対しては適切に機能せず、位置を返しません。

Delphi のアルゴリズムが優先されますが、任意の実装または疑似ロジックでもかまいません。

4

2 に答える 2

8

これは機能する再帰的な実装ですが、十分に高速ではない可能性があります。最悪のシナリオは、一致が見つからず、"What" の最後の文字を除くすべての文字が Where のすべてのインデックスで一致する場合です。その場合、アルゴリズムは、Where の各文字に対して Length(What)-1 + Tolerance 比較を行い、さらに Tolerance ごとに 1 回の再帰呼び出しを行います。Tolerance と What are constnats の長さの両方なので、アルゴリズムは O(n) だと思います。そのパフォーマンスは、「What」と「Where」の両方の長さに比例して低下します。

function BrouteFindFirst(What, Where:string; Tolerance:Integer; out AtIndex, OfLength:Integer):Boolean;
  var i:Integer;
      aLen:Integer;
      WhatLen, WhereLen:Integer;

    function BrouteCompare(wherePos, whatPos, Tolerance:Integer; out Len:Integer):Boolean;
    var aLen:Integer;
        aRecursiveLen:Integer;
    begin
      // Skip perfect match characters
      aLen := 0;
      while (whatPos <= WhatLen) and (wherePos <= WhereLen) and (What[whatPos] = Where[wherePos]) do
      begin
        Inc(aLen);
        Inc(wherePos);
        Inc(whatPos);
      end;
      // Did we find a match?
      if (whatPos > WhatLen) then
        begin
          Result := True;
          Len := aLen;
        end
      else if Tolerance = 0 then
        Result := False // No match and no more "wild cards"
      else
        begin
          // We'll make an recursive call to BrouteCompare, allowing for some tolerance in the string
          // matching algorithm.
          Dec(Tolerance); // use up one "wildcard"
          Inc(whatPos); // consider the current char matched
          if BrouteCompare(wherePos, whatPos, Tolerance, aRecursiveLen) then
            begin
              Len := aLen + aRecursiveLen;
              Result := True;
            end
          else if BrouteCompare(wherePos + 1, whatPos, Tolerance, aRecursiveLen) then
            begin
              Len := aLen + aRecursiveLen;
              Result := True;
            end
          else
            Result := False; // no luck!
        end;
    end;

  begin

    WhatLen := Length(What);
    WhereLen := Length(Where);

    for i:=1 to Length(Where) do
    begin
      if BrouteCompare(i, 1, Tolerance, aLen) then
      begin
        AtIndex := i;
        OfLength := aLen;
        Result := True;
        Exit;
      end;
    end;

    // No match found!
    Result := False;

  end;

次のコードを使用して関数をテストしました。

procedure TForm18.Button1Click(Sender: TObject);
var AtIndex, OfLength:Integer;
begin
  if BrouteFindFirst(Edit2.Text, Edit1.Text, ComboBox1.ItemIndex, AtIndex, OfLength) then
    Label3.Caption := 'Found @' + IntToStr(AtIndex) + ', of length ' + IntToStr(OfLength)
  else
    Label3.Caption := 'Not found';
end;

ケースの場合:

String: Where is our caat if any?
Substring: your cat
Tolerance: 2
Result: match on character 10

長さ 6 の文字 9 での一致を示しています。他の 2 つの例では、期待される結果が得られます。

于 2010-12-07T11:15:29.340 に答える
0

ここにあいまい一致 (近似検索) の完全なサンプルがあり、必要に応じてアルゴリズムを使用/変更できます。 https://github.com/alidehban/FuzzyMatch

于 2020-12-03T23:49:48.527 に答える