ぱらぱらめくる『高速文字列解析の世界』

高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)

• 1 文字列解析の今
  • 文字列解析の道具
    • Burrows Wheeler変換
    • 簡潔データ構造
    • ウェーブレット木
• 2 文字列解析の準備
  • 文字列解析を記述するための記法
  • 文字列操作
  • エントロピー、経験エントロピー(標本エントロピー)
  • 計算モデル
  • 符号
• 3 Burrows Wheeler変換
  • フーリエ変換のようなもの
    • 可逆変換
    • 低エントロピー文字列の冗長性あぶりだし
  • 接尾辞配列
  • 接尾辞配列を用いたBurrows Wheeler 変換
• 4 簡潔データ構造
  • 圧縮と索引の融合
  • 完備辞書
  • 木に対する簡潔データ構造
• 5 ウェーブレット木
  • 多くの操作を効率的に実現できるデータ構造
  • 文字列・２次元グリッド情報、グラフ情報、転置索引、順序情報などを対象にできる
  • ウェーブレット行列
• 6 文字列データの圧縮
  • 圧縮一般
  • 辞書を用いた圧縮
  • 文脈利用の圧縮
  • BWTを利用した圧縮
  • 透過的データ圧縮
• 7 全文検索
  • 全文索引
  • 転置索引
  • 接尾辞配列による検索
  • 圧縮全文検索
  • キーワード集合
• 8 テキストマイニングのためのデータ構造
  • 接尾辞木と極大部分文字列
  • 文書集合の統計量
  • 文書配列を利用した統計量