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

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

古典的な問題として、文字列TTの中にパターンPPが最初に現れる位置を見つけるというものがあります。この問題を効率的に解決するためのアルゴリズムには、Boyer-Moore、Knuth-Morris-Pratt、Two-Way など、様々な古典的アルゴリズムがあります。この記事では、あまり知られていないアルゴリズムであるBitapまたはshift-andアルゴリズム[1]について解説します。このアルゴリズムは、パターンPPの長さがマシンワードの幅よりも短い場合に効率的に動作します。その制約にもかかわらず、理解しやすく実装も容易で、短い文字列に対して比較的効率的であり、ビット演算を特にエレガントな方法で使用するため、私はこのアルゴリズムを非常に気に入っています。

このアルゴリズムが主張されているほど概念的に単純であることを示すために、最もナイーブな文字列マッチングアルゴリズムから段階的に導出してみましょう。

Bitapの導出

ナイーブなアルゴリズム

文字列マッチング問題を解決する最も単純な総当たりアルゴリズムは、文字列TTの各可能な位置からパターンPPをマッチさせようと試みるだけです。

// Tの中で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
}

ストリーミング対応にしたナイーブなアルゴリズム

ここで、アルゴリズムを少し変更する動機として、追加の制約を課してみましょう。テキストTTのすべての文字を一度に与えられるのではなく、それらがストリームの形式で、一度に1文字ずつ提供されると仮定します。（おそらくTTは非常に長く、その内容全体を一度にメモリにロードしたくない場合など。）

上記で提示された単純なアルゴリズムはストリーミングではありません。パターンマッチを検出するために、現在のTTの位置から最大m=len(P)文字先まで読み取る必要があります。データを1パスで処理できるように、どのように適応させることができるでしょうか？

少し考えると、総当たりアルゴリズムの以下のバリアントが思い浮かびます。各開始位置 i=0,… からPPの出現を即座に検出するのではなく、TTをスキャンしながら進行中のマッチのセットを維持することができます。概念的には、進行中のマッチは、現在の位置の直前に既にマッチしたパターンPPの接頭辞と、まだマッチしていない残りの接尾辞で構成されます。TTで新しい文字cを読み取るとき、文字cを期待している進行中のマッチを進め、それ以外は破棄します。アクティブなマッチのいずれかがパターンPPの最後まで進んだ場合、完了です。

func matchOnepass(T, P string) int {
	type state struct {
		remaining string // まだマッチしていないPの接尾辞
	}
	var active []state
	for i := range len(T) {
		c := T[i]

		// 常に新しいマッチを開始しようと試みる。
		actve = 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})
			}
		}
		actve = next
	}
	return -1
}

matchOnepassを少し最適化できます。進行中のマッチの状態を、パターンPPで次にマッチさせる文字のインデックスjで表します。（まだマッチしていないPPの接尾辞は P[j:] に対応します。）この単純化により、以下のようになります。

func matchOnepassInt(T, P string) int {
	var active []int // 状態は整数になった
	for i := range len(T) {
		c := T[i]

		actve = append(active, 0) // 新しいマッチを開始しようと試みる
		var next []int
		for _, j := range active {
			if c == P[j] {
				// 進める
				j++
				if j == len(P) {
					// P全体をマッチさせた
					return i - len(P) + 1
				}
			next = append(next, j)
			}
		}
		actve = next
	}
	return -1
}

このアルゴリズムをさらに改善するにはどうすればよいでしょうか？1つの観察結果は、active内の進行中の状態は常に 0 から len(P)（パターンの長さ）までの整数であるということです。PPがあまり長くない場合、activeセットを整数のリストではなく、より効率的に表現する方法があるかもしれません。この考え方が、ビットセットとビット演算を使用して、Bitapアルゴリズムにつながります。

ビット演算

確かに、PPが比較的短い場合、例えば len(P) < 64 であれば、アクティブな状態のセットを単一の整数（64ビットビットセットとして解釈）にパックできます。たとえば、active = {1, 2, 7} の場合、次のようになります。

active_bitset = 0b1000_0110

試してみましょう！

