転置インデックスを利用した検索とgrepによる検索を比較してみる

検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏を読んでみたところから続く検索してみるシリーズ。

前回作成した検索の処理をもって転置インデックスを作成するところから、それを利用した検索までの一連の流れができたので次は実際にいくらか大きめのデータを入れて比較してみることにします。

いままで作成したnode.js + redisベースの実装はremieraという名前を付けてgithubに置いています。一応、コマンドライン引数でインデックス対象のファイルを指定したり検索ができる様にしています。

<a href="http://github.com/hideack/remiera">hideack/remiera</a>

インデックス対象の文章はテキストファイルで与えられるものとして、1行が1文章として扱われる様になっています。

今回は大きめのデータのサンプルということで本に倣ってWikipediaのタイトル2,654,075件の文字列をサンプルとして投入します。

$ wc -l ~/tmp/wikipedia/jawiki-latest-all-titles
2654075
$ time remiera -i ~/tmp/wikipedia/jawiki-latest-all-titles
remiera -i ~/tmp/wikipedia/jawiki-latest-all-titles  1011.13s user 229.40s system 99% cpu 20:44.89 total

redis自体もコード自体も何もチューニングをしていない状態で20分程度要しました。

では、まずは比較として先ほどインデックス対象としたファイルを素朴にgrepで検索してみます。

$ time grep -n コロスケ ~/tmp/wikipedia/jawiki-latest-all-titles
969851:奈良崎コロスケ
2180964:コロスケ
2180965:コロスケ123123
2180966:コロスケ准将
2180967:コロスケ＠1億円
grep -n コロスケ ~/tmp/wikipedia/jawiki-latest-all-titles  1.46s user 0.01s system 99% cpu 1.479 total

grepでは1.4秒強程度要しています。

次は転置インデックスを使って検索を行ってみます。

$ time remiera -s コロスケ
[ { no: '969850', pos: 3 },
  { no: '2180964', pos: 0 },
  { no: '2180965', pos: 0 },
  { no: '2180963', pos: 0 },
  { no: '2180966', pos: 0 } ]
remiera -s コロスケ  0.09s user 0.03s system 74% cpu 0.156 total

現状の実装では文書番号と出現位置で返るだけですが、0.09秒程度*1で結果が得られています。

インデックスする際に文書番号は0から始めているため 行番号 = 文書番号-1 となっています。これが先ほどのgrepした結果と検索結果とが一致していることもこの結果から確認できます。