転置インデックスをredisで永続化する - テノニッキ (@hideack 's diary)

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

過去に転置インデックスを利用して検索してみるといったエントリを書いてJavaScriptのハッシュで構成された転置インデックスを利用して検索を試みていたが、このままだと永続化できないのでredisを用いて永続化してみた。

node.jsでredisを扱う場合はnode_redisを利用するのがよさそうなのでnpm経由でインストール。

$ npm install redis --save

使い方はそのままの形なので先のgithubのREADME.mdを参照すれば特に支障なく利用できるかと思う。基本的にはredisのコマンドがそのままメソッドとして実装されているので、見た感じそのままである。

今回は転置インデックスをredisに格納するにあたって、以下の方法で実装してみた。ここはひとまずとりあえず。

該当の単語が出現する文書番号を格納
- redisのセット型
- keyを単語とし、その集合として文書番号を格納
該当の単語が特定の文書中に出現する位置を格納
- redisの文字列型
- keyで単語と文書番号を表現し、その値に出現位置をカンマ区切りで格納

としてみた。

こうすることで、検索語が与えられた場合、その検索後を転置インデックスに対応する形で単語分割し、その単語が全て含められる文書を絞り込んだ上で、更に転置インデックスを参照して該当する単語が含まれる位置を探すことで検索が実現できそう。

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

var index = {};

var indexing = function(no, str) {
  ngram(str, 2).forEach(function(gram, pos, array) {
    client.sadd(gram, no);
    client.append(gram + "-" + no, pos + ",");
  });
}

index.redis = function(path) {
  client.flushdb(function(err, didSucceed) {
    var stream = byline(fs.createReadStream(path, { encoding: 'utf8' }));

    var i=0;
    stream.on('data', function(line) {
      indexing(i, line);
      i++;
    });

    stream.on('finish', function(){
      client.end();
    });
  });
}

module.exports = index;

こうすることでredisに転置インデックスを格納することができた。

では、ここまでで転置インデックスの永続化はできたので、実際にこれを利用して検索するのはまた次に。

併せて読みたい