4. ＠nobu_k さん
サフィックスアレイの話(仮)
資料:http://www.slideshare.net/nobu_k/suffix-arraysolr
サフィックス接尾辞
接尾辞を辞書順に並べたものがサフィックスアレイ
転置インデックスより検索速度は遅い。
出現位置から最小と最大がわかり、二分探索ができる
SAのメリット
長いクエリに対してngramより速い
デメリット
インデックス構築系
アルゴリズムが難しい。
メモリ上での構築はちょっとだけ楽（けど、簡単ではない）
SAISなど。けど、これだとメモリがいっぱいないとキツイ
HDDでの構築
ランダムアクセスを排除したアルゴリズムが必要（dc3,dc7）
インデックス更新、差分更新できない。
頑張って１台100GB/day
VSストップワード
ストップワード込でインデックス作るみたい。
1.SAを二分探索
2.該当区間から出現位置をロード
3.出現位置をソート
O(n)だけど、CPUのキャッシュミスが激しく影響
4.ソートした出現位置からヒット文書を求める。
同じくキャッシュミスがやばい
・実際にはmallocした領域のページフォルトが一番やばい
SAが活躍する場面
・遺伝子検索(文字が4(+1)なので)
→組み合わせが絞られている中で探すのが便利ってこと？？
