プログラマブログ

by wacul

menu

2014.06.11Node.js と MongoDB で n-gramを使って全文検索

n-gram による検索

現在、自社開発を行っているプロジェクトではサーバサイドはnode.jsで開発しています。
そして、DBはMongoDBを採用し、node.jsからMongoDBへのアクセスは mongooseを使用しています。

今回、DBに保存されている「お客の名前」を検索したいという要求が生じました。
検索条件として、名前の途中でもヒットするようにする必要があります。
例えば「あい」で検索した場合、以下のような名前がヒットします。

  • あいかわたろう
  • あいだはなこ
  • やまだあいこ
  • おちあいじろう

また、上記の例で「あいだ」で検索した場合は以下の名前がヒットします。

  • あいだはなこ

このような検索を実現するために、n-gramによる検索を実装しました。
n-gramは文字列を nの長さで1文字ずつずらして切り出して保存します。

  • n = 2 のとき 「あいかわたろう」という文字列
    「あい」「いか」「かわ」「わた」「たろ」「ろう」

今回は、2文字以上の文字列で検索がヒットするようにしたいので、n = 2 の bi-gramを実装します。

mongoose での model 定義

bi-gramで分割した文字列を、array で保存します。 mongooseの定義は以下のようになります。
また、検索の高速化のため、indexを張っておきます。

1
2
3
4
5
6
7
customerSchema = new Schema {
  name :  String,     //名前を保存するフィールド
  bigram : {          //名前をbi-gramで分割した文字列を保存するフィールド
    type : [String],
    index : true
  }
};

さらに保存時に自動的にngramを生成したいため、preの’save’をフックします。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
customerSchema.pre('save', function(next){
  if(this.isModified('name')){
    //変更があった時のみ生成する
    this.bigram = textToNgram(searchWord, 2);  // bi-gramで分割して配列にする
  }
});

/**
* 文字列をn-gramで分割して返す
* @param {string} text - 分割対象の文字列
* @param {number} n - 分割数  bi-gramなら2
* @return {array} 分割した文字列をarrayで返す
*/
function textToNgram(text, n){
  ngram = [];
  for(var i = 0; i <= text.length - n; i++){
    ngram.push(text.substr(i, n));
  }
  return ngram
}

検索をする

検索するときも、検索文字列をbi-gramで分割します。
この分割した文字列をMongoDBのクエリにある $all を使うことによって、検索できます。
$all は保存されているarrayフィールドに対して、クエリで渡したarrayの内容がすべて含まれているものを抽出できます。

mongooseのスキーマに投げるクエリは以下のようになります。

1
2
3
4
5
6
7
8
//検索対象の文字列をbi-gramで分割して、arrayに入れます。
searchWordBigram = textToNgram(searchWord, 2)

query = {
  bigram : {
    $all : searchWordBigram
  }
}

正しくない検索のケース

上記手法は検索文字列の順番を見ていないため、一部、正しくない検索結果が返る場合があります。
例えば、 「あいう」 というワードで検索した場合、「あいおいう」というワードもヒットします。 こういう特性があるので、使用する際は注意が必要です。

この記事を書いた人enokido

榎戸です。趣味ではゲームを作っています。

waculでは、プログラマを募集しています。

現在はプロダクトとして、課題発見から改善提案まで自動で行うWeb改善プラットフォーム「AIアナリスト」を開発中です。

waculの採用情報へ

ページトップへ