8

Boyer-Moore 文字列検索アルゴリズムのシフト ルールを理解しようとしてきましたが、理解できませんでした。私はウィキペディアでここを読みましたが、それは複雑すぎます!

誰かがルールを簡単な方法でリストアップしてくれると、非常に役に立ちます。

4

3 に答える 3

16

Boyer-Moore アルゴリズムでは、パターンの末尾からパターン文字とテキスト文字の比較を開始します。不一致が見つかった場合は、タイプの構成があります

....xyzabc....      <-text
  ....uabc          <- pattern
      ^
    mismatch

ここで、不良文字シフトとは、不一致のテキスト文字が、パターンの最初の部分 (パターンから最後のパターン文字を差し引いたもの) でその文字が最後に出現する場合に位置合わせされるようにパターンをシフトすることを意味します。不一致の文字がパターンの最初の部分にまったく表示されない場合は、パターンの 1 つ前の位置。

状況が次の場合、それは左へのシフトである可能性があります。

     v
...xyzazc...
 ....uazc
 ..uazc

それだけでは進歩を保証するものではありません。

もう 1 つのシフトである適切な接尾辞 shiftは、テキストの一致部分 をm、パターン内のその文字シーケンスの右端にある別の文字 (一致した接尾辞が接尾辞の接頭辞でもある場合は、なしを含む) が前にある位置に揃えます。パターン) 一致したパターンのサフィックスよりもm- そのような出現がある場合。

たとえば

           v
....abcdabceabcfabc...
    ...xabcfabcfabc
        ...xabcfabcfabc

一致した部分m = abcfabcは、そのサフィックスオカレンスの左の 4 つのパターンで発生し、サフィックス位置とは異なる文字 (xの代わりにf) が先行するため、4 桁の適切なサフィックスシフトにつながります。

接尾辞とは異なる文字が前にあるパターンに一致部分が完全に出現しない場合、適切な接尾辞シフトは、テキストの一致部分の接尾辞をパターンの接頭辞に揃え、最大の重複を選択します。

      v
...robocab....
    abacab
        abacab

適切なサフィックス シフトは常にパターンを右にシフトするため、進行が保証されます。

次に、不一致があるたびに、悪い文字のシフトと良い接尾辞のシフトの進行が比較され、大きい方が選択されます。ここでは、Christian Charras と Thierry Lecroq によって、他の多くの文字列検索アルゴリズムとともに、より詳細に説明されています。

コメントで言及した例については、

SSIMPLE EXAMPLE
EXAMPLE
  ^

一致する接尾辞はMPLEで、一致しないテキスト文字はIです。Iしたがって、悪い文字シフトは、パターンの最初の部分で最後に出現する を探します。何もないので、悪い文字シフトがパターンをシフトして、不一致Iがパターンの開始前の 1 つになるようにします。

SSIMPLE EXAMPLE
   EXAMPLE

MPLE適切なサフィックス シフトは、パターン内でが前に付いていないの右端のオカレンス、またはそのパターンのプレフィックスであるA最も長いサフィックスを探します。MPLEパターン内のサフィックスの前に一致部分が完全に出現するわけではないため、パターンのプレフィックスでもある一致部分の最長のサフィックスによって、適切なサフィックス シフトが決定されます。この場合、パターンのプレフィックスである一致部分の 2 つのサフィックスは、1 文字の文字列Eと空の文字列です。最長は明らかに空でない文字列であるため、適切なサフィックス シフトはE、テキストの一致部分の 1 文字のサフィックスをパターンの 1 文字のプレフィックスに揃えます。

SSIMPLE EXAMPLE
      EXAMPLE

適切なサフィックス シフトは、パターンをさらに右にシフトするため、それが選択されたシフトです。

次に、パターンの最後の位置ですぐに不一致が発生し、悪い文字シフトPによってテキストP内の がパターン内の に揃えられます (パターンの最後の文字で不一致が発生した場合、適切な接尾辞のシフトをまったく考慮する必要はありません。その場合、悪い文字のシフトよりも大きなシフトを生成することはないためです)。

次に、完全な一致があります。

pattern のバリアントではTXAMPLE、適切なサフィックス シフトにより、一致した部分の空でないサフィックスがパターンのプレフィックスではないことがわかります (また、パターン内で が前にないA完全な一致した部分は発生しません)。 suffix shift は、テキストの一致部分 (Eとスペースの間の境界) の空のサフィックスをパターンの空のプレフィックス ( の前の空の文字列T) に揃えます。

SSIMPLE EXAMPLE
       TXAMPLE

(その後、次のステップで、不良文字シフトによって 2 つLの が整列し、その後のステップでの次の不一致がTパターンの先頭で発生します)。

