FM-Indexのことが懐かしくなったので実装してみました。
３種類のビットベクトルの作りかた
ビットベクトルに対してrankとselectを高速に処理したいが、そのための補助データの大きさはビット長Nに対してo(N)であって欲しい、という状況がまずあったとします。それを叶える方法はいくつかあります。
１
以下は最も基本的な方法です。ビットが密 (0と1の出現頻度に大きな差がない) で、出現位置がバラバラなときに使います。
・ビット列を大ブロックと小ブロックに分ける。
・最初から各大ブロックまでのrank値を事前計算する。
・各大ブロック内の最初から各小ブロックまでのrank値も事前計算する。
・rankは2回の表引きとpopcountで計算できる。
・selectは3段階の二分探索で頑張る。
みたいなやつです。Nの値に応じてブロックの大きさをいい感じに調節して、かつ小ブロックの値をちゃんと詰めて(int8_tとかで)持っておけば、表の大きさはo(N)になります。
２
疎なビット列、すなわち1がわずかしか出てこないビット列に対しては別の方法もあります。
・ビットが立っている位置を昇順に全列挙した配列を作る。
・その配列の下位いくつかのビットはそのまま持っておく。
・それより上位のビットは広義単調増加数列だが、差分列をunary符号化して、前述のビットベクトルとして持っておく。
・当ビット列へのrankとselectは、unary符号化列に対するselectをいい感じに使ってできる。
みたいなやつです。ビット列の疎の度合いに応じて適切な位置で上位下位に切ることで空間効率が良くなります。適切に切ればunary符号化列の0と1の比率が均等に近くなるイメージです。
３
最後に、1と0の頻度は同じくらいだけど出現位置が偏っているケースで効率的に圧縮する方法があります。RRRと呼ばれています。
・ビット列を長さkのブロックに分ける。
・各ブロック内で立っているビット数をそのブロックのクラスcと呼ぶ。
・ブロック長k、クラスcのビット列の種類はCombination(k,c)通りあるが、それらを昇順にソートしたときに何個目になるかをそのブロックのオフセットoと呼ぶ。
・ポイントとして、cとoだけからブロックのビット列は一意に定まる。だからcとoだけ保持すればよい。cはそのまま持っておく。oもそのまま詰めてビット列として持っておく。詰めてというのは、長さceil(log2(Combination(k,c)))のビット列をコンカチしまくるということで、そのままだとどこからビット列が始まるのかわからない。
・なので、オフセットを並べたビット列のうち、値が始まるビットだけ1にしたビット列を疎なビット列として持っておくことで対応する。
・加えて、いくつかのブロック列をチャンクとして、最初から各チャンクまでのクラス値を事前計算しておく。
・rankとselectは表引きとブロック復元で頑張る。
みたいなやつです。ポイントは、1と0が固まって出現するならば、クラスcは0かkに近い値になりがちのはずで、ゆえにCombination(k,c)が小さい値になりがちなため、少ないビット数でoを格納できるところです。ウェーブレット行列ではBWTした文字列をビットスライスしてビット列として持っておきますが、（BWTしているので）実データに対するこのビット列はRRRで圧縮できるような感じに偏っていることが期待できます。
圧縮全文索引について
圧縮全文索引という概念があります。これは、 (巨大で変更されない) リファレンス文字列に対して、完全一致検索クエリを高速に処理したいがそのための補助データは元文字列よりも小さくあって欲しいという望みを概念化したものです。この望みはFM-IndexとRRRとCompressed Suffix Arrayを使えばなんとか実現できます。まず、実文字列をリファレンスとしてRRRをバックエンドにしたFM-Indexは元文字列よりも小さいと期待できます。FM-Indexとはクエリ文字列を受けて、それと完全一致するようなSuffix Array上の位置（Suffix Array上の値ではなく、Suffix Array配列の添字番号）を出力するものです。一方で、普通はクエリを投げる人はリファレンス文字列上の一致位置が欲しいので、Suffix Arrayを読みに行く必要があります。ここでCompressed Suffix Arrayなら元文字列よりも小さく持っておけます。
短所
ここまでの説明で説明を避けてきたことがいくつかあります。ひとつは構築時のメモリ要求量です。 (今回の実装では) 構築ステップで一番最初にSA-ISとかで普通にSAを構築します。これは元文字列の8倍とかのメモリを食います。(8倍と言ったのは例えばリファレンスが長さ2^33の1バイト文字列で、Suffix Arrayの配列がuint64_t[]だった場合) もう一つは、圧縮率と引き換えに計算速度は定数倍悪化することです。使えるメモリ量が多いなら、RRRではなく基本的なビットベクトルを使うほうが高速です。もっと大量のメモリがあればN-gram転置索引とかハッシュ系のやつとか色々ありますし、ヒット箇所の列挙が厳密でなくてもよいなら確率的データ構造とかで色々できるかもしれません。
