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

Backward Search

NLP

以下の論文で、Compressed Suffix Arrayについて全体を俯瞰した。

 

Compressed Full-Text Indexes.

Navarro and Makinen, ACM Computing Surveys, 2007.

http://www.cs.helsinki.fi/u/vmakinen/papers/survey.pdf

 

毎日の通勤の30分ぐらいで、少しずつ読み進めて、ひと月ぐらいかかったが、なんとか概略を掴めるようになった。ただ、経験的エントロピーの部分を理解するのに3日ぐらいかかったけど、まだ理解できていないwいや、おおよそはわかったと思うけど、紙で計算しても例の通りにならない。とりあえず、いつまでも止まっててもしょうがないので、ひとまず飛ばしたw

 

ただ、p.11~12ぐらいのSuffix Array上でのBackward Searchの説明に感動したので、もうちょっと自分の中で消化できるようになったら実装を公開していきたい。Wavelet Treeを使うとBackward Searchは簡単にできるし、FM-Indexを作ることができる。なので、Wavelet Treeを実装したくなった。なので、6月~7月は、Wavelet Treeを作ってみる。 

 

 

広告を非表示にする