読者です 読者をやめる 読者になる 読者になる

Wavelet Treeをもう一度

NLP

文字列本のメインであるウェーブレット木をもう一度素直に見直すことにした。

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

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

Wavelet Treeに関する著者のスライドは以下である。

http://www.slideshare.net/pfi/ss-15916040

ふらふらと論文を眺めていたら、Navarro神の「Wavelet Trees for All」というサーベイ論文が加筆されて更新されていた。内容自体はあまり変わっていないと思うが図が増えていた。以下がその論文である。

http://www.dcc.uchile.cl/~gnavarro/ps/jda13.pdf

大半の内容は、文字列本で解説されているので、あまり気にする必要はないが、個人的に気になった項目について少し書いておく。
(勉強不足だったので)

まず、ウェーブレット木の高速化である。ウェーブレット木の性能は、文字種に依存する。それは、ウェーブレット木の高さが文字種に依存するからそうなる。これは、最悪値を保証するが、最速値も木の高さに依存している。ウェーブレット木を高速化するには、この木の高さを抑える必要がある。そのような考え方で高速化するのが、Multiary-Wavelet Treeである。ウェーブレット木は、通常、2分木であるが、例えば、8分木にすれば、256の文字種があった場合、木の高さを、8から3に抑えることができる。この分、高速化する。

実用的な実装は、以下の論文らしい。

https://github.com/alexbowe/wavelet-paper/raw/thesis/thesis.pdf

まだ読んでないので、なんとも言えない。

もちろん、ウェーブレット行列にも適用できる。

http://www.dcc.uchile.cl/~gnavarro/ps/spire12.4.pdf

まとめにちょっとだけ記述がある。

次に、ウェーブレット木の圧縮である。以前の記事で、文書ID配列にウェーブレット木を適用した場合、RRRを使っても圧縮されないということを書いた。現状、最も有力なのは、Re-Pairを使った簡潔ビットベクトルを利用して圧縮する方法である。文書ID配列は、BWTのように同じ文書IDが繰り返されない代わりに、同じ文書IDの組み合わせは繰り返される傾向にある。この性質を利用して圧縮できるようだ。ただ、Re-Pairを使った簡潔ビットベクトルの実装は、なかなかにめんどくさく、いずれしっかり書こうと思う。現状、Re-Pair以外に有力な圧縮表現がないようなので、今後の研究に期待したい。

最後に、Wavelet Trieである。これは、もはや名前だけ出てて、なんのことかあまりわかっていないが、興味のある人(ウェーブレット木萌え && Trie萌えな人)は、読んでみるといいかもしれません。私は読もうと思います(萌えてるので)。

http://arxiv.org/abs/1204.3581

この他にもLZ78のフレーズをウェーブレット木で検索する話とかがおもしろそうだった。

ほんとは、すべて実装して理解するのが一番いいと思うのだが、なかなか時間がとれないな。
(やっぱり、手を動かしている人が最強だと思います。)