"Compact Data Structures: A Practical Approach" の輪講が終わりました

5月から以下の本の輪講を助教の先生と @yurahuna と私でやっていました。修論の追い込み次期ということで9章のグラフの章が終わったところで一旦終了としました（本当は11章のTextまでやりたかったのですが仕方ないね）。

Compact Data Structures: A Practical Approach

Compact Data Structures: A Practical Approach

9章までの簡単なまとめ

2章では基本事項として最悪エントロピーやシャノンエントロピーの計算，ハフマン符号による符号化，イェンゼンの不等式の計算練習をやりました。簡潔データ構造は「情報量の下限に近い容量で有益な操作を提供する」というデータ構造なので，この本ではどんなデータ構造についても最初にエントロピーを計算するところから始めています。ハフマン符号は最適な平均ビット長で表現することができる符号化方式であり，後の章では順列の圧縮やウェーブレット行列の圧縮にも使いました。イェンゼンの不等式は f(x) が凸関数のとき（本書ではもっぱら log(x) に対して使う）に Σ f(x) を f(Σx) で抑えるのに使える便利な式で，後の章のいろいろなところで活躍しました。

3章では固定長配列や可変長配列を保存する方法について学びました。可変長配列では配列の途中の要素を取り出すためにポインタが必要になってしまうのですが，ポインタは情報量的には余分な領域なのでSampled PointerやDense Pointerといったテクニックを導入しました。また，この章の最後のApplicationの節では定数時間初期化配列についても学びました。

qiita.com

4章ではビット列に対して rank （ビット列の先頭からあるインデックスまでの1の数）と select （k 番目の1を返す）を実現するデータ構造であるBitVectorについて学びました。以後の章ではBitVectorを使い倒していくことになります。またビット列に含まれる1の数がビット列全体に比べて非常に少ない場合に有効なBitVectorであるVery Sparse BitVectorについてもやりました。

5章では順列のinverseやpowerを高速に処理するデータ構造について学びました。なぜ順列が5章に配置されているのかというと，6章で必要になるからです。この本は章の間の依存関係についてよく考えられていると思います。

kujira16.hateblo.jp

6章では数列に対して rank と select を実現するデータ構造について学びました。順列を使う方法から始まり，ウェーブレット木・ウェーブレット行列とその圧縮表現について学んだあと，アルファベットサイズ σ が大きい場合にクエリ O(log log σ) の時間計算量で処理するテクニックであるalphabet partitioningについて学びました。

7章ではバランスの取れた括弧列 (BP) を管理するデータ構造であるrmM-treeについて学びました。括弧列の処理は，この本を読むまで全く理解できず，私が一番知りたいと思っていたところだったので非常に楽しかったです。データを log n 個ずつに分割してクエリを O(log log n) 時間で処理する方法についても学んだのですが，ここは非常に難しかったですね…

8章では簡潔データ構造の研究の中で最も大きな成果の1つである木（順序木）の表現について学びました。LOUDSは行える操作が限られていますがBitVectorのrank, selectだけで実現できるので高速，BPは多様な操作が行なえますがBPを使う必要がある，DFUDSはLOUDSとBPの中間という感じでした。

9章ではグラフの簡潔表現について学びました。特に平面グラフの圧縮は非常にコンパクトに圧縮できるということが分かり，いろいろな分野に応用できそうだと思いました。

感想

9章まで終えた感想ですが，章ごとの依存関係がきっちり整理されており，後ろの章で紹介される考え方が前の章に出てくるということがなく，前から読んでいくのであれば非常に読みやすい教科書だと思いました。一方で，前の章を読まないと後ろの章が全く理解できないということにもなりがちなので，輪講の課題図書としては人数が増えてくると使いにくい部分もあるかもしれません。たとえば，8章のTreeを理解するには7章のBPを理解する必要があり，BPの理解にはさらに4章のビット列の理解が必要，といった感じです。

とはいえ，一部の高度な部分を除いては全体的に平易にかかれているのでおすすめできます。Navarro先生ありがとうございました！！