簡潔データ構造

簡潔データ構造とは，データをエントロピーの限界まで圧縮して保存しつつ，検索等の処理を行う際にはあたかも非圧縮のデータに対してアクセスしているように扱えるデータ構造である。データを圧縮することにより，これまでのデータ構造よりも多くのデータを扱えるようになる。扱うデータによっては 1/100 まで圧縮できる。2000年以降，多くの理論的・実用的データ構造が提案されており，ゲノム情報処理等では実際に使われている。 　本書は，基本的な簡潔データ構造（ビットベクトル，文字列，木構造等）の理論を説明する。初期の簡潔データ構造は非常に難解なものが多く，実装しても性能の出ないことが容易に想像できたが，後に提案されたものは理論的性能を保ったまま簡単化されており，容易に実装可能であり実際の性能も良い。本書ではそのようなデータ構造を中心に説明しているため，簡潔データ構造を実問題に適用する際の助けになると思われる。 第1章　はじめに 1.1　背景 1.2　簡潔データ構造の歴史 1.3　本書の構成 第2章　基本事項 2.1　計算モデル 2.2　標準的な記号と関数 2.3　情報理論的下限 2.4　簡潔データ構造 2.5　エントロピー 2.6　整数の符号化 2.7　整数列の符号化 第3章　基本的な簡潔データ構造 3.1　ビットベクトルの簡潔データ構造 3.2　パタンに対するrank/select 3.3　疎なベクトルの簡潔データ構造 3.4　非常に疎なベクトルの簡潔データ構造 3.5　下限 3.6　実装上の工夫 3.7　文献ノート 第4章　ウェーブレット木 4.1　文字列でのrank/select 4.2　アルファベットサイズが大きいとき 4.3　その他の演算 4.4　ハフマン型ウェーブレット木 4.5　多分岐ウェーブレット木 4.6　直接アドレス可能符号 4.7　直交領域探索 4.8　文献ノート 第5章　区間最小値問い合わせ 5.1　問題の定義 5.2　RMQをLCAに帰着 5.3　LCAをRMQに帰着 5.4　±1　RMQ問題 5.5　RMQ問題の定数時間アルゴリズム 5.6　RMQ問題の4nビットデータ構造 5.7　RMQ問題の2nビットデータ構造 5.8　サイズの下限 5.9　文献ノート 第6章　順序木 6.1　LOUDS表現 6.2　括弧列(BP)表現 6.3　DFUDS表現 6.4　BP表現のより簡単なデータ構造 6.5　動的な簡潔順序木 6.6　文献ノート 第7章　文字列検索のデータ構造 7.1　接尾辞配列 7.2　接尾辞木 7.3　圧縮接尾辞配列 7.4　圧縮接尾辞木 7.5　文書集合に対するデータ構造 7.6　文献ノート 第8章　BW変換 8.1　ブロックソート圧縮法 8.2　逆BW変換とLF関数 8.3　FM-index 8.4　圧縮接尾辞配列とFM-indexの関係 8.5　双方向BW変換 8.6　ラベル付き木の圧縮 8.7　de Bruijnグラフの圧縮 8.8　文献ノート 参考文献