出版社内容情報
簡潔データ構造とは，データをエントロピーの限界まで圧縮して保存しつつ，検索等の処理を行う際にはあたかも非圧縮のデータに対してアクセスしているように扱えるデータ構造である。データを圧縮することにより，これまでのデータ構造よりも多くのデータを扱えるようになる。扱うデータによっては 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 文献ノート
参考文献
杉原 厚吉［スギハラ コウキチ］
編集
室田 一雄［ムロタ カズオ］
編集
山下 雅史［ヤマシタ マサフミ］
編集
渡辺 治［ワタナベ オサム］
編集
定兼 邦彦［サダカネ クニヒコ］
著・文・その他
目次
第１章 はじめに
第２章 基本事項
第３章 基本的な簡潔データ構造
第４章 ウェーブレット木
第５章 区間最小値問い合わせ
第６章 順序木
第７章 文字列検索のデータ構造
第８章 ＢＷ変換
著者等紹介
定兼邦彦［サダカネクニヒコ］
１９７１年生まれ。１９９５年東京大学理学部情報科学科卒業。２０００年東京大学大学院理学系研究科情報科学専攻博士課程修了。東京大学大学院情報理工学系研究科数理情報学専攻教授・博士（理学）。専門はアルゴリズムとデータ構造（本データはこの書籍が刊行された当時に掲載されていたものです）
※書籍に掲載されている著者及び編者、訳者、監修者、イラストレーターなどの紹介情報です。
感想・レビュー
※以下の感想・レビューは、株式会社ブックウォーカーの提供する「読書メーター」によるものです。
mft
