研究室‎ > ‎卒業生のみなさまへ‎ > ‎LUU TUAN ANH‎ > ‎読書‎ > ‎

検索エンジン

久保木先輩に紹介してくれたSearch Engineを読んでいます。すごく面白くて、わかりやすいです。

検索エンジンの仕組み：


  • 索引構築部（Indexer, インデクサー）
    • 索引構築部では，検索したいテキスト文書を検索しやすいフォーマット（索引）に変換する作業を担当します。
    • 転置索引や接尾辞配列などの索引構造
  • 検索部（Searcher, サーチャー）
    • 索引部に対して検索処理が行われます
    • 検索処理自体はシンプルな場合が多い
  • 索引（Index, インデックス）
    • 索引部は，索引構築部で構築された索引そのものになります。
    • ファイルはディスク上に保存される場合が多い
    • 圧縮されます

転置索引

  • 転置索引＝辞書＋転置リスト
  • 辞書は単語だけでなく，その単語に対応するポスティングリストの位置情報を含んでいます
  • ポスティングリストは，どの文書に出現するかを表すのに最低でも文書のID（数値）が必要となります
  • ブーリアン検索（Boolean Retrieval）
  • Document-level inverted list
  • Word-level inverted list
  • フレーズ検索

辞書の実装

  • 小規模、中規模には,Binary Search Tree.
    • メモリの上で実行するので、早い。
    • ディクスの上では、あまり効率ではない。
  • 大規模には
    • ディクスに保存しなければならない。
    • B+木の方が早い。
  • 計算量を考慮するだけじゃなくて、実行時間も大事。

転置リストの実装

  • ポスティングリストの圧縮
  • 通常ポスティングリストはディスク上に格納され，パフォーマンスの観点から，リストはディスクの連続した領域に格納されることが多い

日本語(東南アジアの言語)における転置索引

  • 形態素解析：
    • ノードの数が少ない
    • 構築処理，検索処理も速く
    • 検索漏れが生じてしまう
    • 未知語の問題
  • N-gram：
    • 検索漏れが発生しない
    • 辞書のサイズ，転置リストのサイズが大きく
  • 現代の検索エンジンは，文の分割方法に依存しないように設計されることが多い
    • 文書の特性に応じて形態素解析とN-gramを使い分けられる
    • 文字の位置のオフセットでインデックスする

転置索引の構築

  • 転置索引は多くの場合はメモリより大きいので、ディスクを用いた構築方法が必要となる。
    • Sort-based Inversion
      • Sort-based Inversionではすべての辞書をメモリ上に保持するため，扱う文書数が多くなる場合には問題となり，また，ディスクベースでソートを行うためI/Oコストも大きくなります。
    • Merge-based Inversion
      • 一般的にはMerge-based Inversionによる構築方法の方が効率的であると考えられています。
  • 構築方法の種類
    • 静的な構築方法
      • 静的な構築方法では，入力データに対して構築処理を行い，それらの処理の完了時に検索可能となるように構築する方法となります。
      • 静的な方法は文書の到着(作成)から索引への反映までに多くの時間が許容できる場合に用いられる。
    • 動的な構築方法
      • 動的な構築方法では，索引構造を常に検索可能，かつ，最新の状態に保つように構築する方法になります。
      • 動的な方法は，検索可能になるまでの待ち時間をほんの少ししか許容できない場合に用いられる方法。

転置索引における検索処理

  • 検索の流れ

    • 疑似コード

       1: sort Q by the length of each term's posting list
 2: t = shift Query
 3: posting_list = FetchList(term)
 4: for all t ∈ Q do
 5:   t = shift Query
 6:   posting_list = Intersect(posting_list,t)
 7: end for
 8: array = NewArray()
 9: for all Di ∈ DocIDs(posting_list) do
10:   arrayi =CalcRelevancy(Q,Di) or GetAttribute(Di)
11: end for
12: HeapSortK(array)
13: Identify the k greatest arrayi values and return the corresponding documents.

    • 関連度によるランキング
    • 情報検索とは：
      • 文書とクエリの関連度のみを考慮した検索
      • 1つでもクエリ中のタームを含む文書とクエリの関連度を考慮した検索

Comments