完備辞書（簡潔ビットベクトル）の解説 - アスペ日記

以前、「簡潔データ構造 LOUDS の解説」というシリーズの記事を書いたことがあります。 LOUDS というのは木構造やtrieを簡潔に表すことができるデータ構造なのですが、この中で「簡潔ビットベクトル」というものについてはブラックボックスとして扱っていました。 また、中学生にもわかるウェーブレット行列を書いたときも、その中で出てきた「完備辞書」の実装には触れませんでした。 この「簡潔ビットベクトル」「完備辞書」は、同じものを指しています*1。 今回は、このデータ構造*2について書いてみます。 完備辞書でできること ビット列に対する定数時間の rank と selectです*3。 rank()は、「ビット列の先頭から位置 k までに、1 のビットがいくつあるか」*4。 select()は、「ビット列の先頭から見て、n 個目の 1 のビットの次の位置はどこか」*5。 それぞれ例を挙げます。

[takeda25]

完備辞書について書いた。

[sh19910711]

"完備辞書でできること > ビット列に対する定数時間の rank と select / ビット列の先頭から位置 k までに、1 のビットがいくつあるか / あんまり容量を取らないでけっこう速くできるというのが重要"

[sonots]

あとで読む

[teddy-g]

Succinct Bit Vectorの説明。ちゃんとひとつひとつ確認しながら読みたいと思う。

[y-imaya]

実装する前にこれ読みたかった

[sucrose]

“「幼稚園児にもわかる完備辞書」というタイトルにしようかと思いましたが、さすがに思いとどまりました”