func matchOnepassBitset(T, P string) int {
	var active uint64 // ビットセット
	for i := range len(T) {
		c := T[i]

		actve |= 1 << 0 // ビットセットに0を追加する（新しいマッチを開始しようと試みる）
		var next uint64
		for j := range 64 {
			if active&(1<<j) == 0 {
				continue
			}
			// アクティブセット内の各状態jについて...

			if c == P[j] {
				// 進める
				j++
				if j == len(P) {
					// P全体をマッチさせた
					return i - len(P) + 1
				}
			next |= 1 << j
			}
		}
		actve = next
	}
	return -1
}

うーん。これは大きな改善には見えません。activeがよりコンパクトなエンコーディングを持っているのは良いことですが、まだ2つのネストされたループがあり、どうにかして内側のループを排除できないかという疑問が生じます…

巧妙なビット操作と視点の小さな変更を使用することで、実際にそれを排除できることが判明しました。上記のアルゴリズムでは、各マッチ状態を見て、それが（cとP[j]を比較することによって）継続できるかどうかを確認し、可能であれば1つ進めます。一方、別の方法は、すべてのマッチ状態を無条件に1つ進め、無効な遷移から生じた状態を破棄することです。鍵は、前の方法とは異なり、これらの両方のステップを、ビットセット全体に一度に作用する単一のビット操作で実装できることです。

実際、すべてのマッチ状態を1つ進めるには、1つ左にシフトするだけで十分です：active << 1。残る唯一の課題は、無効な遷移から生じた状態を破棄することです。つまり、next = active << 1 が与えられた場合、文字 c を観察した後に実際に進むべき状態のみを保持したいのです。2番目の、そして最後の洞察は、パターンに出現する各文字に対して、文字 c を観察した後に発生しうる有効な状態のビットセットを事前に計算し、適切なビットセットと交差させることでこれを達成できるということです。

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]

		actve |= 1 << 0 // 新しいマッチを開始しようと試みる
		next := (active << 1) & validMask[c] // 状態を進め、無効な遷移をマスクする
		if next&(1<<len(P)) != 0 {
			// P全体をマッチさせた！
			return i - len(P) + 1
		}
		actve = next
	}
	return -1
}

ついに、shift-andまたはBitapアルゴリズム（<< 1でシフトし、次に& validMask[c]でANDを取ることから名付けられました）にたどり着きました！

典型的な提示方法では、インデックスの規則が1つずれており、実際にはより適切ですが、精神は同じであり、私の規則はこのブログをより自然に流れるようにします。また、すべてのビットマスクを反転させ、ビットANDの代わりにビットORを使用する、より効率的なバリアントであるshift-orもあります。これは、入力文字あたり1つのビット演算が少なくなります。

だから何？

冒頭で述べたように、Bitapアルゴリズムはパターンが比較的短い場合にのみ真に輝きます。理論的にはより長いパターンに一般化できますが（マルチワードビットセットを使用することによって）、パフォーマンスの向上は低下し始めます。さらに、漸近的には、パターンの長さが定数に制限されている場合、Bitapの実行時間はナイーブな総当たりアルゴリズムと同じ（どちらもテキストTTの長さに線形）になります。そして実際には、必要な事前計算のために、1回限りのテストではナイーブなアルゴリズムよりもパフォーマンスが悪くなる可能性があります。

これらの制限を考慮すると、なぜ私はBitapを気に入っているのでしょうか？私は、それが概念的に非常にエレガントで、ナイーブなアルゴリズムから導出するのが簡単だと考えています。上記で説明したように、入力文字列をステップ実行しながらアクティブな状態のセットを維持し、ビット演算を使用して高速化します。Boyer-MooreやKMPについても詳細に学習しましたが、それらをゼロから導出するにはかなりの時間がかかります[2]が、Bitapは非常に簡単に導出できます。私にとっては、それは単に異なるように装飾されたナイーブなアルゴリズムだからです。この記事を読んだ後、皆さんも同じように感じてくれることを願っています。

---

1. ここで私が言及しているのは厳密な文字列マッチングアルゴリズムであることに注意してください。「Bitapアルゴリズム」は、レーベンシュタイン距離の点でファジーマッチングをサポートするバリアントを指すこともありますが、それはこの投稿の主題ではありません。↩︎
2. そして、Two-Wayアルゴリズムをゼロから導出できればと願うばかりです。それがどのように機能するかさえ理解していません。↩︎