ボイヤー・ムーア・ホースプールアルゴリズム

コンピュータサイエンスにおいて、ボイヤー・ムーア・ホースプールアルゴリズム、またはホースプールアルゴリズムは、文字列内の部分文字列を見つけるためのアルゴリズムです。これは、1980年にナイジェル・ホースプールによって簡略化ボイヤー・ムーア（SBM）として発表されました。^{[ 1 ]}

これは、クヌース・モリス・プラットアルゴリズムに関連するボイヤー・ムーア文字列検索アルゴリズムの簡略化です。このアルゴリズムは、ランダムテキストに対して平均計算量がO(n)となるように空間計算量を時間計算量と交換していますが、最悪の場合、パターン長がm、検索文字列長がnの場合にはO(nm)となります。

Boyer–Mooreと同様に、Boyer–Moore–Horspoolはパターンを前処理して、アルファベットの各シンボルについて、安全にスキップできる文字数を含むテーブルを生成します。前処理フェーズは、擬似コードで次のように表されます（アルファベットが256シンボル、つまりバイトの場合）。

// オリジナルとは異なり、ここではゼロベースのインデックスを使用します。function preprocess ( pattern ) T := 256 個の整数の新しいテーブルfor i from 0 to 256 exclusive T [ i ] := length ( pattern ) for i from 0 to length ( pattern ) - 1 exclusive T [ pattern [ i ]] := length ( pattern ) - 1 - i return T

パターン検索は次のように進行します。手順検索では、 「needle in haystack」の最初の出現箇所のインデックスが報告されます。

// 2 つの文字列を、最初の len 文字まで比較します。// 注: これは !memcmp(str1, str2, len) と同等です。function same ( str1 , str2 , len ) i := len - 1 // 元のアルゴリズムはここで賢く動作しようとします。// 最後の文字、次に最後から 2 番目の文字などをチェックします。 while str1 [ i ] == str2 [ i ] if i == 0 return true i := i - 1 return falsefunction search ( needle , haystack ) T := preprocess ( needle ) skip := 0 // haystack[skip:] はインデックス `skip` から始まる部分文字列を意味します。C 言語では &haystack[skip] になります。while length ( haystack ) - skip >= length ( needle ) if same ( haystack [ skip : ] , needle , length ( needle )) return skip skip := skip + T [ haystack [ skip + length ( needle ) - 1 ]] return - 1

このアルゴリズムは、長いニードル文字列に対して最も優れたパフォーマンスを発揮します。これは、干し草の山の現在の位置の最後のバイトまたはその付近で、一致しない文字に一貫して遭遇し、かつニードルの最後のバイトがニードル内の他の場所に存在しない場合に特に当てはまります。例えば、「z」で終わる32バイトのニードルが、「z」バイトを含まない255バイトの干し草の山を検索する場合、最大224バイトの比較が必要になります。

最良のケースは、ビッグオー記法のボイヤー・ムーア文字列検索アルゴリズムと同じですが、初期化と各ループの定数オーバーヘッドは少なくなります。

最悪のケースは、不正文字スキップが常に低い値（下限値1バイトの移動）で、ニードルの大部分がヘイスタックと一致する場合に発生します。不正文字スキップが低いのは、部分一致の場合のみで、ニードルの最後の文字がニードル内の他の場所にも出現し、最後の2つの位置の両方に同じバイトが存在する場合に1バイトの移動が発生します。

上記の「最良」ケースに類似した典型的な退化ケースは、255個の「z」バイトからなる干し草の山の中に、「a」バイトの針とそれに続く31個の「z」バイトが存在する場合です。この場合、31回のバイト比較が成功し、1回のバイト比較が失敗して1バイト先に進みます。このプロセスはさらに223回（255 - 32）繰り返され、合計のバイト比較回数は7,168回（32 × 224）になります。（異なるバイト比較ループでは、動作が異なります。）

最悪のケースは、Boyer–Moore文字列検索アルゴリズムの場合よりもかなり高い値を示しますが、通常の使用状況ではこのような値になるのは明らかに困難です。また、この最悪のケースは、単純な（しかし一般的な）memcmp()アルゴリズムの場合にも最悪のケースとなる点にも注目すべきです。ただし、その実装は大幅に最適化されており（キャッシュにも優しい）、より効率的です。

function same_orig(str1, str2, len) i ← 0 str1[len - 1] = str2[len - 1] の場合、 str1[i] = str2[i] の間、 i = len - 2 の場合、 true を返す i ← i + 1 falseを返す

function same_raita(str1, str2, len) i ← 0 中間 ← 長さ / 2 3つの事前チェック。len ≥ 3 の場合、str[mid] != str2[mid] の場合、 false を 返す。len ≥ 1 の 場合、 str[0] != str2[0] の場合、 false を返す。len ≥ 2 の 場合、 str[len - 1] != str2[len - 1] の場合、 falseを返す。任意の比較ループ。 len < 3またはSAME(&str1[1], &str2[1], len - 2)を返します。

• アルゴリズムの説明
• V8 JavaScriptエンジンのC++による実装