「高速文字列解析の世界」を読む前に知っておくと良いこと
「高速文字列解析の世界」という大変すばらしい本が発売された。わりと敷居が高い本ではあるので読む前に知っておくとよさそうなことを書いておく。
「高速文字列解析」とは
本書でいう高速文字列解析というのは主に2つのことを指している。ひとつはデータを圧縮して小さくしてディスクよりメモリ、メモリよりキャッシュというようにより高速な記憶装置で扱いましょう、という話。もうひとつはデータ構造を工夫することで複雑な操作もそこそこ高速に扱えますよ、という話。つまり「圧縮」の話と「効率的なデータ構造」の話があると考えておくと良い。
キーワードは3つ
オビにも書いてあるけれど、本書が主に扱うのは「BWT」「簡潔データ構造」「ウェーブレット木」の3つ。具体的には「BWT」が「圧縮」に関わっていて「ウェーブレット木」が「効率的なデータ構造」に関わっている。「簡潔データ構造」は基本的な道具として本書の色々なところで出てくる。
Burrows Wheeler変換
Burrows Wheeler変換(BWT)は接尾辞配列(Suffix Array)と同等の情報を持ちながらインデックスをほぼ必要としないというすごいデータ構造。なのでSuffixArrayでできることはBWTでもできる。でも世の中、そんなにうまくは行かなくてBWTでSuffixArrayと同じ事をするにはBWTの逆変換が高速にできないといけない。ところが「ウェーブレット木」を用いることでBWTの逆変換が高速に実現できる。というわけでBWTの実装にウェーブレット木を用いるとまじぱないっすよ、ってことになる。
簡潔データ構造
簡潔データ構造には色々あるけれど本書で主に扱うのは「完備辞書」とよばれるもの(私は簡潔ビットベクトルとよんでいたけど、どっちがメジャーかは知らない)。完備辞書というのはrank,selectという2つの操作が高速にできるビット列のこと。
rank(i)はi番目のビットより前にいくつ1が立っているかを返す。select(i)はi番目に1が立っているビット列の位置を返す。例えば
ビット列：1001000100 rank(0) = 0, rank(1) = 1, rank(2) = 1, rank(3) = 1, rank(4) = 2, rank(5) = 2, rank(6) = 2, rank(7) = 2, rank(8) = 3, rank(9) = 3, select(0) = 0, select(1) = 3, select(2) = 7
という感じ。この操作は一体何がしたいのかというと、例えばegg, book, dogという3つの単語があったときにeggbookdogという風にくっつけてデータを管理したい。このとき単語の切れ目の位置をそれぞれ8bitで記憶したりすると24bitかかってもったいない。こういうときに先ほどの1001000100のように切れ目になる位置に1を置いたようなビット列(10bitなので24bitより効率的)を用意してやると最初の単語の位置はselect(0)=0, 次の単語の位置はselect(1)=3というように計算できる。また位置5はrank(5)=2なので2番目の単語、位置8はrank(8)=3なので3番目の単語という計算ができる。
要するに可変長のデータ列を効率的に扱うためにはデータ長だけのビット列を用意してやってビット列上の位置から何番目のデータなのか知るにはrankを、データからビット列上の位置を知るにはselectを使えば良いよ、という話。このテクニックは本書で頻出するので自分で例題を書いて計算してみたりして充分に慣れたほうが良い。ここは完備辞書が使えるかも、とか日常的に考えるような姿勢が大切。逆に言うと完備辞書はあくまで道具なので完備辞書の実装方法について書いてある4章は初回はすっとばしても良いと思う。実装は難しいので。。。
ウェーブレット木
「ウェーブレット木」は万能のデータ構造と本書では言っているが実際にはそんなに万能ではない。何が出来るのかは本書を読んできちんと理解すると良い。「ウェーブレット木」の実装には「簡潔データ構造」が必要で、さらに前述のとおり「ウェーブレット木」を用いることで「BWT」が効率化出来る。つまり「簡潔データ構造」→「ウェーブレット木」→「BWT」という順で応用に向かっていく。ただ簡潔データ構造(というか完備辞書)はウェーブレット木以外にも使われるし、ウェーブレット木はBWT以外にも使われるのですべてがBWTに集約されるというわけでもない。
圧縮の話
本書の大きなテーマのひとつが圧縮。圧縮といってもミラクルが起きてデータが縮むわけではなく、よく出てくるデータを短いビット列で、あんまり出ないデータを長いビット列で表現すればトータルでデータサイズが縮むよね、って話。この発想だと必然的に個々のデータは可変長になるので前述の完備辞書が必要になってくる。ちなみに圧縮については第2章では「大きい数字とかそんなに出てこないよね、きっと」という大雑把な発想で小さい数字に短いビット列を割り振るような話が書いてあり、第6章では実際にデータの頻度を見つつ圧縮する話が書いてある。
全文検索の話
BWTはSuffixArrayとほぼ同じなのでBWTで全文検索できちゃうよね。BWTはウェーブレット木があるから超効率よくね。ウェーブレット木は完備辞書があるから超効率よくね。ってことでできたのが超効率のいいSuffixArrayだ、よしこれをFM-Indexと名付けよう！っていうような話が書いてあるのが第7章。この章にはCSA(圧縮接尾辞配列)ってのも書いてあるけどFM-Indexの登場でほぼオワコンなのでめんどかったら読み飛ばすのが吉。
つまりどう読めばいいのか
圧縮の基礎が書いてある2章とBWTについて書いてある3章は重要だけど、既存のドキュメントが充実しているので本書が難しいようならググるなり他書を読むなりすると良い。4章はrank,selectの操作の意味を覚えたら飛ばしてOK。5章のウェーブレット木は多分本書のメイン。既存資料もそんなに充実してないので頑張って本書を読むか論文を読むかの2択。6,7,8章は「BWT」「簡潔データ構造」「ウェーブレット木」が身についてから読むくらいで良いかも。FM-Indexだけは最初から読んでも良いかもしれない。個人的には6,7,8あたりが一番役に立った(ちゃんと論文読んでなかったのとかあったので)けど、初心者が慣れないうちに読むと爆死しそうな感じもする。
わりとどうでもよい話
本書の感想。ウェーブレット行列とかの最先端の手法までカバーされてるのはさすがという印象。技術は書籍化される頃にはオワコンという印象があるけどウェーブレット行列とかまだはじまったばかりの技術ですよ。超早い。
アルファベットサンプリング、LZEndは本書ではじめて知って面白いと思った。XBWは前にPFIブログで読んだけどすっかり忘れていて、本書を読んで思い出した。「BWT」「簡潔データ構造」「ウェーブレット木」については知っていたので本書はわりとさくさく読めて、ちゃんと調べていなかった手法の概要を短時間で知ることができたので個人的には満足した本だった。
逆に「BWT」「簡潔データ構造」「ウェーブレット木」について入門したい人にとって本書はどうかといわれるとわりと不親切な本である気もするけど、元論文は本書より鬼畜なものが結構あるので一概に本書が不親切とも言えない。私の場合、実装を読んだり、論文を読んだり、スライドを読んだりして勉強したけど何が近道なのかはよくわからない。
とりあえずページ数の割に内容が詰まった本だとは思う。例えばウェーブレット行列は私がつくったスライド(http://ja.scribd.com/doc/102636443/Wavelet-Matrix)は60Pあるのに対して本書では2Pで解説されているのでどれだけ内容が圧縮されているかは推して知るべし。なので1ページ読むのに超時間かかる！とか落ち込まずに、この1ページは30Pのスライドが圧縮されているのだ！とか思ってじっくり読むと良いかも。あと論文を読むときのように本書単独で読もうとせずにわからない部分は適宜他の資料をあさると良いと思った。
