出版書誌データベース

★コンパクトデータ構造の魅惑的なアルゴリズムの世界を、特に実用性を重視して紹介！
★幅広いトピック（ビットベクトル、数列、順列、木、格子、2項関係、グラフ、トライ、テキスト集合）の理論から応用例までを丁寧に解説！
★150を超えるアルゴリズムの擬似コードを掲載した唯一無二の成書！

【本書より抜粋】
多くの圧縮アルゴリズムでは、圧縮されたデータ中の一つの値のみにアクセスする場合でも、データを先頭から復元していく必要がある。コンパクトデータ構造の目的は、まさにこの問題にチャレンジすることである。コンパクトデータ構造を用いると、データとそれに対する追加のデータ構造を小さい領域で格納するだけではなく、データに対してコンパクトな表現のまま、つまりデータを復元せずに、アクセスや問合せを行うことができる。
本書は、読者にコンパクトデータ構造の魅惑的なアルゴリズムの世界を、特に実用性を重視して紹介することを目的としている。紹介する多くのデータ構造は無理なく実装できて空間的、速度的に効率が良いことが示されており、実際すでに実装されている。
また、理論についてもなおざりにはしない。理論はなぜ、またどのようにデータ構造が動作するのかを完全に理解し、新たな課題に直面したときにデータ構造を適用あるいは拡張するために必要不可欠である。本書は、読者にコンパクトデータ構造の背後にあるアルゴリズム論と数学の美しさをわかりやすく紹介する。

【主な内容】
第1章　はじめに
第2章　エントロピーと符号化
第3章　配列
第4章　ビットベクトル
第5章　順列
第6章　シーケンス
第7章　括弧列
第8章　木
第9章　グラフ
第10章　格子
第11章　テキスト
第12章　動的データ構造
第13章　最近の動向（符号化データ構造、反復的な文書集合、2次記憶）

第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 次記憶
参考文献

著：ゴンザロ・ナバロ
ゴンザロ・ナバロ（Gonzalo Navarro）
チリ大学計算機科学専攻 教授


訳：定兼 邦彦
東京大学大学院情報理工学系研究科 教授
著書『簡潔データ構造（アルゴリズム・サイエンス・シリーズ）』共立出版（2018）にて、2019年度大川出版賞を受賞