シフタアルゴリズム
ビット演算を利用した単純で高速なパタンマッチアルゴリズム 特徴
最小限のメモリで高速に検索できる
検索文字列長の制限あり
曖昧検索にも拡張できる
例
アクティブな状態の遷移
「restaurant」というパタンを認識する状態遷移機械は「restaurant」を認識する状態遷移機械.iconのように表現できる。ここで、灰色のノードはアクティブな状態を示している。 最初は左端のノードだけがアクティブになっているが、「r」を認識すると二番目のノードもアクティブになり、「r」を認識した後の状態.iconに遷移する。
「restaurant」を認識すると、状態は「restaurant」を認識した後の状態.iconのように変化する。
シフタアルゴリズムではノードのアクティブ状態をビットパタンで表現する。「restaurant」を認識する状態遷移機械.iconは10000000000と表現し、「restaurant」認識後の「restaurant」を認識した後の状態.iconは10000000001 と表現する。
この状態遷移機械は非決定性であるが、状態の表現に10 ビットしか必要としないため、状態をひとつの整数値で表現できることに加え、状態遷移を簡単な論理積演算とシフト演算だけで高速に計算できるという特徴がある。 Reference