転置インデックスを利用して検索してみる

n-gram及び、転置インデックスを作ってみたので実際に検索してみます。

ngram や indexing は上の記事で書いた関数がそのまま入ります。

var _ = require('underscore');

// (snip)

var search = function(query, n) {
  var grams = ngram(query, n),
      firstPostingList = invertedIndex[grams[0]],
      results = [];

  var searchProcess = function(positions, key) {
    positions.forEach(function(pos){

      if (query.length <= n) {
        results.push({no:key, pos:pos});
      } else {
        for(var i=1; i<grams.length; i++) {
          postingList = invertedIndex[grams[i]];

          if (postingList[key]) {
            var targetList = postingList[key];

            if (_.contains(targetList, pos + i)) {
              if (i == grams.length - 1) {
                results.push({no:key, pos:pos});
              }
            } else {
              continue;
            }
          }
        }
      }
    });
  };

  _.each(firstPostingList, searchProcess);
  return results;
}

// Indexing
var text = [
  "本日は晴天なり。いい天気なり。コロスケなり。",
  "コロばない様にスケートボートに乗ります",
  "今日は黒豆を煮てコロスケとコロコロコミックとコロッケを買いに行きます。コロスケ〜。"
];

for(var i=0; i<text.length; i++) {
  indexing(i, text[i]);
}

// Search
var res = search("コロスケ", 2);

// Results
var resultOut = _.template("文書番号=<%=no %> : 文字位置=<%=pos %>")

_.each(res, function(v){
  console.log(resultOut(v));
});

これを実行してみると、「コロスケ」で検索した結果が出力されます。

文書番号=0 : 文字位置=15
文書番号=2 : 文字位置=8
文書番号=2 : 文字位置=35

インデックスに投入した文書とくらべて、検索した単語が含まれる文書が抽出できていて且つ、出現位置も正しく特定できています。

やっていることとしては、

検索語をn-Gramで分割する (上の例なら "コロスケ" → "コロ", "ロス", "スケ")
分割された最初の分割語を持つ文書とその出現位置を転置インデックスから得る
得られた一つ目の文書について
- 2番目の分割語がその文書に含まれているか確認する
- 含まれていればその語の出現位置が1番目の検索語の次にあるかを確認する
- 以下、検索語を分割した数だけ繰り返す
以下、分割された最初の分割語が含まれる文書数繰り返す

といった手順。

ひとまず素朴な検索ができたけれど、このままだと転置インデックスが永続化されないですね。

では、次に何かしらのストレージを利用して永続化させることをやってみます。

一連のn-gram, 転置インデックス, 検索の話は以下の本を読んでいたら実際に手を動かして確認したくなったので試してみたのでした。

具体例も多く、読んでいても面白いですが実際に手を動かすともっと面白いのでお勧め。

今回の話は第4章「検索しよう」の内容を読みながら進めてみました。

検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