「高速文字列解析の世界」サポートページ

このページでは「高速文字列解析の世界」に関する追加情報・訂正・サンプルコード等の情報を掲載します。
誤り・コメントなどありましたら daisuke.okanohara+string@gmail.com に送っていただければ幸いです。

お知らせ

  • 2013/6/1 4刷が決定されました。
  • 2013/2/14 3刷が決定されました。
    岩波書店自然科学書の専門書月刊売上で1位になりました。[link](集計期間:1/14~2/10)
  • 2013/1/11 2刷が決定されました。
  • 2012/12/27 出版しました。サポートページを開設しました
書誌情報




文字列解析は古典的でありながら、全ての解析に重要となる技術です。本書ではその中でも、ここ十年で最も大きな進歩であり重要な技術である、Burrows Wheeler変換,簡潔データ構造、ウェーブレット木の三つの技術に注目し解説を試みました.

  • Twitterアカウント @faststringworld (評判情報や関連情報を挙げています)

目次

第1章 文字列解析の今
1.1 世の中の文字列
1.2 現在の計算機環境
1.3 文字列解析の例
1.4 文字列解析のための道具
1.5 本書の概要
第2章 文字列解析の準備
2.1 文字列の記法
2.2 文字列上の操作
2.3 経験エントロピー
2.4 計算モデル
2.5 符号
第3章 Burrows Wheeler変換
3.1 接尾辞配列
3.2 Burrows Wheeler変換
3.3 接尾辞配列,BWTの構築
3.4 BWTの性質と復元
第4章 簡潔データ構造
4.1 圧縮と索引の融合
4.2 完備辞書
4.3 木に対する簡潔データ構造
第5章 ウェーブレット木
5.1 文字列上の操作の実現
5.2 ウェーブレット木の構築方法と特徴
5.3 文字列操作の実現
5.4 さまざまなデータへの適用
5.5 ウェーブレット木の圧縮
5.6 アルファベット数が大きい場合
第6章 文字列データ圧縮
6.1 基本的なデータ圧縮の例
6.2 辞書を用いた圧縮:LZ法
6.3 文脈を利用した圧縮:PPM法
6.4 BWTを利用した圧縮
6.5 透過的データ圧縮
第7章 全文検索
7.1 問題設定
7.2 逐次検索
7.3 全文索引
7.4 接尾辞配列による検索
7.5 圧縮全文索引
7.6 キーワード集合の管理
7.7 アルファベットサンプリング
第8章 テキストマイニングのためのデータ構造
8.1 接尾辞木と極大部分文字列
8.2 文書集合の統計量
8.3 文書配列を利用した統計量の計算

訂正・追記

(新しい版では既に修正されている場合があります。)
  • p.12 2.1章 文字列の記法:Σ^kについての例。例えばΣ={a, b, c}の時、Σ^2 = {aa, ab, ac, ba, bb, bc, ca, cb, cc}。
  • p.18 2.5.1章「加算無限個」は「可算無限個」
  • p.19 2.5.2章「例えば,P(1100_2) = 110_2」は,「例えば,P(1100_2) = 100_2」
  • p.19 2.5.4章「r = x' / k」は,「r = (x' / k) + 1」。また「mを長さ|(k)_2|ビット」は「mを長さ|(k-1)_2|ビット」
  • p.20 2.5.6章 「lg p ビット」は 「-lg p ビット」
  • p.21 表2.2 100に対するゴロム符号化は「0000000000001011」
  • p.24 3.1章「<_{lec}」は「_{lex}」
  • p.28 3.2章「C[0, \delta]」は「C[0, \sigma]」、
    「T_B = "a_1 r_1 d_1 c_1 a_2 ...」は「T_B = "a_1 r_1 d_1 $ c_1 a_2」、
    「T_F = "a_1 a_2 ...」は「T_F = "$ a_1 a_2 ..."」、
    「T_B = "ard$caaaaabb"であるが」は「T_B = "ard$rcaaaabb"」、
    「T_F="$aaaaabcdrr"」は「T_F="$aaaaabbcdrr"」、
    「T_B="a_1 r_1 d_1$  c_1 ...」は「T_B="a_1 r_1 d_1 $ r_2 c_1 ...」
  • p.31  補題3.7 証明中 「S_{i+1}はyが1回以上繰り返された後にyより...」は「S_{i+1}はyが0回以上繰り返された後にyより...」、同様に「S_{j+1}はyが1回以上繰り返された後にyより...」は「S_{j+1}はyが0回以上繰り返された後にyより...」
  • p.38 Algorithm2 3番目のfor文のCの添字「c」は「i」
    また、同アルゴリズムの最後のfor文のT[i]への代入とpへの代入は順番が逆
  • p.44  4.2.1章 「 rank(B, i) として求めることができる」は 「 rank_1(B, i) として求めることができる」
  • komiya様、早川様、吉田様、hirokazu様、光成様、福島様、野口様、黒石様、宵様、磯谷様、ご指摘ありがとうございます。

関連情報

参考コード

本書を読む上で参考になるコード集であり、一緒に読むと理解が深まります。また実際に使うことができます。
(開発者の明記がない場合は、著者が開発をしています)
  • sais-lite
    • Induced Sortingを用いた接尾辞配列の線形時間の構築
    • 作者:Yuta Mori氏
    • 3.3章:接尾辞配列、BWTの構築
  • libcds
    • 簡潔データ構造ライブラリ
    • 作者:Francisco Claude氏
    • 4章:簡潔データ構造、5章:ウェーブレット木
  • data compression programs
    • LZ, BWT, PAQなどのデータ圧縮プログラムとベンチーマーク
    • 作者:Matt Mahoney氏
    • 6章:文字列データ圧縮
  • tx-trie ux-trie
    • LOUDSによる簡潔木を利用したtrie(ux-trieの方が新しく、tailを圧縮)
    • 4.3章 : 木に対する簡潔データ公図
  • sdarray
    • 疎な場合の完備辞書
    • 4.2.4章 : 完備辞書 疎な場合
  • rsdic
    • RRR + αによる完備辞書
    • 4.2章:完備辞書(rsdicの中身は本書の範囲外)
    • 現時点で一番コンパクトかつ高速な完備辞書
  • wat-array
    • ウェーブレット木とその実装
    • 5章 ウェーブレット木 5.6.1章 ポインターが無いウェーブレット木
  • mini-se
    • 全文検索のサンプルコード
    • WEB+DB Press Vol.53, 2009 速習サーチエンジンの記事の付属コードです
    • 2.5章 符号 7.2章 逐次検索  7.3章 全文索引
  • esaxx
    • 拡張接尾辞配列の構築
    • 8.1章:接尾辞木と極大部分文字列
  • ds-vector
    • 動的な簡潔配列
    • 本書の範囲外