Compressed Permuterm Index

　hillbigさんに紹介してもらったCompressed Permuterm Indexをちょっと前に読んだ。Compressed Permuterm Index以前にそもそもbackward search自体が理解できなくて、refferされてる別の論文読んだりしてたらだいぶ時間がかかってしまった。
　この論文に書かれているアイデアを文章で説明するなら、単語集合を*辞書順にソートしておけば*、Suffix Arrayを作ったときに、単語の先頭から末尾へジャンプするのは簡単だ、という事だ。この事実を利用して、Prefix Suffix Searchが実現できるよーと言うのがこの論文の主張。アイデア自体はすごい単純だし、実装もすごく簡単なんだけど、どんなものを食べればこんなすごいアイデアが出てくるようになるのかはさっぱりわからない。脱帽。
　backward searchに関しては、というか、圧縮全文索引に関してはたぶんCompressed full-text indexesというサーベイ論文を読むのが一番手っ取り早いんじゃないかと思うが、ACM会員じゃないので読んでない。大学からならアクセスできるのかもしれないけど、もう卒業しちゃったしなぁ…。
　というわけで、Compressed Suffix Arrayに関してはIndexing Compressed Text (P. Ferragina and G. Manzini, 2005)で勉強したんだけど、理解してから読み直してみると、Compressed Permuterm Indexの論文のbackward searchの説明は、短い割によく書けててわかりやすい。気合いを入れて読んだら、こっちの方だけでも十分に理解できそうだ。