概要 rank/select は簡潔データ構造(Succinct Data Structures)の核になる関数です.ビット列の k ビット目までに含まれる 0, 1 の数を求めるのが rank,k 番目の 0, 1 の位置(Index)を求めるのが select であり,ビット列の密度(1 の割合)によって,いろいろな実装があります. marisa-trie では,0, 1 の割合が極端に偏らないビット列を想定するとともに,32-bit 環境における性能の劣化を防ぐために,64-bit 整数を使わないようにしました.そのため,ほとんどの部分は以前に開発したライブラリからの流用ですが,新しく書き直した部分もあります.ちなみに,索引のサイズはビット列の長さ n bits に対して (1/4)n bits です. 基本 ビット列の実装 ビット列の格納には 32-bit 整数の配列を使っています