カテゴリー:
検索エンジン
閲覧数:339 配信日:2017-03-05 22:19
A.全文照合方式 ／ 全文書走査
検索対象の文書をすべて走査して，一致する文字列を含む文書を探す方法
・クエリ発行後、検索対象の文書1つ1つが「クエリ単語」を含んでいるのかチェックする
・非常に簡単に実装できる（UNIXの「grep」コマンドで実装できる）
・全文を突っ込んだフィールドに対して LIKE 演算子で単純な中間一致検索
・便利
・最も単純な手法
全文照合アルゴリズム
・KMP(Knuth-Morris-Pratt)法
・BM(Boyer-Moore)法
問題点
・検索のたびに対象のテキストデータをメモリ上に読み込んで照合処理を行うため，大量の検索対象の場合，どうしても検索時間がかかる
・クエリ発行後に対象文書集合を走査するため、「対象となる文書の数が大きくなると、検索に時間がかかり過ぎる」
・単純な中間一致検索は対象のデータを毎回全文嘗め回すので、データ量が増えるとそれに比例して遅くなってしまう
向いている対象
・検索対象が少量
・検索回数も少ない
B.索引方式 ／ インデックス
予め検索対象の文書をいったんメモリ上に読み込み，検索語に対応する索引データを作成する前処理を行う
・検索時には，予め作成されている索引を元に，合致した文書を見つけ出す方法
・ユーザーがクエリを発行した際、インデックスを持つ検索エンジンは自身のインデックスを調べてクエリ単語を含む文書集合を返す
・ここでいうインデックスは「どの文書が、どの単語を含むのか」という情報を保存するテーブル
・大量の文書集合を高速に検索できる
特徴
・高速に大量の文書を検索するのに向いている
・クエリを含む文書を収集する時間を短縮できる
・インデックスを利用した検索システムと全文書のコンテンツを走査する検索システムを比較すると、多くの場合インデックスを利用した検索システムの方が高速に動作する
・検索対象となる文書数（量）が大きくなっても、検索性能はそれほど劣化しない（注：正確には検索エンジンを保持する計算機のメモリ量とインデックスの大きさなどに依存する）
・大規模データを扱う高負荷な環境では、インデックスの利用が「ほぼ必須」
問題点
・予め索引を作成する必要がある
・索引の作成処理は，かなり負荷の高い処理
向いている対象
・検索対象が大量
・頻繁に検索
インデックスのデータ構造の種類
・「転置」インデックス
・「接尾辞配列」インデックス
利用される手法
・形態素解析方式
・N-Gram方式