全文検索 wikipedia|無料辞書
全文検索(ぜんぶんけんさく、Full text search)とは、
コンピュータにおいて、複数の文書(ファイル)から特定の文字列を
検索すること。「ファイル名検索」や「ファイル内文字列検索」と異なり、「複数文書にまたがって、文書に含まれる全文を検索する」という意味で使用される。
◆ 全文検索技術
◇ grep型
順次走査検索、逐次検索とも。「
grep」とは
Unixにおける
文字列検索コマンドであり、複数の
テキストファイルの内容を順次走査していくことで、検索対象となる文字列を探し出す。一般に「grep型」と呼ばれる検索手法は、事前に索引ファイル(インデックス)を作成せず、ファイルを順次走査していくために、検索対象の増加に伴って検索速度が低下するのが特徴である。ちなみに「grep型」とは実際にgrepコマンドを使っているという意味ではないので注意のこと。
◇ 索引(インデックス)型
検索対象となる文書数が膨大な場合、grep型では検索を行うたびに1つ1つの文書にアクセスし、該当データを逐次検索するので、検索対象文書の増加に比例して、検索にかかる時間も長くなっていってしまう。そこであらかじめ検索対象となる文書群を走査しておき、高速な検索が可能になるような索引データを準備することで、検索時のパフォーマンスを向上させる手法が取られている。事前に索引ファイルを作成することをインデクシング(indexing)と呼ぶ。インデクシングにより生成されるデータは
インデックス(インデクス)と呼ばれ、その構造は多くの場合、「文字列 | ファイルの場所 | ファイルの更新日 | 出現頻度…」といったようなリスト形式(
テーブル構造)を取り、文字列が検索キーとなっている。検索時にはこのインデックスにアクセスすることで、劇的に高速な検索が可能となる。
索引文字列の抽出手法
形態素解析
英文の場合は単語と単語の間にスペースが入るため、自然、スペースで区切られた文字列を抽出していけば、索引データの作成は容易となる。しかし日本語の場合は、単語をスペースで区切る「
わかち書き」の習慣がないため、
形態素解析技術を用いて、文脈の解析、単語分解を行い、それをもとにインデックスを作成する必要がある。形態素解析を行うためには解析用の
辞書が必須であり、検索結果は辞書の品質に少なからず影響を受ける。また、辞書に登録されていないひらがな単語の抽出に難があるなど、技術的障壁も多く、検索漏れが生じることが欠点とされる。
N-Gram
「N文字インデックス法」「Nグラム法」などともいう。検索対象を単語単位ではなく一定のN文字単位で分解し、それの出現頻度を求める方法。Nの値が1なら「ユニグラム(uni-gram)」、2なら「バイグラム(bi-gram)」、3なら「トライグラム(tri-gram)」と呼ばれる。たとえば「全文検索技術」という文字列の場合、「全文」「文検」「検索」「索技」「技術」と2文字ずつ分割して索引化を行ってやれば、検索漏れが生じず、辞書の必要も無い。しかし形態素解析によるわかち書きに比べると、意図したものとは異なる検索結果(検索ノイズ=「京都」で検索すると「東京都庁」がヒットするなど)が生じることが多く、インデックスのサイズも肥大化しがちであることが欠点とされる。
その他
他に日本語文書から索引文字列を抽出する手法として、文字種による切り分け、
Suffix Array、
シグネチャ法などがありそれぞれに特長があるが、先の2種に比べると大規模なシステムには適用しづらく、精度の問題もあり主流とはなっていない。
文書フィルタ
検索対象文書が
プレーンテキスト以外、たとえば
HTML文書ならば
タグの除去等の処理を行ってテキストを抽出できるが、特定メーカーの
ワープロ独自形式など
バイナリ形式の場合、インデクサは直接ファイルからテキストを抽出することが出来ないため、
文書フィルタを利用して該当ファイルからテキストを抜き出す必要が生じる。文書フィルタ機能はインデクサが内包しているものもあれば、
アドインなどの機能拡張によって実装する場合もある。
・代表的な文書フィルタ
・
Namazu でPDF文書からテキストを抽出するために利用されることが多い。
・IFilter
・Index Service、Windowsデスクトップサーチのアドインとして各社より提供されている。
・xdoc2txt
・高速Grepソフトウェア「KWIC Finder」からフィルタ部分を抜き出したもの。
Hyper Estraier では標準文書フィルタとして利用されている。
転置ファイル
全文検索用のインデックスには様々な形式があるが、最も一般的なものは単語と、単語を含む文書ファイルのIDとで構成された可変長のレコードを持ったテーブルで、
転置ファイル(inverted file 転置インデックスとも)と呼ばれるものである。インデクシングや実際の検索の際には「
二分探索」などの
アルゴリズムを使って、高速に検索単語から文書IDを探し出すことが出来る。転置ファイルのデータ構造や、採用している探索アルゴリズムは全文検索システムによって様々であり、これらの違いによってインデックスサイズ、検索速度、検索精度に大きな違いが出ることがある。