cocone engineering

こんにちは。ポケコロサーバー開発を担当しているNです。
今回はポケコロのタグ検索で使った全文検索の方法について紹介したいと思います。

まずはポケコロのタグ機能である「ポケタグ」について簡単に紹介します。

ポケタグとは

好きなことや興味があることを自分のプロフィールにタグを付けて、共通のタグを付けている友だちを探したり、共通のタグが多い友だちをおすすめする、いわゆるハッシュタグをベースとした友だち検索（友だちマッチング）の機能です。

今回紹介する機能は、タグを部分一致で検索してサジェストする機能です。
検索回数が多いことと、文字を入力するたびに検索を行うため早いレスポンスが要求されます。

全文検索を実現するため、主に下記の方法が使われています。

上記以外にも全文検索機能を提供する構造体（例えば ConcurrentRadixTree ）を利用するなど様々の方法がありますが、今回は N-Gram と Redis を利用して直接実装することにしました。

基本になるタグのマスタは MongoDB に入っています。

まず、今回使用する N-Gram と Redis SET の SINTER コマンドについて理解しておきましょう。

N-Gram とは
任意の文字列や文書を連続した n 個の文字で分割するテキスト分割方法．特に，n が 1 の場合をユニグラム（uni-gram），2 の場合をバイグラム（bi-gram），3 の場合をトライグラム（tri-gram）と呼ぶ。例)「ポケとも募集」というタグを N-Gram で分割した例
※ 3文字で分割した例

つまり、ある文章を指定した文字数（ N ）で分割するテキスト分割方法です。

処理の内容

1. 転置インデックスを作成

全文検索するためには転置インデックスを作成する必要があります。
今回は転置インデックスを Redis の SET として作成します。

下記のようなタグマスタを例で説明します。

まずタグの文字列を N-Gram で分割します。今回は 2 文字分割の BI-Gram を使用しました。

分割した N-Gram の文字列に Prefix（この例では “TAG_” ）をつけて、それをキーに Redis の SET としてタグ ID を保存します。

※ Prefix は転置インデックスを識別するためにつけています。不要な場合は付けなくていいと思います。

他のすべてのタグも繰り返し作成します。
作成が終わるとこのようなイメージになります。

2.転置インデックスで検索を実行する

検索するときも検索キーワードを N-Gram で分割します。
分割した N-Gram のキーワードで SINTER コマンドを実行して Redis から共通するタグ ID を探します。

検索キーワードが「とも募」の場合を例で説明します。
検索キーワードの「とも募」を BI-Gram で分割したら[とも, も募]になります。

キーの Prefix である ”TAG_” をそれぞれのワードに結合して Redis で共通のメンバー（タグ ID ）を検索してみましょう。

「とも募」が含まれているタグ ID 1、3が検索されました。

ソースコードは下記のようになります。

転置インデックスの作成

int tagId = 1;
String tag = "ポケとも募集";

Set nGramSet = this.buildNGram(tag);  // [ポケ, ケと, とも, も募, 募集]

for (String nGramWord : nGramSet) {
   String key = this.getNGramTagKey(nGramWord); // "TAG_" + nGramWord
   this.redisClusterTemplate.opsForSet().add(key, tagId);
}

... 

// N-Gram作成
public Set buildNGram(String tagName) {

   int n = 2;     // bigram

   Set grams = new LinkedHashSet<>();
   if (tagName.length() < n) {
       return grams;
   }
   String[] strArr = toArray(tagName);
   for (int i = 0; i <= strArr.length - n; i++) {

       StringBuilder sb = new StringBuilder();
       for (int j = i; j < i + n; j++) {
           sb.append(strArr[j]);
       }
       grams.add(sb.toString());
   }
   return grams;
}

SINTERで共通のタグID検索

String searchKeyword = "とも募";

// N-Gram作成
Set nGramSet = this.buildNGram(tag); // [とも, も募]

// Redisキーへ変換 [“TAG_とも”, “TAG_も募”]
Set redisKeySet = nGramSet.stream().map(this::getNGramTagKey).collect(Collectors.toSet());

// SINTERで検索 -> SINTER TAG_とも TAG_も募
Set searchResultTagIdSet = this.redisClusterTemplate.opsForSet().intersect(redisKeySet);

// 検索結果 : 1, 3

まとめ

今回は N-Gram と Redis を利用して簡単に全文検索を実装した例を紹介しました。
実際は全角 / 半角を変換したり漢字の読み方、ひらがな / カタカナを変換したりして転置インデックスを作成したら、よりヒットしやすく応用することもできると思います。
短いキーワードの全文検索を実装する場合の一つの選択肢としてご参考になればと思います。