JavaScriptで転置インデックスを作る

先日ngramに分割する処理を書いたので次は転置インデックスを作ってみます。 今回は完全に単語の位置まで記録するものとし、

{'晴天': { '0': [ 3 ] }}

といった具合で2-gramで分割された単語とそれに対応する文書とその位置が管理されるものとします。上の例だと「晴天」という単語は文書番号0の3文字目に記録されているといった具合。

var invertedIndex = {}

var ngram = function(words, n) {
  var i;
  var grams = [];

  for(i=0; i<=words.length-n; i++) {
    grams.push(words.substr(i, n).toLowerCase());
  }

  return grams;
}

var indexing = function(no, str) {
  ngram(str, 2).forEach(function(gram, index, array) {
    var postingList;

    if (invertedIndex[gram]) {
      postingList = invertedIndex[gram];
    } else {
      postingList = {};
    }

    if (postingList[no]) {
      postingList[no].push(index);
    } else {
      postingList[no] = [index];
    }

    invertedIndex[gram] = postingList;
  });
}

これに対して文書を与えることで2-gramな転置インデックスが作成されます。

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

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

実際に転置インデックスを覗いてみます。

> console.log(invertedIndex)
{ '本日': { '0': [ 0 ] },
  '日は': { '0': [ 1 ], '2': [ 1 ] },
  'は晴': { '0': [ 2 ] },
  '晴天': { '0': [ 3 ] },
  '天な': { '0': [ 4 ] },
  'なり': { '0': [ 5, 12, 19 ] },
  'り。': { '0': [ 6, 13, 20 ] },
  '。い': { '0': [ 7 ] },
  'いい': { '0': [ 8 ] },
  'い天': { '0': [ 9 ] },
  '天気': { '0': [ 10 ] },
  '気な': { '0': [ 11 ] },
  '。コ': { '0': [ 14 ] },
  'コロ': { '0': [ 15 ], '1': [ 0 ], '2': [ 8, 13, 15, 22 ] },
  'ロス': { '0': [ 16 ], '2': [ 9 ] },
  'スケ': { '0': [ 17 ], '1': [ 7 ], '2': [ 10 ] },
  'ケな': { '0': [ 18 ] },
(以下省略)

といった具合。「コロ」という語が文書番号2(text変数の3番目の配列)に頻出しているので確認できやすいですね。

じゃ、次はこれを使って検索してみようということになるので、これはまた次回。