于 2012-11-01T12:09:54.817 に答える
7

ここに良いビジュアライゼーションがあります。

(編集: 例と前処理ステップの実装方法の例の両方を含む非常に良い説明もありますhere .)

一般的なルール：

  • パターンとテキストを揃えて、揃えた部分が一致するようにする方法を探しています。そのような配置が存在しない場合、そのパターンはテキスト内に見つかりません。
  • 各配置を右から左に確認します。つまり、パターンの最後の文字が現在の配置と一致するかどうかを確認することから始めます。
  • 位置合わせされていない文字をヒットした場合は、パターン内のテキスト側の文字の最後の出現が、現在見ているテキスト側の文字のこの出現と位置合わせされるように、オフセットを増やします (パターンをシフトします)。 . これには、パターン内の各文字が存在する場所のインデックスを事前に作成する (または毎回検索しますが、効率は低くなります) 必要があります。
  • テキストで考慮されている文字がパターンに表示されない場合は、パターンの全長分スキップします。
  • パターンの末尾がテキストの末尾からはみ出している場合 (オフセット + 長さ (パターン) > 長さ (テキスト))、パターンはテキストに表示されません。

私が今説明したのは、「悪い性格」のルールです。「適切なサフィックス」ルールは、シフトの別のオプションを提供します。どちらが遠くにシフトしても、あなたが取るべきものです。適切な接尾辞ルールなしでアルゴリズムを実装することは完全に可能ですが、インデックスが構築されると効率が低下します。

適切な接尾辞規則では、パターンの各複数文字の部分文字列を見つける場所も知っている必要があります。不一致にヒットすると (いつものように、右から左にチェックします)、適切な接尾辞のシフトにより、既に一致していた文字が再び一致するポイントにパターンが移動します。あるいは、一致した部分がパターン内で一意である場合は、それをスキップしてスキップできることがわかっています。パターンの他の部分。

たとえば、次の状況を考えてみましょう。

  • 私のパターンは「犬」で終わります。
  • 現在、「s dog」で終わるテキストの一部に合わせています。
  • したがって、悪い文字は 's' (一致を停止する場所) であり、良い接尾辞は "dog" (一致した部分) です。

ここには 2 つのオプションがあります。

  1. パターンの最初の 's' (右から左へ) がテキストの 's' と揃うようにシフトします。パターンに 's' がない場合は、パターンの先頭を 's' の直後に移動します。
  2. 次の「犬」がテキスト内の「犬」と揃うようにシフトします。パターンに別の "dog" がない場合は、パターンの開始を "dog" の終わりの直後に移動します。

そして、私は、より遠くに移動できる方を選択する必要があります。

それでも混乱する場合は、より具体的な質問をしてみてください。どこで立ち往生しているかわからない場合、明確にするのは困難です。

于 2012-11-01T12:08:49.177 に答える
1

ヒューリスティックには、バット シンボル ヒューリスティックとグッド パターン ヒューリスティックの 2 つがあります。

まず、針比較は最後から始まります。そのため、文字がニードル シフトと一致しない場合、干し草の山で少なくとも比較された文字はニードルと一致します。例）針は「ABRACADABRA」で、干し草の山にある現在の文字は「B」です。最後の「A」と一致せず、前の「R」とも一致しないため、1 つシフトしても意味がなく、一致しません。ただし、"B" は針の末尾から 2 番目の文字に一致します。したがって、針を少なくとも 2 位置ずらします。ヘイスタックの現在の文字が針のどの文字とも一致しない場合、針は現在の文字を超えてシフトする必要があります。言い換えれば、ヘイスタックの現在の文字が針の文字と一致するまでパターンをシフトするか、針全体がシフトされるまでパターンをシフトします。

シフト量は計算されて配列に格納されるため、「ABRACADABRA」の場合は ['R'] = 1、['B'] = 2、['D'] = 4 などになります。

haystack: XYABRACADABRA...
                    |
needle:   ABRACADABRA
           ABRACADABRA <-- pointless shift: R will not match B
            ABRACADABRA

第二に、干し草の山で少なくとも「ABRA」の一致が見つかった場合 (ただし、完全な一致はありません)、次の「ABRA」が一致するように針をシフトできます。

一致する部分のシフト量も事前に計算されます。例: ['A'] = 3、['RA'] = 11、['BRA'] = 11、['ABRA'] = 7、['DABRA'] = 7 ...

haystack: XYZYXADABRACADABRA...
needle:   ABRACADABRA           (shift to ABRA from matched ADABRA)
          ~~~~   ~~~~
                 ABRACADABRA

これはすべてのコーナーケースの完全な説明ではありませんが、アルゴリズムの主なアイデアです。

于 2012-11-01T12:17:13.240 に答える