ウェーブレット行列とFM-indexで全文検索を書いてみた

www.youtube.com

去年のはじめに高速文字列本を買ったのですが、アルゴリズムを眺めるだけで実装はしていませんでした。特にウェーブレット行列は実装が大変そうにしか見えなくて敬遠していたのですが、ICPCの夏合宿で @hirokazu1020 さんに「あれはアイデアさえ理解していれば実装するのは簡単だよ」という旨のことを言われたので、学校のプログラミングの演習の自由課題としてウェーブレット行列とFM-indexを実装してみました。

制作物はブラウザ上で動く青空文庫のインクリメンタル検索です。C++で書いたFM-indexをboost-pythonを使ってPythonから呼び出せるようにし、Flaskを使ってブラウザからのリクエストに応答するような仕組みにしてみました。アルゴリズムの本質的なところは全て自分で書こう！というモチベーションで始めたのですが、SA-ISが難しくてsais.hxxという有名なライブラリに頼ることになりました。

アルゴリズム的に迷ったところは、高速文字列本に書いてあるウェーブレット行列と元論文に書いてあるウェーブレット行列が若干違うっぽい？ところでした (上位ビットからソートするのか，下位ビットからソートするのか)。本質的には同じなのかもしれませんが･･･

実装の難易度ですが、時間さえあればそれほど難しくないように思いました。競プロ的には真面目に簡潔にする必要性は低いので、sucvectorの実装で手を抜けばシンプルに書けるはずです。また、sucvectorのselectは不要な場合も多いので、そこをサボることができれば、最低限必要な箇所だけなら100行を超えずに実装できるでしょう。

今回の制作物の最大の反省点は設計が残念なことになってしまったことです。テストはしっかり書いたのでそんなに大変じゃないはずなのですが、リファクタリングする気が全く起こらないです…

スライド

FM-indexによる全文検索 from Sho IIZUKA

www.slideshare.net

コード

誰かの役に立つかもしれないので一応公開しておきますが、ウェーブレット行列やFM-indexは cybozulib のものがとんでもなく高速なので、そちらを利用することを強くおすすめします。また、他の人が使えるようにドキュメントを整備しているわけではないので、たぶんこれだけ渡されても使い方が分からないと思います。動かしたいという奇特な方がいらっしゃった場合は改善するかもしれません。あと、理由はよく分かりませんが、たまにSEGVします (もはや自力で改善するモチベーションが無い…)

github.com