Bitap: 私のお気に入りの文字列マッチングアルゴリズム

古典的な問題は、文字列Tの中でパターンPの最初の出現箇所を見つけることです。この問題を効率的に解決するためのアルゴリズムには、Boyer-Moore、Knuth-Morris-Pratt、Two-Wayなど、さまざまな古典的なアルゴリズムがあります。この記事では、あまり知られていないアルゴリズム、BitapまたはShift-andアルゴリズムについて解説したいと思います。このアルゴリズムは、パターンPが比較的短い場合（マシンワードの幅未満）に効率的に動作します。その制約にもかかわらず、理解と実装が容易で、短い文字列に対して比較的効率的であり、ビット演算を特にエレガントな方法で使用するため、私はこのアルゴリズムを非常に気に入っています。このアルゴリズムが主張されているほど概念的に単純であることを示すために、最も単純な文字列マッチングアルゴリズムから段階的に導出してみましょう。 最も単純なアルゴリズム 文字列マッチング問題を解決するための最も単純な総当たりアルゴリズムは、文字列Tの可能なすべての開始位置からパターンPを一致させようとするだけです。 ```go // Tのi番目の位置から始まるパターンPを見つける最初のインデックスiを返します。 // 見つからない場合は-1を返します。 // // パターンPは空でないことが要求されます。 func match(T, P string) int { outer: // 文字列Tの各位置 i = 0, ... から開始して... for i := range len(T) - len(P) + 1 { // パターンPを1文字ずつ一致させようとします... for j := range len(P) { // ミスマッチが発生した場合、次の開始位置に進みます。 if T[i+j] != P[j] { continue outer } } return i } return -1 } ``` 最も単純なアルゴリズム、ストリーミング対応版に ここで、アルゴリズムを少し変更する動機として、追加の制約を課してみましょう。テキストTのすべての文字を一度に与えられるのではなく、それらが文字ごとにストリームとして提供されると仮定します。（おそらくTは非常に長く、その内容全体を一度にメモリにロードしたくない場合。）上記で提示された単純なアルゴリズムはストリーミングではありません。パターンの一致を検出するために、現在のTの位置から最大m = len(P)文字先まで読み取る必要があります。どのように適応すれば、データの一回のパスだけで処理できるでしょうか？少し考えれば、総当たりアルゴリズムの以下のバリアントが思いつきます。各開始位置i = 0, ...からTを先読みして一致を検出するのではなく、Tをスキャンしながら進行中のマッチのセットを維持することができます。概念的には、進行中のマッチは、現在の位置の直前にすでに一致したパターンPの接頭辞と、まだ一致していない残りの接尾辞で構成されます。Tで新しい文字cを読み取るとき、文字cを期待している進行中のマッチを進め、残りを破棄します。アクティブなマッチのいずれかがパターンPの最後まで進んだ場合、完了です。 ```go func matchOnepass(T, P string) int { type state struct { remaining string // Pのまだ一致していない接尾辞 } var active []state for i := range len(T) { c := T[i] // 常に新しいマッチを開始しようとします。 act ive = append(active, state{remaining: P}) var next []state for _, m := range active { if c == m.remaining[0] { // この進行中のマッチを1つ進めます。 remaining := m.remaining[1:] if remaining == "" { // P全体が一致しました。最後の文字は位置iに出現します。 // 最初の文字は |P| - 1 だけ左に出現します。 return i - len(P) + 1 } next = append(next, state{remaining}) } } act ive = next } return -1 } ``` matchOnepassを少し最適化できます。進行中のマッチの状態を、パターンPで次に一致させるべき文字のインデックスjで表すことによって。（まだ一致していないPの接尾辞はP[j:]に対応します。）この単純化により、以下のようになります。 ```go func matchOnepassInt(T, P string) int { var active []int // 状態は整数になりました for i := range len(T) { c := T[i] act ive = append(active, 0) // 新しいマッチを開始しようとします var next []int for _, j := range active { if c == P[j] { // jを進めます j++ if j == len(P) { // P全体が一致しました return i - len(P) + 1 } next = append(next, j) } } act ive = next } return -1 } ``` このアルゴリズムをさらに改善するにはどうすればよいでしょうか？1つの観察として、active内の進行中の状態は常に0からlen(P)（パターンの長さ）までの整数になります。Pがあまり長くない場合、整数のリストの代わりにアクティブなセットを表すより効率的な方法があるかもしれません。このアイデアが、ビットセットとビット演算を使用した次の変更につながり、Bitapアルゴリズムが生まれます。 ビット演算 確かに、Pが比較的短い場合、例えばlen(P) < 64であれば、アクティブな状態のセットを単一の整数（64ビットビットセットとして理解）にパックできます。たとえば、active = {1, 2, 7}の場合、active_bitset = 0b1000_0110となります。試してみましょう！ ```go func matchOnepassBitset(T, P string) int { var active uint64 // ビットセット for i := range len(T) { c := T[i] act ive |= 1 << 0 // ビットセットに0を追加します（新しいマッチを開始しようとします） var next uint64 for j := range 64 { if active&(1<<j) == 0 { continue } // アクティブセット内の各状態jについて... if c == P[j] { // jを進めます j++ if j == len(P) { // P全体が一致しました return i - len(P) + 1 } next |= 1 << j } } act ive = next } return -1 } ``` うーん。それは大きな改善には見えません。activeがよりコンパクトなエンコーディングを持っているのは良いことですが、まだ2つのネストされたループがあり、どうすれば内側のループを排除できるかという疑問が生じます…巧妙なビット演算と視点の小さな変更を使用することで、実際にそれを実行できることが判明しました。上記のアルゴリズムでは、各マッチ状態を見て、それが（cとP[j]を比較することによって）継続できるかどうかを確認し、可能であれば1つ進めます。一方、別の方法は、すべての一致状態を無条件に1つ進め、無効な遷移から生じた状態を破棄することです。鍵は、前の方法とは異なり、これらの両方のステップを、ビットセット全体に一度に作用する単一のビット演算で実装できることです。実際、すべての一致状態を1つ進めるには、1つ左にシフトするだけで十分です：active << 1。残る唯一の課題は、無効な遷移から生じた状態を破棄することです。つまり、next = active << 1が与えられた場合、文字cを観測した後に実際に進むべき状態のみを保持したいのです。2番目かつ最後の洞察は、パターンに出現する各文字に対して、文字cを観測した後に生じうる有効な状態のビットセットを事前に計算し、適切なビットセットと交差させることでこれを達成できるということです。 ```go func matchBitap(T, P string) int { var validMask [256]uint64 // バイトでインデックス付けされたビットマスクのテーブル for j := range len(P) { // cを見た場合、状態j+1に進むことが許可されます // （以前は状態jにあったと仮定します）。 c := P[j] validMask[c] |= 1 << (j + 1) } var active uint64 for i := range len(T) { c := T[i] act ive |= 1 << 0 // 新しいマッチを開始しようとします next := (active << 1) & validMask[c] // 状態を進め、無効な遷移をマスクします if next&(1<<len(P)) != 0 { // P全体が一致しました！ return i - len(P) + 1 } act ive = next } return -1 } ``` ついに、Shift-andまたはBitapアルゴリズム（<< 1シフトし、次にvalidMask[c]と＆（and）するため、このように名付けられました！）にたどり着きました！典型的な提示では、実際にはより適切な、わずかに異なるインデックス規約が使用されていることに言及しますが、精神は同じであり、私の規約はこのブログをより自然に流れるようにします。また、すべてのビットマスクを反転させ、ビットANDではなくビットORを使用する、より効率的なバリアントであるShift-orもあり、入力文字あたり1つのビット演算が少なくなります。