文字列マッチングのためのボイヤー・ムーアアルゴリズム

前回の記事では、KMPアルゴリズムを紹介しました。

ただし、これは最も効率的なアルゴリズムではなく、実際には広く使用されていません。さまざまなテキスト エディターの「検索」機能 (Ctrl+F) では、主に Boyer-Moore アルゴリズムが使用されます。

Boyer-Moore アルゴリズムは効率的であるだけでなく、独創的に設計されており、理解しやすいものでもあります。このアルゴリズムは、1977 年にテキサス大学の Robert S. Boyer 教授と J Strother Moore 教授によって発明されました。

以下では、ムーア教授自身の例に基づいてこのアルゴリズムを説明します。

1.

文字列が「HERE IS A SIMPLE Examples」で、検索語が「EXAMPLE」であると仮定します。

2.

まず、「文字列」と「検索語」を先頭に揃え、末尾から比較を始めます。

これは非常に賢いアイデアです。末尾の文字が一致しない場合、1 回の比較だけで、最初の 7 文字 (全体) が探しているものではないことが確実にわかるからです。

「S」は「E」と一致しないことがわかります。このとき、 「S」は「不良文字」、つまり一致しない文字と呼ばれます。また、検索語「EXAMPLE」には「S」が含まれていないこともわかりました。つまり、検索語を「S」の後の位置に直接移動できるということです。

3.

さらに最後から始めると、「P」は「E」と一致しないので、「P」は「不正な文字」であることがわかります。ただし、検索語「EXAMPLE」には「P」が含まれています。したがって、2 つの「P」が揃うように、検索語を 2 つ後ろに移動します。

4.

「悪い性格のルール」を要約すると次のようになります。

シフト数 = 不正な文字の位置 - 検索用語内の前の出現

検索語に「不正な文字」が含まれていない場合、最後の出現位置は -1 になります。

「P」を例に挙げてみましょう。これは「悪い文字」として、検索語の 6 番目の位置に表示されます (番号は 0 から始まります)。検索語で最後に表示されたのは位置 4 だったので、6 - 4 = 2 位置後ろにシフトされます。 2 番目のステップの「S」を例に挙げてみましょう。これは 6 番目の位置に表示され、最後に表示されたのは -1 でした (つまり、表示されませんでした)。その後、検索用語全体が 6 - (-1) = 7 位置後ろにシフトされます。

5.

やはり最後から始めると、「E」は「E」と一致します。

6.

最初の数字を比較すると、「LE」は「LE」と一致します。

7.

最初の数字を比較すると、「PLE」は「PLE」と一致します。

#p#

8.

最初の数字を比較すると、「MPLE」は「MPLE」と一致します。この状況を「適切なサフィックス」、つまりすべての末尾が一致する文字列と呼びます。 「MPLE」、「PLE」、「LE」、および「E」はすべて適切な接尾辞であることに注意してください。

9.

前の数字と比較すると、「I」と「A」が一致しないことがわかります。つまり、「私」は「悪い性格」なのです。

10.

「悪い文字のルール」によれば、検索語は 2 - (-1) = 3 桁後ろにシフトする必要があります。問題は、現時点でもっと良い移動方法はあるかということです。

11.

この時点で「適切な接尾辞」が存在することがわかります。したがって、 「適切な接尾辞のルール」を採用することができます。

シフト番号 = 適切な接尾辞の位置 - 検索用語内の前の出現位置

たとえば、文字列「ABCDAB」の最後の「AB」が「適切なサフィックス」である場合。すると、その位置は 5 (0 から始まり、最初の「B」の値を取る) になり、「検索用語の最後の出現位置」は 1 (最初の「B」の位置) になるため、5 - 1 = 4 位置戻り、前の「AB」は次の「AB」の位置に移動します。

別の例を挙げると、文字列「ABCDEF」の「EF」が適切なサフィックスである場合、「EF」の位置は 5 で、最後に出現した位置は -1 (つまり、出現しなかった) であるため、5 - (-1) = 6 位置後ろにシフトされ、つまり、文字列全体が「F」の後の位置に移動されます。

このルールには注意すべき点が 3 つあります。

（１）「良い接尾辞」の位置は最後の文字を基準とする。 「ABCDEF」の「EF」が適切な接尾辞であると仮定すると、その位置は「F」、つまり 5 (0 から始まる) に基づきます。

（2）検索語の中に「好后支」が1回だけ出現する場合、その最後の出現位置は-1になります。たとえば、「EF」は「ABCDEF」に 1 回しか出現しないため、最後の出現位置は -1 (つまり、出現しなかった) になります。

（３）「良い接尾辞」が複数ある場合、最長の「良い接尾辞」を除き、他の「良い接尾辞」の最後の出現位置は先頭でなければならない。たとえば、「BABCDAB」の「良い接尾辞」が「DAB」、「AB」、「B」であると仮定すると、「良い接尾辞」が最後に現れたのはいつでしょうか。答えは、この時点で使用するのに適した接尾辞は「B」であり、その最後の出現は先頭、つまり位置 0 であるということです。このルールは次のように表現することもできます。最長の「適切なサフィックス」が 1 回だけ出現する場合、検索語句は位置計算のために次の形式「(DA)BABCDAB」に書き換えることができます。つまり、「DA」が仮想的に先頭に追加されます。

上の例に戻りましょう。この時点で、すべての「適切な接尾辞」（MPLE、PLE、LE、E）のうち、「EXAMPLE」の「E」だけが先頭にまだ表示されるため、6 - 0 = 6 桁後ろにシフトされます。

12.

ご覧のとおり、「悪い文字ルール」では 3 桁しかシフトできませんが、「良い接尾辞ルール」では 6 桁シフトできます。したがって、ボイヤー・ムーア アルゴリズムの基本的な考え方は、2 つのルールのうち大きい方の値を毎回元に戻すことです。

さらに巧妙なのは、これら 2 つのルールでシフトされる数字の数は検索語句のみに依存し、元の文字列とはまったく関係がないことです。そのため、「悪い文字ルールテーブル」と「良い接尾辞ルールテーブル」を事前に計算して生成することができます。使用する際は、表を参照して比較するだけです。

13.

末尾から比較を続けると、「P」は「E」と一致しないので、「P」は「悪い文字」です。 「悪い文字のルール」によれば、シフトは 6 - 4 = 2 桁です。

14.

最後から少しずつ比較していき、すべてが一致することがわかったら検索は終了します。検索を続行する場合 (つまり、すべての一致を検索する場合)、「適切な接尾辞のルール」に従って、6 - 0 = 6 位置戻ります。つまり、先頭の「E」を末尾の「E」の位置に移動します。

オリジナルリンク: http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html