"高速文字列解析の世界"を読んだ
高速文字列解析の世界というタイトルからは、どんな中身なのかあまり伝わってこないので、どんなことが書いてある本なのか、中身をちょっと紹介してみる。
1章、2章は概観や準備であり、3章からが本番なのだが、Burrows Wheeler Transform、簡潔データ構造、ウェーブレットツリー、データ圧縮、全文検索、テキストマイニングのためのデータ構造、という章題になっている。
何に使うのかという目的ベースで考えると、この本に載っているのは、データ圧縮、情報検索とテキストマイニングの基盤技術である（データ圧縮については基盤と言うよりはそのものだが）。ただ、この本には本当に基盤技術の話しか載っていないので、「この本で情報検索はバッチリだぜ！！」というような訳にはいかない。テキストマイニングに関しても同様である。別途入門書を読むなりしないと、より高次元（ここでの高低は技術の積み重ねの高低であり、難しさの高低ではない）の知識を手に入れることはできない。
というわけで、全くの初心者にこの本をおすすめするというわけには行かない（基盤側の技術についてから上側の機能を推測できるようなレベルの人ならば話は別で、そういう人もいっぱいいるとは思うけれど）のだが、初心者向けの本、例えば 情報検索の基礎とか検索エンジンはなぜ見つけるのか ―知っておきたいウェブ情報検索の基礎知識のような本を読んだけど、次に何を読めばいいのだろう、というような人に、これまではThe Burrows-wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching のような洋書を薦めるしかなかった（もしくは「SIGIRの論文とか読むといいよ？」と言うぐらいか）のだが、これからは多少ハードルを下げ、日本語の本を薦めることができるというわけだ。あと、The Burrows-wheeler Transformの方は読んでないけど、たぶんこっちの方が新しいことが書いてある。Wavelet Matrixとか。
というのが一般的な話だと思うのだが、個人的には前から読みたかった話が色々と書いてある。以下にまとまりのない感じで感想を述べる。
XBWはとりあえず理解した。XBWのアイデアは賢い。BWTの拡張になっていてLF-mappingが成り立つのである。賢い。賢いがLOUDSと比べてどれぐらい速いんだろうか。ちょっと気になる。あと、marisa-trieで使ってる再帰的Trie分解と組み合わせることができるし、パトリシア化もできそうなのだが、実装するとものすごく辛いだろうなぁ……。
透過的符号の話とかも面白い。透過的符号というのは、ランダムな位置から効率よく復元できる符号化方法で、書籍のほうで紹介されている手法では、ほとんどの値が小さくてたまにおっきな数字が混ざってる、みたいな配列をこれで符号化するとサイズが小さくなって速度もあんまり落ちない。実装も簡単そう。
ウェーブレットツリーはどういうデータ構造なのかはだいたい知ってるのだが、いろいろな操作ができるという事はよく知らないのでこれから勉強したい。
接尾辞配列をInduced Sortingで作る話は難しい。寝る前にちょろちょろ読んでるのでは理解できなさそうだ。紙と鉛筆で自分で配列書いてみないとしんどい。
まとめると、情報検索やテキストマイニングなどの新しい基盤技術に興味のある人、データ圧縮に興味のある人におすすめの本であると言える。
高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)
posted with amazlet at 13.01.08
