Compressed Permuterm Index - 射撃しつつ前転 改hillbigさんに紹介してもらったCompressed Permuterm Indexをちょっと前に読んだ。Compressed Permuterm Index以前にそもそもbackward search自体が理解できなくて、refferされてる別の論文読んだりしてたらだいぶ時間がかかってしまった。 この論文に書かれているアイデアを文章で説明するなら、単語集合を*辞書順にソートしておけば*、Suffix Arrayを作ったときに、単語の先頭から末尾へジャンプするのは簡単だ、という事だ。この事実を利用して、Prefix Suffix Searchが実現できるよーと言うのがこの論文の主張。アイデア自体はすごい単純だし、実装もすごく簡単なんだけど、どんなものを食べればこんなすごいアイデアが出てくるようになるのかはさっぱりわからない。脱帽。 backward searchに関しては、というか、圧
