RRR

ウェーブレット行列というデータ構造を使えば、文字列に対するrankクエリ（i.e.文字列の先頭から位置iまでの間にアルファベットcが何回出現したか）をO(log C)で処理できます。ただしCはアルファベットの数です。このテクニックを使うと、長さMのクエリ文字列に対して完全一致検索クエリをO(MlogC)で処理できます。このアルゴリズムをFM-indexと呼びます。FM-indexは時間計算量が小さいだけではなく、そのために事前に用意すべき追加データがO(N)で済む（ただしNはリファレンス文字列の長さ。正確にはO(NlogC)でしょうが、慣習としてここのlogCは省略します）という長所があります。ちなみにこの「検索を高速化するために事前に用意する追加データ」は『索引』という単語の意味そのものです。全文検索用の索引で、かつリファレンス文字列自体よりも小さな索引を『圧縮全文索引』と呼びます。

以前の記事で、FM-indexによる全文検索の具体的なコードを示しましたが、そのコードの索引は圧縮全文索引にはなっていませんでした。まず、示したコードの手順は以下の通りでした。（Compressed Suffix Arrayは作っていませんでしたが、作るとした場合の手順です）
・構築ステップ
(1)リファレンス文字列を使ってSuffix Arrayを構築する。
(2)Suffix Arrayを使ってCompressed Suffix ArrayとBWT文字列を構築する。
(3)BWT文字列を使ってWavelet Matrixを構築する。
・検索ステップ
(4)Wavelet Matrixを使って、完全一致箇所を意味するSuffix Array上の区間を求める。
(5)Compressed Suffix Arrayを読み、その区間内の値を列挙する。それらがリファレンス文字列上の完全一致箇所そのものである。
構築ステップを終えて検索ステップに移るとき、生のSuffix ArrayとBWT文字列は捨ててよいです。Wavelet MatrixとCompressed Suffix Arrayだけ保持する必要があります。Compressed Suffix Arrayは好きなだけ圧縮できますが、問題はWavelet Matrixです。Wavelet MatrixはLogC個のSuccinct Bit Vectorから成ります。そしてあのコードにおいて各Succinct Bit Vectorは長さNのビット列と追加データから成っていました。結局、あのコードにおけるWavelet Matrixは元文字列のコピーと同じ大きさのビット列を含んでおり、ゆえに元文字列よりも大きいものでした。『圧縮全文索引』であるためにはその『長さNのビット列』を何らかの方法で可逆圧縮する必要があります。そのビット列は具体的にはBWT文字列をある意味でソートしてからBit Slicingして得られたビット列でした。一般にビット列の1と0の出現確率が大きく異なれば、少ないほうの出現位置を可変長配列で持つことで自明に可逆圧縮できますが、それは期待できません。しかし幸いなことに、実データに対するBWTの性質からして同じ文字が連続しがちなはずであり、ゆえに『ビット列』では同じビットが連続しがちなはずです。この性質を利用してビット列を可逆圧縮する方法として、RRRというアルゴリズムが岡野原本のp52以降で紹介されています。

RRRは元論文の筆者たちのイニシャルです。具体的には岡野原本を読んでください。