全文検索エンジンメモ

自然言語処理

検索の種類

逐次検索(grep)型
  • すべてのドキュメントを順次探していく方法
  • ドキュメントの増加により検索速度が低下する
    • 普通に探索、KMP法、BM法など
  • 全部見るので、検索漏れがない
  • 並列化しやすい
Suffix型
  • 事前に全てのドキュメントを検索可能な構造に変換し、メモリにすべてのせ探す方法
  • Trie、Suffix Array/Treeなど
  • PFIのSedue
    • 圧縮したSuffixArrayを用いる
転置インデックス型
  • 事前に全てのドキュメントについて索引データを準備し、それを使って探す方法
  • 索引を探すだけなので高速に処理ができるが、事前準備が必要
    • 本の後ろの索引からページを探すような感じ
  • ドキュメントが変更されたらインデックスの情報も更新しなくてはいけない
  • ドキュメントからの索引用単語の選び方によっては検索漏れが発生する

ドキュメントから索引用の単語抽出

各ドキュメントから索引用の単語を抽出する方法は以下がある。

辞書を使う方法
  • 辞書に登録されている単語について、ドキュメントにその単語があるかどうかで判断
  • キーワードリストなど
形態素解析を使う方法
N-gramを使う方法
  • ドキュメントのN-gramを索引用単語として使用
  • 検索クエリもN-gramにしてから検索する
  • bigramなどは「東京都」が「東京」「京都」になってしまう問題がある

転置インデックスが保持する情報

索引用単語に対して何を保持しておくかは、以下がある。
転置インデックス自体はkey-valueストアなどでも保持できる。

文書IDのみ保持
  • 「天気 -> 1,3,5」など
文書ID＆単語出現位置を保持
  • 「天気 -> (1,15),(3,5),(5,59)」など
  • 出現位置を保持する利点
    • 検索結果のスニペット表示
    • 複数クエリのドキュメント内の位置的な距離を計算できる(scoreとして利用、n-gramが連続しているかどうかのチェック)

転置インデックス型全文検索エンジンの流れ

  • 検索対象ドキュメントを集める(クローリング)
  • 検索対象ドキュメントから索引を抽出(インデクサ)
  • 転置インデックスを作成(インデックス作成)
  • 検索クエリで、索引を問い合わせ(問い合わせ)
  • インデックスから対応ドキュメントを返す(検索結果)
    • 必要ならば、スコアにより並び替えて表示(スコアリング＆ランキング)

参考文献

  • web開発者のための大規模サービス技術入門 -データ構造、メモリ、OS、DB、サーバ/インフラ-
  • wikipedia - 全文検索