確率と情報の科学
高速文字列解析の世界
データ圧縮・全文検索・テキストマイニング
高度で高速な文字列データの解析に必要な理論から，データの圧縮，検索，分析の実践手法までを紹介する．
文書，ウェブ上の情報，ゲノム配列，センサデータなど，多様な情報が「文字列」として表現される．そのデータ量は爆発的に増加しており，多くの分野で，より高度で高速な解析技術が求められている．本書では文字列解析に有用な理論，データ構造，アルゴリズムと，それをふまえたデータの圧縮，検索，分析の実践手法を紹介する．
■著者からのメッセージ
文字列解析の分野は広く，進展も著しいため，本書ですべての情報はカバーできない．本書では，文字列解析という問題の特徴，面白さをとらえており，普遍的である話を取り込むことを心がけた．特に，Burrows Wheeler 変換，簡潔データ構造，ウェーブレット木という３つの技術に注目し，解説を試みた．これら３つの技術はここ十年における文字列解析の中で最も大きな進歩であり，今後も重要な技術と考えられる．そして，これらの技術は文字列解析以外にもグラフ情報や，２次元グリッド情報などに対して非常に強力なツールとなる．（中略）本書は，理論だけを追うのではなく実用的な側面も重視し，データや現在の計算機環境のトレンドを考慮し，シンプルで他と組み合わせやすい手法に注目して書いた．本書を読むことによって，文字列解析の世界に少しでも興味を持っていただければ幸いである．
■著者からのメッセージ
文字列解析の分野は広く，進展も著しいため，本書ですべての情報はカバーできない．本書では，文字列解析という問題の特徴，面白さをとらえており，普遍的である話を取り込むことを心がけた．特に，Burrows Wheeler 変換，簡潔データ構造，ウェーブレット木という３つの技術に注目し，解説を試みた．これら３つの技術はここ十年における文字列解析の中で最も大きな進歩であり，今後も重要な技術と考えられる．そして，これらの技術は文字列解析以外にもグラフ情報や，２次元グリッド情報などに対して非常に強力なツールとなる．（中略）本書は，理論だけを追うのではなく実用的な側面も重視し，データや現在の計算機環境のトレンドを考慮し，シンプルで他と組み合わせやすい手法に注目して書いた．本書を読むことによって，文字列解析の世界に少しでも興味を持っていただければ幸いである．
――「はじめに」より
まえがき
第１章 文字列解析の今
1.1 世の中の文字列
1.2 現在の計算機環境
1.3 文字列解析の例
1.4 文字列解析のための道具
1.5 本書の概要
第２章 文字列解析の準備
2.1 文字列の記法
2.2 文字列上の操作
2.3 経験エントロピー
2.4 計算モデル
2.5 符号
第３章 Burrows Wheeler変換
3.1 接尾辞配列
3.2 Burrows Wheeler変換
3.3 接尾辞配列，BWTの構築
3.4 BWTの性質と復元
第４章 簡潔データ構造
4.1 圧縮と索引の融合
4.2 完備辞書
4.3 木に対する簡潔データ構造
第５章 ウェーブレット木
5.1 文字列上の操作の実現
5.2 ウェーブレット木の構築方法と特徴
5.3 文字列操作の実現
5.4 さまざまなデータへの適用
5.5 ウェーブレット木の圧縮
5.6 アルファベット数が大きい場合
第６章 文字列データ圧縮
6.1 基本的なデータ圧縮の例
6.2 辞書を用いた圧縮：LZ法
6.3 文脈を利用した圧縮：PPM法
6.4 BWTを利用した圧縮
6.5 透過的データ圧縮
第７章 全文検索
7.1 問題設定
7.2 逐次検索
7.3 全文索引
7.4 接尾辞配列による検索
7.5 圧縮全文索引
7.6 キーワード集合の管理
7.7 アルファベットサンプリング
第８章 テキストマイニングのためのデータ構造
8.1 接尾辞木と極大部分文字列
8.2 文書集合の統計量
8.3 文書配列を利用した統計量の計算
参考文献
索 引
第１章 文字列解析の今
1.1 世の中の文字列
1.2 現在の計算機環境
1.3 文字列解析の例
1.4 文字列解析のための道具
1.5 本書の概要
第２章 文字列解析の準備
2.1 文字列の記法
2.2 文字列上の操作
2.3 経験エントロピー
2.4 計算モデル
2.5 符号
第３章 Burrows Wheeler変換
3.1 接尾辞配列
3.2 Burrows Wheeler変換
3.3 接尾辞配列，BWTの構築
3.4 BWTの性質と復元
第４章 簡潔データ構造
4.1 圧縮と索引の融合
4.2 完備辞書
4.3 木に対する簡潔データ構造
第５章 ウェーブレット木
5.1 文字列上の操作の実現
5.2 ウェーブレット木の構築方法と特徴
5.3 文字列操作の実現
5.4 さまざまなデータへの適用
5.5 ウェーブレット木の圧縮
5.6 アルファベット数が大きい場合
第６章 文字列データ圧縮
6.1 基本的なデータ圧縮の例
6.2 辞書を用いた圧縮：LZ法
6.3 文脈を利用した圧縮：PPM法
6.4 BWTを利用した圧縮
6.5 透過的データ圧縮
第７章 全文検索
7.1 問題設定
7.2 逐次検索
7.3 全文索引
7.4 接尾辞配列による検索
7.5 圧縮全文索引
7.6 キーワード集合の管理
7.7 アルファベットサンプリング
第８章 テキストマイニングのためのデータ構造
8.1 接尾辞木と極大部分文字列
8.2 文書集合の統計量
8.3 文書配列を利用した統計量の計算
参考文献
索 引
岡野原大輔（おかのはら だいすけ）
1982年生まれ．2010年３月，東京大学大学院情報理工学系研究科コンピュータ科学専攻博士課程を修了，情報理工学博士．2006年３月に（株）Preferred Infrastructureを共同で創業，現在，同取締役副社長．主な受賞歴は，IPA未踏ソフト創造事業スーパークリエータ認定（2005年），東京大学総長賞（2007年），言語処理学会年次大会優秀発表賞（2009年，2010年）など．
1982年生まれ．2010年３月，東京大学大学院情報理工学系研究科コンピュータ科学専攻博士課程を修了，情報理工学博士．2006年３月に（株）Preferred Infrastructureを共同で創業，現在，同取締役副社長．主な受賞歴は，IPA未踏ソフト創造事業スーパークリエータ認定（2005年），東京大学総長賞（2007年），言語処理学会年次大会優秀発表賞（2009年，2010年）など．
