Edited at

全文検索ことはじめ

More than 3 years have passed since last update.


全文検索の至上命題


  • 速く検索する

  • 精度よく検索する


インデックス

インデックス=索引

全てのデータを調べて検索された条件を探し出すのは遅いため、高速化のために

本の末尾の「索引」と同様に、ある情報(単語など)がどこに存在するかの対応付けを作成する

ハッシュであったりツリーであったり、データ構造の実装は様々


全文検索におけるインデックス

一般的に検索対象の文字列を決まったルールで分割し、

分割した語彙が含まれる文書一覧の対応付け(ポスティングリスト)をインデックスとする。

分割するルールは下記が代表的。


形態素

意味のある単語ごとに分割して、それぞれの単語の索引を作成

 東京都 → 東京 + 都

※形態素解析では上記だけの分割になるとは限らない。

「ひがしきょうと」という地名の「東 + 京都」という分割も有り得るし

「東京都」という単語も一つの意味のある単語となる。


N-gram

機械的に N 文字ごとに分割して、それぞれの単語の索引を作成

N = 2 の場合、

 東京都 → 東京 + 京都 + 都

となる。(最後の「都」は 2文字ではないが、「都」だけで検索された時のための index として必要)

分割した N 文字ずつの索引から対象の文書を探し出し、

N + 1 文字以上の場合、その文字列が含まれているかを確認(PostgreSQL では recheck という)

ex.) 「東京と京都」という文章には「東京」「京都」が含まれているが、

「東京都」は含まれていない


pg_bigm と Groonga における確認ロジックの違い

pg_bigm

 元の文字列をシーケンシャルに確認(全部なめる)

  ⇒ヒットが多いとき、元の文字列が長いときは遅くなってしまう

Groonga

 元の文字列において何番目に出現したかをインデックスで保持しておく

  ⇒データサイズが大きくなる インデックスのデータサイズも Groonga のほうが小さい

   wikipedia の全文検索であれば pg_bigm より高速


スコアリング

検索対象を「ユーザーの欲しい度合」と考えられうる順に並べる。

まずは下記の二つの要素を考えるとよい。


  • 確実性

  • 重要性


確実性

確実性が高いものに高いスコアを付与する


  • 完全一致のものは確実性が高い

  • キーワードの検索条件より、選択されたエリア等のデータのが確実性が高い

  • GPS の位置情報など、ユーザが入力したものではないデータの方が確実性が高い場合もある

  • ユーザが任意に付与できるタグ等は確実性が低くなる傾向がある(Qiita のタグなど)


重要性

重要性が高いものに高いスコアを付与する


  • 必須項目とオプション項目がある場合、必須項目の方が重要

  • ブログ記事であれば重要度は ブログタイトル > 記事本文 > 脚注 となるのが一般的