お手軽転置インデクスを用いた検索エンジン: (1) AND検索編
突然Cでコードを書きたくなったので，なんちゃって転置インデクスを用いた検索プログラムを書いてみた．
転置インデクスとは，索引語と呼ばれる単語が出現する文書情報 (場合によっては位置情報も) を保持したデータ構造のことで，索引語と，それに対応する転置リストによって構成される．
# 索引語 -> 転置リスト hoge -> 5: 1,2,3,4,5 fuga -> 3: 1,4,5 piyo -> 2: 4,5
これは，hogeという単語が文書1,2,3,4,5に出現し，fugaという単語が文書1,4,5に出現し，piyoという単語が文書4,5に出現する情報を保持している．最初の5,3,2という数字はそれぞれ索引語がいくつの文書に出現したかという文書頻度 (document frequency; DF) を表している．
検索クエリhogeが入力された場合には，文書1,2,3,4,5を検索結果として取得する．文書のランキングや，検索結果の表示方法 (スニペット生成) の話は今日は扱わない．
hoge AND fugaというAND検索を行う場合は，ふたつの索引語の転置リストを見比べて，共通の文書ID集合を取得する．上記インデクスを眺めると，文書4,5が結果として取得できることがわかる．
具体的には，ふたつの転置リストを先頭から順番に比較を行いながら走査し，小さい値を持つ方のリストのポインタを増やし，同じ値のものがあれば結果に保存する，というマージソートと同じようなアルゴリズムにしたがって積集合演算を行い，共通文書IDを取得する．
このように共通文書IDを効率よく取得するために，文書IDは一般的には昇順に保持されている．また，文書IDを昇順に並べることにより差分値で転置リストを表現できるため，圧縮効率の観点からも良い．
今日は転置インデクスによる検索処理と，複数単語でAND検索のイメージを掴むための，簡単な転置インデクスを用いた検索処理を実装してみた．
転置インデクスをきちんと書くと大変なので，いちファイル = いち転置リスト．"hoge"というファイルがあれば，"hoge"という単語についての転置リストがファイル内に記述されているというなんちゃってインデクス方式を採用．
% cat hoge 5 1 2 3 4 5 % cat fuga 3 1 4 5 % cat piyo 2 4 5
これで転置リストの出来上がり．
さて，入力された検索クエリに応じて該当するファイルを読み込み，転置リストの共通文書IDを取得する処理を書けばよい．
A AND Bの結果の長さはmin(A, B)になるため，複数クエリのAND検索を行う場合には，転置リストが短い順に共通文書IDの取得を行うと効率が良いことがわかる．
例えば，上記のhoge AND fuga AND piyoを検索する場合は，piyoとfugaの共通文書IDを取得し，その結果とhogeの転置リストの処理を行えばよい．
というわけでこんなものを作ってみた．
複数検索クエリが入力された場合に，
- 入力された検索クエリに対して転置リストを取得し，
- それぞれを転置リストの短い順に並び替え，
- 順々に文書IDの積集合を取得し，
- 最終的な結果を取得する
# ファイル一覧 % ls -F Makefile index/ invlist_and invlist_and.c # indexの中身を見る % cd index % ls foo fuga hoge piyo # 実行方法 % ../invlist_and foo fuga hoge piyo inverted lists for input query === foo -> 7:1 5 6 7 8 9 10 fuga -> 3:1 4 5 hoge -> 5:1 2 3 4 5 piyo -> 2:4 5 ordered list=== piyo -> 2: 4 5 fuga -> 3: 1 4 5 hoge -> 5: 1 2 3 4 5 foo -> 7: 1 5 6 7 8 9 10 Intersection of piyo and fuga: 4 5 Intersection of last result and hoge: 4 5 Intersection of last result and foo: 5 search result === result num: 1 5
やったー，動いたー．ぱちぱちぱち．転置インデクスを使ったAND検索の中身がわかったでしょうか？
今回のコードをGitHubに置いておきます． <= 今日これが言いたいために書きました．登録だけしていたんですが，生まれて初めてGitHub使ってみました．
参考文献
共通文書IDを取得する積集合演算はなかなか奥が深い．演算を行う転置リストの長さであったり，文書IDが一様に分布している場合と，偏って出現している場合とでは有効な演算が異なってくる．
全部を網羅しているわけではないけれど，転置リストを用いたAND検索のための積集合演算の研究を行っている研究グループはそこまで多くはない．(勝手にそう思っている) 代表的な研究グループ3つの，代表的な論文は以下のとおり．万が一興味があれば，どうぞ．
- R. Baeza-Yates1 and A. Salinger. Experimental Analysis of a Fast Intersection Algorithm for Sorted Sequences. In Proc. SPIRE 2005, pp.13--24, 2005.
- J. Barbay, A. Lopez-Ortiz, T. Lu and A. Salinger. An experimental investigation of set intersection algorithms for text searching. Jornal of Experimental Algorithmics, vol.14, No.7, pp.3.7--3.24, 2009.
- P. Sanders and F. Transier. Intersection in Integer Inverted Indices. In Proc. ALENEX 2007, 2007.
