圧縮したまま検索

「情報処理」に載った岡野原さんの記事「圧縮したまま検索」を読んだ。簡潔データ構造の解説だけあって、文章も簡潔で難解。LOUDSの部分で振り落とされてしまった。でも面白かったので、いつか自分で実装できればと妄想している。とりあえずライブラリの名前だけ決めた。


簡単に内容の紹介すると、まず、前半ではRank/Seleect辞書を導入して、これを用いてLOUDS、ウェーブレット木、圧縮全文検索とデータ構造を導入していく。後半はこれらを実装したライブラリの紹介をしている。

で、LOUDSで分からなくなったわけだけど、何処が分からなくなったかというと$\mathbf{parent}$を求める計算のところ。$\mathbf{parent}(b) = \mathbf{select}_0(B, p)$とあるのだが…なんか違わないか。$\mathbf{parent}(b) = \mathbf{select}_1(B, \mathbf{rank_1}(B, \mathbf{select}_0(B, p)) + 1)$くらいじゃないだろうか。勘違いしているのかもしれないけど。LOUDSの解説は情報系修士にもわかるLOUDS - アスペ日記にもあるけど、こちらは定式化が微妙に違うみたいな気がする。