こういう仕様の簡潔ビットベクトル実装が欲しい

簡潔ビットベクトル（succinct bit vector）の概念はとてもシンプルですが、いざ実際に使おうとすると実装ごとに大小さまざまな仕様差異があり、思わぬところで悩みます。

この記事は、簡潔ビットベクトルの「仕様」に対する「個人的な要件」を記録したものです。なお、「実装方法」の話題は出てきません。

また、厳密には「rank1」「select1」と書くべきところを、本記事では「rank」「select」と略記しています。

簡潔ビットベクトルとは

簡潔ビットベクトル（succinct bit vector）は、ざっくり言うと「rank と select という操作を高速に実行できるビット列」のことです。

「rank(p)」は「p ビット目より左に、いくつ 1 が立っているか」、
「select(c)」は「c 個目の 1 が何ビット目にあるか」を調べる操作です。

簡潔ビットベクトルはこれらの操作を、定数時間かそれに準ずる時間で実行できます。

簡潔ビットベクトルについての詳しい解説は、以下のリンク先をご参照ください。

• 完備辞書（簡潔ビットベクトル）の解説 - アスペ日記
• 簡潔データ構造 - Wikipedia
• 簡潔データ構造 - 共立出版

簡潔ビットベクトルの用途

簡潔ビットベクトルの応用事例の中で、私が身近に感じているのは「LOUDS トライ」です。

LOUDS（level-order unary degree sequence）は、ビットベクトルを使うことで、限界までデータ量を減らすことができるツリー表現のことです。

かな漢字変換の辞書データなど、「似たような文字列を大量に保持して検索する」場合などに、大きな強みを発揮します。

LOUDS についての詳しい解説も、リンク先をご参照ください。

• 簡潔データ構造 LOUDS の解説（全12回、練習問題付き） - アスペ日記
• 日本語入力を支える技術 | 技術評論社

簡潔ビットベクトルの仕様バリエーション

冒頭でも述べたとおり、簡潔ビットベクトルの仕様には多くのバリエーションがあります。

それらのバリエーションは、大まかには、以下の４つの部分仕様に因数分解できます。

(1) ビット位置が、「0 始まり」か「1 始まり」か
(2) rank(p) の集計範囲として、位置 p を含むか否か
(3) select(c) が最小位置を返すか、最大位置を返すか
(4) 有効範囲外の引数が渡されたときに、エラーとするか否か

簡潔ビットベクトル仕様に対する、個人的な要件

(1) ビット位置は「0 始まり」であってほしい

まず、ビット位置（= ビット列内でのビットのindex）は、「0 始まり」（0-based）であってほしいです。例えば、ビット列「1000 …」における先頭の「1」を、「0 番目のビット」と呼びたいです。

その理由は、私が「配列の添字が 0 から始まるプログラミング言語」を使用しているからです。簡潔ビットベクトルは、配列と同じくらい基礎的なデータ構造であり、配列もビットベクトルも分け隔てなくシームレスに取り扱いたいです。

一方で、計算機科学の分野などでは、配列の添字が「1 から始まる」こと（1-based）がよくあります。簡潔ビットベクトルの研究論文でも、ビット位置が「1 から始まる」ものを見かけることが多い印象です。それらの論文で提案されたアルゴリズムを逐語的に実装したライブラリでは、ビット位置が「1 始まり」になっていることがあります。

そしてこれは私見ですが、この件（0 始まりか、1 始まりか）が、(2) や (3) の仕様バリエーションをも生み出しているように感じます。

(2) rank(p) の集計範囲に、位置 p を含めないでほしい

次に、rank(p) の集計範囲には、位置 p を含めないでほしいです。

つまり、位置 p の「手前」までに存在する 1 の個数を数えてほしいです。

この件は本当に混迷を極めていて、Wikipedia 上の同じ記事の 日本語版 と 英語版 とですら、説明が統一されていません。

当該記事において、rank(x) の集計範囲は k で表されていますが、
日本語版では「k ∈ [0 ... x)」と半開区間（左閉右開）、
　英語版では「k ∈ [0 ... x]」と閉区間になっています。

つまり、
前者（日本語版）の説明では x は集計範囲に含まれず、（= exclusive）
後者　（英語版）の説明では x は集計範囲に含まれます。（= inclusive）

なお、手元にある計算機科学の書籍では「k ∈ [1 ... x]」相当の表現になっています。

この計算機科学の表現（「1 始まり」）をプログラミング言語（「0 始まり」）に持ってくるときに、
集計範囲の長さ（要素数）を維持するように調整すると前者、
集計範囲の開始位置を「1」から「0」に変えるだけだと後者になります。

具体例を挙げると、ビット列「1111」に対し、
前者だと rank(2) は 2（= 範囲 [0, 2) すなわち 0 <= k < 2 にある 1 の個数）を、
後者だと rank(2) は 3（= 範囲 [0, 2] すなわち 0 <= k <= 2 にある 1 の個数）を返します。

これらはただの取り決めに過ぎず、どちらの方式でも一貫した論理を構築できます。ただ、昨今のプログラミング言語の API では範囲指定において終端の index は範囲に含めない（= exclusive）ものが多く、それらと親和性が高いのは前者（「rank(p) の集計範囲には、位置 p を含めない」）です。

