4章
簡潔データ構造は、操作が高速でありながら作業領域量が小さいという2つの性質を兼ね備えたデータ構造であり、データ圧縮と索引の技術が組み合わさったものである
高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)完備辞書(FID)
- access: B[i]を返す
- rank:B[0,i)中のb∈{0,1}の数を返す
- select:B中で伝統から見てi+1番目に出現したb∈{0,1}の位置を返す
p.48の式がo(n)ビットに抑えられていると書いてあるのだが手で計算して確かめていない（ので後で計算する）。 (13.01.05 libcdsのチュートリアル読んだら理解した)
簡潔木の説明がさらりとしすぎてあまり触れられていない気もするが、本書においてあまり重要でないってことでいいのかな（全体を読んでみないとわからない）。
それから読んでいて索引が貧弱だなと思った。RRRとかselectとか引けない。