検索の高速化

　300MB近いSuffixArrayを構築して検索をしている。二回目以降の検索は問題ないのだが、一回目の検索はかなりレスポンスが悪い。これはディスク読み込みに時間がかかっているものと思われる。なんとかならないか、ちょっと考えてみた。
　検索時にはたぶん二分探索してるだろう。これだとSuffixArrayのいろいろな部分を読み込まないといけないので、ディスク読み込みに時間がかかる。まず、読み込み回数を減らすために内挿ができないだろうか…と考えたのだが、内挿はやっぱ難しい。たぶん、試してもあんまりパフォーマンスは出ないだろう。
　なぜ内挿が難しいのかというと、データの分布を事前に予測することが難しいからだ。予測が外れたらあまりパフォーマンスが出ない（はず）。だったら、内挿用のデータを作ればいいのではないだろうか。SuffixArrayのいろんなところを読むからパフォーマンスが悪いわけで、二分探索の最初の1,2回さえ内挿できれば、十分に速度は出るはず。要するに、検索文字列の先頭数バイトをキーとして、SuffixArrayの探索範囲に関するデータを取ってくる構造を作ればよい。
　と、ここまで書いてきて、これはたぶん、データベースで言うインデックスというものなのではないか、と思い当たった。それはともかく、この方向性で実装すれば、速度を上げられるだろう。
　このキーから探索範囲を引くためのデータ構造自体はなにで実装するべきだろうか。ハッシュかなぁ。