コンパクトデータ構造　実践的アプローチ

発売日 : 2023年07月28日

著者／編集 : ゴンザロ・ナバロ/定兼 邦彦

出版社 : 講談社

発行形態 : 単行本

理論から応用例まで、幅広いトピックを丁寧に解説。１５０を超えるアルゴリズムの擬似コードを掲載した唯一無二の成書。研究者必携！

第1章 はじめに
1.1 なぜコンパクトデータ構造か？
1.2 なぜ本書か？
1.3 本書の構成
1.4 ソフトウェア資源
1.5 用いる数学と記法
1.6 文献ノート
参考文献
第2章 エントロピーと符号化
2.1 最悪時エントロピー
2.2 シャノンエントロピー
2.3 経験エントロピー
2.4 高次エントロピー
2.5 符号化
2.6 ハフマン符号
2.7 整数に対する可変長符号
2.8 イェンセンの不等式
2.9 応用
2.10 要約
2.11 文献ノート
参考文献
第3章 配列
3.1 固定サイズの要素
3.2 可変サイズの要素
3.3 部分和
3.4 応用
3.5 要約
3.6 文献ノート
参考文献
第4章 ビットベクトル
4.1 access
4.2 rank
4.3 select
4.4 非常に疎なビットベクトル
4.5 応用
4.6 要約
4.7 文献ノート
参考文献
第5章 順列
5.1 順列の逆元
5.2 順列の累乗
5.3 圧縮可能な順列
5.4 応用
5.5 要約
5.6 文献ノート
参考文献
第6章 シーケンス
6.1 順列の使用
6.2 ウェーブレット木
6.3 アルファベット分割
6.4 応用
6.5 要約
6.6 文献ノート
参考文献
第7章 括弧列
7.1 単純な実装
7.2 計算量の改良
7.3 多種類括弧列
7.4 応用
7.5 要約
7.6 文献ノート
参考文献
第8章 木
8.1 LOUDS：単純な表現
8.2 バランスした括弧列
8.3 DFUDS表現
8.4 ラベル付き木
8.5 応用
8.6 要約
8.7 文献ノート
参考文献
第9章 グラフ
9.1 一般のグラフ
9.2 クラスタ化グラフ
9.3 kページグラフ
9.4 平面的グラフ
9.5 応用
9.6 要約
9.7 文献ノート
参考文献
第10章 格子
10.1 ウェーブレット木
10.2 k2木
10.3 重み付きの点の検索
10.4 高次元の格子
10.5 応用
10.6 要約
10.7 文献ノート
参考文献
第11章 テキスト
11.1 圧縮接尾辞配列
11.2 FM-index
11.3 高次圧縮
11.4 構築法
11.5 接尾辞木
11.6 応用
11.7 要約
11.8 文献ノート
参考文献
第12章 動的データ構造
12.1 ビットベクトル
12.2 配列と部分和
12.3 シーケンス
12.4 木構造
12.5 グラフと格子
12.6 テキスト
12.7 メモリの割り当て
12.8 要約
12.9 文献ノート
参考文献
第13章 最近の動向
13.1 符号化データ構造
13.2 反復的な文書集合
13.3 2 次記憶
参考文献

Navarro, Gonzalo, 1969-

ゴンザロ・ナバロ

定兼 邦彦

定兼, 邦彦, 1971-