redisで作成した転置インデックスで検索してみる

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

前回のエントリで転置インデックスをredisに作ってみるところまではできたので、次は実際にこれを利用して検索を行ってみます。

前回はbi-gramで文章を分割し、分割語を転置インデックスとして以下の形で格納しています。それぞれ、

(A)分割語が属す文書番号を管理するセット型の集合
(B)特定の文書に特定の分割語の出現位置を管理する文字列型の集合

これを利用して検索を行うために以下の手順で処理を進めます

(1) 与えられた分割語をbi-gramで分割する

ここでは検索語として「コロスケ」を考えます。bi-gramなので、コロ, ロス, スケ に分割。

(2) 分割語が全て含まれる文書を特定する

(A)のセット型の集合に対してSINTERコマンドを発行して各分割語が全て含まれる文書番号を抽出します。

127.0.0.1:6379> SINTER コロ ロス スケ
1) "9"
...

(3) (2)で得られた文書中の分割語の出現位置を確認

(2)で得られた分割語が全て含まれる文書、それぞれに対して分割語毎にその出現位置を確認し、その語が連続しているかを確認します。例えば、コロ, ロス, スケの分割語が文書番号9で含まれていることが(2)でわかっていれば、その出現位置が連続で出現するかを確認します。

127.0.0.1:6379> GET コロ-9
"3"
127.0.0.1:6379> GET ロス-9
"4"
127.0.0.1:6379> GET スケ-9
"5"

この場合は文書番号9の3文字目から分割語が連続で出現していることから、「コロスケ」という単語が文書番号9の3文字目に含まれていることがわかります。

上記までの内容をまとめると以下の様な概要図になります。

実際にnode.jsで書いてみた例は以下の形になりました。

'use strict';
var ngram = require('../util/ngram'),
    _ = require('underscore'),
    redis = require("redis"),
    client = redis.createClient();

var search = {};

search.basic = function(query, n, callback) {
  var grams = ngram(query, n),
      results = [];

  client.sinter(grams, function(err, documentNumbers){
    if (documentNumbers.length == 0) {
      client.end();
      callback(null, results);
    }

    documentNumbers.forEach(function(docNo) {
      var positions = grams.map(function(gram){
        return gram + "-" + docNo
      });

      client.mget(positions, function(err, res){
        var charPositions = res.map(function(pos){
          return pos.split(",").filter(function(e){return e !== ""}).map(function(e){return parseInt(e)});
        });

        for(var i=1; i<charPositions.length; i++) {
          charPositions[i] = charPositions[i].map(function(v) {return v-i});
        }

        charPositions.reduce(function(a,b) {return _.intersection(a,b)}).forEach(function(position) {
          results.push({no:docNo, pos:position});
        });

        if (docNo == documentNumbers[documentNumbers.length - 1]) {
          client.end();
          callback(null, results);
        }
      });
    });
  });
}

module.exports = search;