テキスト圧縮はこれ一冊でOK！？な優良書籍「The Burrows-Wheeler Transform」を読んだ
以前より気になっていた書籍「The Burrows-Wheeler Transform Data Compression, Suffix Arrays, and Pattern matching」を読む機会を得ることができた。それなりに高額な本だったので購入が躊躇っていたのだけど、これは自分用に購入してもいいかも。というくらいの良書だったので紹介しておく。
本書はタイトルのとおりBWT(Burrows-Wheeler変換)に関する書籍。サブタイトルにあるようにデータ圧縮やSuffixArrayによる全文検索についても充実した内容になっている。最後のPattern matchingはテキストから検索キーとexactにマッチした、もしくは類似した箇所を取り出すよ、という話。2008年の本なので比較的新しい話題も扱っていて満足度が高い。
また本書の特色は圧縮ありきで始まり、そこから全文検索可能なアルゴリズムであるFM-Indexにまで話が続く、という点。私はSuffixArrayから勉強を始めたので全文検索ありき、でそこから圧縮の話題に拡張していったので視点が逆で新鮮だった。
もちろんCompressedSuffixArrayについても詳しく説明があり、非常に内容が充実している。参考までに以下に目次をメモしておくよ。
1 Introduction 1.1 An example of a Burrows-Wheeler Transform 1.2 Genesis of the Burrows-Wheeler Transform 1.3 Transformation 1.4 Permutation 1.5 Recency 1.6 Pattern matching 1.7 Organization of this book 1.8 Further reading 2 How the Burrows-Wheeler Transform works 2.1 The forward Burrows-Wheeler Transform 2.2 The reverse Burrows-Wheeler Transform 2.3 Special cases 2.4 Further reading 3 Coders for the Burrows-Wheeler Transform 3.1 Entropy coding 3.2 Run-length and arithmetic coder 3.3 Move-to-front lists 3.4 Frequency counting methods 3.5 Inversion Frequencies (IF) 3.6 Distance coding 3.7 Wavelet trees 3.8 Other permutations 3.9 Block size 3.10 Further reading 4 Suffix trees and suffix arrays 4.1 Suffix Trees 4.2 Suffix arrays 4.3 Space issues in suffix trees and suffix arrays 4.4 Further reading 5 Analysis of the Burrows-Wheeler Transform 5.1 The BWT, suffix trees and suffix arrays 5.2 Computational complexity 5.3 BWT context clustering property 5.4 Analysis of BWT output 5.5 Analysis of BWT compression performance 5.6 Relationship with other compression schemes 5.7 Further reading 6 Variants of the Burrows-Wheeler Transform 6.1 The sort transform 6.2 Lexical permutation sorting 6.3 The extended BWT 6.4 Sort-based context similarity measurement 6.5 Word-based compression 6.6 Further reading 7 Exact and approximate pattern matching 7.1 Exact pattern matching algorithms 7.2 Pattern matching using the Burrows-Wheeler Transform 7.3 Performance of BWT-based exact pattern matching 7.4 Approximate pattern matching 7.5 Hardware algorithms for pattern matching 7.6 Conclusion 7.7 Further reading 8 Other applications of the Burrows-Wheeler Transform 8.1 Compressed suffix trees and compressed suffix arrays 8.2 Compressed full-text indexing 8.3 Bioinformatics and computational biology 8.4 Test data compression 8.5 Image compression, computer vision and machine translation 8.6 Joint source-channel coding 8.7 Prediction and entropy estimation 8.8 Further reading 9 Conclusion A Notation B Ongoing work on the Burrows-Wheeler Transform B.1 BWT-related web sites B.2 Ph.D. theses relating to the Burrows-Wheeler Transform References Index
といった感じ。注目したいのは7章で、BWTを使って全文検索するよ！ということでFM-Indexの話につながっていく。一応の本書のゴールが7章だと思うので先に読んで目指すべき点を明確にしておくのもよいかも。そして8章では別のアプローチということでCompressedSuffixArrayのお話につながる。私にこっちが入り口だったけど。。。
あとはSuffixArrayについてもざっと触れるだけかとおもいきや線形時間構築や省メモリ構築の話もあって予想外に充実している。
というわけで中々面白い本でした。圧縮データ構造に興味がある人は手元においておきたい一冊！かも。
