from Generate and Filter

ビット演算を利用した単純で高速なパタンマッチアルゴリズム

特徴

最小限のメモリで高速に検索できる

検索文字列長の制限あり

曖昧検索にも拡張できる

例

アクティブな状態の遷移

「restaurant」というパタンを認識する状態遷移機械はのように表現できる。ここで、灰色のノードはアクティブな状態を示している。

最初は左端のノードだけがアクティブになっているが、「r」を認識すると二番目のノードもアクティブになり、に遷移する。

「restaurant」を認識すると、状態はのように変化する。

シフタアルゴリズムではノードのアクティブ状態をビットパタンで表現する。は10000000000と表現し、「restaurant」認識後のは10000000001 と表現する。

この状態遷移機械は非決定性であるが、状態の表現に10 ビットしか必要としないため、状態をひとつの整数値で表現できることに加え、状態遷移を簡単な論理積演算とシフト演算だけで高速に計算できるという特徴がある。

Reference