Bitapはなぜ美しいのか、素朴なアルゴリズムから導出する
Bitap: My favorite string matching algorithm
Boyer-MooreやKMPほど知られていないbitap（shift-and）アルゴリズムを、素朴な実装から段階的に導出。ストリーミング化、ビットセット化を経て、シフトとマスクだけでマッチ状態を一括更新する仕組みを明らかにする。短いパターンに限定されるが、その簡潔さと導出のしやすさが魅力だと著者は語る。
Boyer-MooreやKMPを詳細に学んだけれど、それらをゼロから導出するにはかなり時間がかかる。一方bitapはとても簡単に導出できる。私にとっては、単に素朴なアルゴリズムを別の装いで着せただけなのだ。
HNでの議論
10- Rendello
私もお気に入りの文字列マッチングアルゴリズムがあって、Wojciech Mułaによるこの投稿[1]の「Generic SIMD」だ（他の2つのSIMDアルゴリズムは、intrinsicsを使う予定がなかったのでちゃんと読んでいない）。
あの投稿のスレッド[2]には、ripgrepのburntsushiからのものも含めて、良いコメントがいくつかあった。
- MattPalmer1086
ああ、先週末ちょうど、パターン長が64未満のときにKMPの代わりにBitap（Shift-OR変種）を使うように自分の文字列検索アルゴリズムを更新していたところだ。速いんだ。本当に素晴らしいアルゴリズムだね。
私の検索アルゴリズムHashChain [1]は非常に高速な準線形アルゴリズムだが、マッチの検証にKMP（そして今はBitap）を使っているので、最悪計算量が線形になる（Boyer Moore Horspoolのように二次ではない）。
- MattPalmer1086
これはBitapを第一原理から本当にうまく導出しているね。そんなのは初めて見た。よくやった！
一つ小さなツッコミ：彼はナイーブアルゴリズムが線形だと言っているが、それは平均ケースではそうかもしれないが、最悪計算量は二次だ。Bitapは最悪ケースでも線形だ。