ライタアルゴリズム

コンピュータサイエンスにおいて、RaitaアルゴリズムはBoyer–Moore–Horspoolアルゴリズムの性能を向上させる文字列検索アルゴリズムです。このアルゴリズムは、Boyer–Moore文字列検索アルゴリズムと同様に、検索対象の文字列をパターンに基づいて前処理します。与えられた文字列内の特定のサブストリングの検索パターンは、Boyer–Moore–Horspoolアルゴリズムとは異なります。このアルゴリズムは、1991年にTimo Raitaによって発表されました。^{[ 1 ]}

Raitaアルゴリズムは、与えられたテキスト「T」内のパターン「P」の各文字を比較することにより、パターン「P」をテキスト「T」内で検索します。検索は次のように行われます。テキスト「T」のウィンドウは「P」の長さとして定義されます。

1. まず、パターンの最後の文字とウィンドウの右端の文字が比較されます。
2. 一致するものがあれば、パターンの最初の文字がウィンドウの左端の文字と比較されます。
3. 再び一致した場合、パターンの中央の文字とウィンドウの中央の文字を比較します。

事前チェックがすべて成功した場合、元の比較は最後から2番目の文字から開始されます。アルゴリズムのどの段階でも不一致が発生した場合は、前処理フェーズで計算された不良文字シフト関数が実行されます。不良文字シフト関数は、Boyer–Moore–Horspoolアルゴリズムで提案されているものと同じです。^{[ 1 ]}

同様の事前チェックの現代的な定式化はstd::string::find、libc++ および libstdc++ の線形/二次文字列マッチング器である に見られます。 の最適化されたバージョンを想定するとmemcmp、「元の比較」で文字をスキップしない方が、パターンが整列される可能性が高いため、より効率的になる傾向があります。^{[ 2 ]}

パターン: abddb

テキスト: abbaabaabddbabadbb

前処理段階：

 アブド 4 3 1

試行1： abbaabaabddbabadbb ....b 4だけシフトする（bmBc[a]）

パターンの最後の文字とウィンドウの右端の文字を比較します。一致しないため、前処理段階の値に基づいて4だけシフトします。

試行2： abbaabaabddbabadbb AdB 3だけシフトする（bmBc[b]）

ここでは、パターンの最初と最後の文字は一致していますが、真ん中の文字は一致していません。そのため、パターンは前処理段階に応じてシフトされます。

試行3： abbaabaabddbabadbb アブドゥル 3だけシフトする（bmBc[b]）

ここで完全一致が見つかりましたが、アルゴリズムはそれ以上進めなくなるまで続行します。

試行4： abbaabaABDDBabadbb ....b 4だけシフトする（bmBc[a]）

この段階では、4文字分ずらす必要がありますが、パターンを4文字分ずらすことはできません。そのため、アルゴリズムは終了します。大文字で表記されている文字は、テキスト内のパターンと完全に一致しています。

1. 前処理段階にはO(m)の時間がかかります。ここで「m」はパターン「P」の長さです。
2. 検索段階の時間計算量はO(mn)で、ここで「n」はテキスト「T」の長さです。

• ボイヤー・ムーア文字列検索アルゴリズム
• ボイヤー・ムーア・ホースプールアルゴリズム

• Raitaアルゴリズムのアプレットアニメーションと説明