また前者を採用した場合、rank(p) を「先頭 p ビットに含まれる 1 の個数」と解釈することができ、このとき配列の添字が「0 から始まる」のか「1 から始まる」のかを気にする必要がありません。

さらに、rank(0) はビット列の中身によらず、必ず 0 になります。

(3) select(c) は、最小位置を返してほしい

冒頭でも述べたとおり、一般的な定義として、「select(c)」は「c 個目の 1 が何ビット目にあるか」を調べる操作です。

例えばビット列「110011」があるときに、2 個目の 1 は先頭から「2番目」、ビット位置でいうと「1」に存在しますから、select(2) には 1 を返してほしいです。

ところで、いくつかの実装を試した中には select(c) の定義が上記とは異なるものも存在しました。具体的には上記のビット列に対する select(2) として 3 を返してくる実装です。

始めはバグかと思ったのですが、そのライブラリのリファレンスに「returns the greatest position that is preceded by the specified number of ones.」と記述されており、意図して「最大位置」を返却しているようでした。

まとめると、select(c) の仕様に対する個人的な要件は、以下のとおりです。

• 引数 c として、ビットの個数（c >= 1）を受け取ってほしい
• select(c) として「c 個目の 1 が何ビット目にあるか」を返してほしい。（先頭を 0ビット目とする）

また、ここまでの要件から導かれることとして、
select(c) が存在するならば rank(select(c)) + 1 == c が成立してほしいです。

例えばビット列「110011」に対し、
select(1) == 0, rank(0) == 0
select(2) == 1, rank(1) == 1
select(3) == 4, rank(4) == 2
select(4) == 5, rank(5) == 3
となり、つまり
rank(select(1)) + 1 == 1
rank(select(2)) + 1 == 2
rank(select(3)) + 1 == 3
rank(select(4)) + 1 == 4
が成立してほしいです。

(4) 有効範囲外の引数が渡されたときの挙動

これは、実装ごとに最もばらつきがある部分です。

rank(p) と select(c) のそれぞれについて、以下のバリエーションがあります。

• 有効範囲外の引数が与えられたら、無難な値を返す
• 有効範囲外の引数が与えられたら、-1 などの無効値を返す
• 有効範囲外の引数が与えられたら、例外を投げてクラッシュする
• 有効範囲外の引数が与えられた場合の動作は未定義

(4a) rank(p) で p が有効範囲外ならば、無難な値を返してほしい

あるビット列の長さが N のとき、そのビット列には 0ビット目 から N-1ビット目 までが存在し、Nビット目は存在しません。

しかし、Nビット目の「手前」までに存在する 1 の個数であれば、数えることが可能です。

つまり rank(N) は有効で、その値は「当該ビットベクトルに含まれている 1 の全個数」です。

この考えを推し進めていくと、例えば p == N + 9999 はビット位置としては明らかに不正であり、十中八九、呼び出し側に何らかのバグがありますが、それでも rank(N + 9999) の値は自然に定義できて rank(N + 9999) == rank(N) です。

「-1 ビット目」や「-9999 ビット目」についても、ほぼ同様の議論を経て、自然に定義することができます。rank(-1) == rank(-9999) == 0 です。

ビット位置 p 自体の有効範囲は [0, N) すなわち 0 <= p < N ですが、考えようによっては、rank(p) の定義域は整数全体ともみなせます。(= 有効範囲外が存在しない)

(4b) select(c) で c が有効範囲外ならば、-1 などの無効値を返してほしい

「select(c)」は、「c 個目の 1 が何ビット目にあるか」を調べる操作です。

ここでもし、対象のビット列に含まれている 1 が 10 個だけだったら、11 個目の 1 は探しようがありません。つまり rank(p) のケースとは異なり、このときの select(11) は、本質的に無効です。

ただし、呼び出し元は select(11) を呼び出してみるまで、それが無効だということが分かりません。そのため、もし「無効な引数で select(c) を呼び出したら、クラッシュするか未定義動作になる」という仕様だったら、ライブラリとして非常に使いづらいものになります。

結論として、select(c) が要求されたものを返却できないときには、-1 などの無効値を返してほしいです。

なお、例えば select(-1) や select(N + 9999) は呼び出す前から無効であることが自明ですから、これらについてはクラッシュさせるという選択肢もありえます。しかしその場合、呼び出し元のプログラムを書くときに考えることが少し増えます。そのため、自明な無効値でも、そうでない無効値でも、一律 -1 を返してくれることを望みます。

まとめ

以下のような仕様の簡潔ビットベクトル（succinct bit vector）実装を必要としています。

• ビット位置 p は、先頭ビットを 0ビット目としたときの p ビット目を意味してほしいです。
• rank(p) は、ビット位置 p の「手前」までに存在する 1 の個数を数えてほしいです。
  • たとえ p ビット目に 1 が立っていても、rank(p) には含めないでほしいです。
  • p <= 0 の場合には、0 を返してほしいです。
  • p が ビット列の長さ以上のときには、そのビット列に含まれる 1 の全個数を返してほしいです。
• select(c) は、「c 個目の 1 が何ビット目にあるか」を返してほしいです。
  • c 個目の 1 が存在しない場合には、-1 を返してほしいです。
  • c が有効範囲外の場合にも、-1 を返してほしいです。
  • select(c) が存在するならば rank(select(c)) + 1 == c が成立してほしいです。