この記事は、大部分または全てを単一の情報源に依拠しています。関連する議論は ( 2015年10月) |
| クラス | 部分文字列検索 |
|---|---|
| データ構造 | 弦 |
| 最悪の場合の パフォーマンス | |
| 平均的な パフォーマンス |
コンピュータサイエンスにおいて、ボイヤー・ムーア・ホースプールアルゴリズム、またはホースプールアルゴリズムは、文字列内の部分文字列を見つけるアルゴリズムです。1980年にナイジェル・ホースプールによって簡易ボイヤー・ムーア（SBM）として発表されました。[1]
これは、Knuth-Morris-Prattアルゴリズムに関連するBoyer-Moore文字列検索アルゴリズムの簡略化です。このアルゴリズムは、ランダムテキストに対して平均的なケースでO(n)の計算量を達成するために空間を犠牲にしていますが、最悪のケースではO(nm)（パターンの長さがm、検索文字列の長さがn）となります。
説明
ボイヤー・ムーアと同様に、ボイヤー・ムーア・ホースプール法はパターンを前処理し、アルファベットの各記号について安全にスキップできる文字数を含む表を作成します。この前処理段階は、擬似コードで次のように記述されます（アルファベットが256記号、つまりバイトの場合）。
// オリジナルとは異なり、ここでは 0 ベースのインデックスを使用します。
function preprocess ( pattern ) T := 256 個の整数の新しいテーブルfor iは0から256までしか含みませんT [ i ] := length ( pattern ) for i は0からlength ( pattern ) - 1 までしか含みませんT [ pattern [ i ]] := length ( pattern ) - 1 - i return T
パターン検索は以下のように進行します。search 手続きは、haystack内でneedleが最初に出現するインデックスを報告します。
// 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 false
function 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 := skip + T [ haystack [ skip + length ( needle ) - 1 ]] return - 1
パフォーマンス
このアルゴリズムは、長いニードル文字列で最も高いパフォーマンスを発揮します。つまり、干し草の山の現在位置の最終バイトまたはその付近で一致しない文字が連続して出現し、かつ、そのニードルの最終バイトがニードル内の他の場所に出現しない場合です。例えば、末尾が「z」である32バイトのニードルを、255バイトの干し草の山に「z」バイトが含まれない状態で検索する場合、最大224バイトの比較が必要になります。
最良のケースは、ビッグ O 表記法の Boyer-Moore 文字列検索アルゴリズムの場合と同じですが、初期化と各ループの一定のオーバーヘッドは少なくなります。
最悪の動作は、不正文字のスキップが常に低く（移動の下限は1バイト）、ニードルの大部分が干し草の山と一致する場合に発生します。不正文字のスキップが低くなるのは、ニードルの最後の文字がニードル内の他の場所にも出現し、最後の2つの位置の両方に同じバイトがある場合に1バイトの移動が発生する部分一致のときのみです。
上記の「最良の」ケースに類似した標準的な退化ケースは、255個の「z」バイトからなる干し草の山の中に「a」バイトの針があり、その針に続いて31個の「z」バイトが続くというものです。この場合、31回のバイト比較が成功し、1バイトの比較が失敗して1バイト進みます。このプロセスはさらに223回（255 − 32）繰り返され、合計バイト比較は7,168回（32 × 224）になります。（バイト比較ループが異なると、動作は異なります。）
最悪のケースでは、ボイヤー・ムーアの文字列検索アルゴリズムよりも大幅に高い値となりますが、通常の使用例ではこれを達成するのは明らかに困難です。また、この最悪のケースは、単純な（しかし一般的な）memcmp()アルゴリズムでも最悪のケースとなる点にも注目すべきです。ただし、単純なアルゴリズムの実装は大幅に最適化される傾向があり（キャッシュとの親和性も向上しています）、この点も考慮する必要があります。
比較ループの調整
元のアルゴリズムはより洗練されたsame()ループを使用していました。これは、正方向に進む前に追加の事前チェックを使用します。[1]
関数same_orig(str1, str2, len)
私 ← 0
str1[len - 1] = str2[len - 1]
の場合、 str1[i] = str2[i]
の場合、 i = len - 2 の
場合はtrue を返します。
私 ← 私 + 1
false
を返す
BMHアルゴリズムの調整版として、Raitaアルゴリズムがあります。このアルゴリズムでは、中間文字のチェックを、最後、最初、中間文字の順に行う追加の事前チェックが追加されています。このアルゴリズムは、チェックに合格した場合にのみ、完全なループ処理に入ります。[2]
関数same_raita(str1, str2, len)
私 ← 0
ミッド ← レン / 2
3つの事前チェック。if
len ≥ 3
if str[mid] != str2[mid]
return false
if len ≥ 1
if str[0] != str2[0]
return false
if len ≥ 2
if str[len - 1] != str2[len - 1]
return false
従来の比較ループ。len
< 3またはSAME(&str1[1], &str2[1], len - 2)
を返します。
この1992年のチューニングが、現代のマシンでも依然としてパフォーマンス上の優位性を維持しているかどうかは不明です。著者らの論拠は、実際のテキストには通常、これらの3文字で効果的に事前フィルタリングできるパターンが含まれているというものです。Raita氏は、古い最後の文字の事前チェックを認識していないようです（彼は、後方参照のみのsameルーチンがHorspoolの実装であると信じていました）。そのため、読者は結果を鵜呑みにしないようお勧めします。[2]
現代のマシンでは、 memcmpのようなライブラリ関数は、手書きの比較ループよりも優れたスループットを提供する傾向があります。libstdc++とlibc++の両方における「SFC」ループ（Horspoolの用語）の挙動は、データのアライメントに悪影響を与えるため、現代のRaita実装では1文字シフトを含めるべきではないことを示唆しているようです。[3] [4]また、他の文字列検索アルゴリズムの詳細な分析については、 「文字列検索アルゴリズム」も参照してください。
参考文献
- ^ ab Horspool, RN (1980). 「文字列における実用的な高速検索」.ソフトウェア：実践と経験. 10 (6): 501– 506. CiteSeerX 10.1.1.63.3421 . doi :10.1002/spe.4380100608. S2CID 6618295.
- ^ ab Raita, Timo (1992). 「Boyer-Moore-Horspool 文字列検索アルゴリズムのチューニング」.ソフトウェア: 実践と経験. 22 (10): 879– 884. doi :10.1002/spe.4380221006. S2CID 14193323.
- ^ 「⚙ D27068 string::find の改善」。LLVMコードレビュー。
- ^ "[PATCH] 文字列検索アルゴリズムの改善". GCC .
外部リンク
- アルゴリズムの説明
- C++で書かれたV8 JavaScriptエンジンからの実装
