全文検索
出典: フリー百科事典『ウィキペディア(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文字ずつ分割して索引化を行ってやれば、検索漏れが生じず、辞書の必要も無い。しかし形態素解析によるわかち書きに比べると、意図したものとは異なる検索結果(検索ノイズ=「京都」で検索すると「東京都庁」がヒットするなど)が生じることが多く、インデックスのサイズも肥大化しがちであることが欠点とされる。
-形態素解析とN-gramの比較-
形態素解析 | N-gram | |
インデクシング速度 | 遅い | 早い |
インデックスサイズ | 小さい | 大きい |
検索ノイズ | 少ない | 多い |
検索漏れ | 多い | 少ない |
検索速度 | 速い | 遅い |
言語依存 | 辞書が必要 | 辞書が不要 |
[編集] 文書フィルタ
検索対象文書がプレーンテキスト以外、たとえばHTML文書ならばタグの除去等の処理を行ってテキストを抽出できるが、特定メーカーのワープロ独自形式などバイナリ形式の場合、インデクサは直接ファイルからテキストを抽出することが出来ないため、文書フィルタを利用して該当ファイルからテキストを抜き出す必要が生じる。文書フィルタ機能はインデクサが内包しているものもあれば、アドインなどの機能拡張によって実装する場合もある。
- 代表的な文書フィルタ
- Xpdf
- IFilter
- MSN サーチ ツールバー with Windows デスクトップ サーチの機能拡張
- Index Service、Windowsデスクトップサーチのアドインとして各社より提供されている。
- xdoc2txt
- http://www31.ocn.ne.jp/~h_ishida/xdoc2txt.html
- 高速Grepソフトウェア「KWIC Finder」からフィルタ部分を抜き出したもの。Hyper Estraier では標準文書フィルタとして利用されている。
[編集] 転置ファイル
全文検索用のインデックスには様々な形式があるが、最も一般的なものは単語と、単語を含む文書ファイルのIDとで構成された可変長のレコードを持ったテーブルで、転置ファイル(inverted file 転置インデックスとも)と呼ばれるものである。インデクシングや実際の検索の際には「二分探索」などのアルゴリズムを使って、高速に検索単語から文書IDを探し出すことが出来る。転置ファイルのデータ構造や、採用している探索アルゴリズムは全文検索システムによって様々であり、これらの違いによってインデックスサイズ、検索速度、検索精度に大きな違いが出ることがある。
- 転置ファイルの例 -
単語 | 文書ID |
サーチ | 1, 3, 4 |
デスクトップ | 2, 4, 7 |
解析 | 3, 5, 6, 7 |
形態素 | 2, 6, 7 |
検索 | 1, 6 |
全文 | 1, 6, 7 |
※二分探索を行うためには単語と文書IDはソート済みでなければならない
[編集] 主な用途
- www検索サービス
- 検索サービスの中では、超大型の機能が求められる分野で、一握りのプレーヤーによる熾烈な競争が行われている。ウェブの初期から行われていたサービスのひとつで、技術の進歩もめざましい。
- 企業向け社内検索サービス
- 社内ファイルサーバの文書資産を高速全文検索するシステム。WordやExcelといったオフィススイートから、メール、データベースなどの多くのファイル形式に対応し、企業の性格に応じて、多様な検索結果を返す。近年、電子データの企業資産の重要性が増し、非常に発達してきている分野。
- デスクトップ検索
- 個人のローカルファイルを検索するためのアプリケーションソフトウェア。Word,Excel,PDFなど様々なファイル形式に対応している。また、画像データなどの、個人の保有にあるマルチメディアデータの検索に特化したものもあり、スピードと手軽さが求められている。
[編集] 代表的な全文検索エンジン
[編集] サーバ/ワークステーション向け
- Namazu
- 全文検索システム Namazu
- わかち書きベース。
- 2単語によるフレーズからハッシュ値を計算し保持することによって、フレーズ検索が可能。フォルスドロップ(false drop=誤った候補)あり。
- 日本で広く使われている全文検索システム。
- 無償。
- Hyper Estraier
- 全文検索システム Hyper Estraier
- N-gramベース(N.M-gram)。わかち書き方式も併用可。
- 分散インデクス、Webクローラ、検索用CGIなど標準添付のプログラムが充実。
- N.M-gram方式とは、N文字に続くM文字のハッシュ値を計算し保持することによって、フレーズ検索が可能。フォルスドロップあり。
- 大規模なインデックスも作成可。
- 無償。
- Rast
- 全文検索システムRast
- わかち書きベース・N-gramベースの選択
- 単語の出現位置情報を保持し、正確なフレーズ検索が可能。フォルスドロップなし。
- 無償。
- Lucene
- Apache Lucene
- Analyzerと呼ばれるクラスを選ぶことにより、N-gramやわかち書き形式でのインデックス作成ができる。
- Javaによる全文検索システム。
- Wikipediaの検索に使われている。
- 大規模なインデックスも作成可。
- 無償。
- Senna
- Senna 組み込み型全文検索エンジン
- わかち書きベース・N-gramベースの選択
- 他のプログラムからライブラリとして呼び出して利用する。
- MySQLの中に全文検索エンジンを組み込むパッチが提供されており、MySQLを利用しているプログラムであれば全文検索機能を手軽に実現できる。
- PostgreSQLに対して、Sennaを全文検索エンジンとして組み込むためのモジュールLudiaが公開されている。
- perlバインディングにより、perlスクリプトから簡単に利用することができる。PHP, Ruby, Pythonバインディングも提供されている。
- 大規模なインデックスも作成可。
- 無償。
- SMART/InSight 2.0
- ウチダスペクトラム株式会社)
- 形態素解析、N-gram選択可。
- ActiveDirectoryなどのACL継承機能有り。
- 非常に高速なFastDataSearchをエンジンとして使用。
- 有償。
- Oracle Secure Enterprise Search
- Oracle Japan / Oracle Secure Enterprise Search 10g)
- N-gramベース(V-gram)。
- ログインしたユーザーが参照可能な結果のみを表示するセキュア検索が特徴。
- 有償。
[編集] 個人向け
- FindFast(マイクロソフト)
- MS Office97/2000に標準搭載されていた。
- 2時間おきにインデックス更新。CPU負荷が極めて高いためユーザーの評判は悪かった。
- Officeファイルが対象であり、メール検索などはできない。
- インデックスサービス(マイクロソフト)
- Windows2000/XPに標準搭載。
- アプリケーションではなくサービスとして提供されているため使いづらい。
- デフォルトではオフとなっているため利用者は少ないと思われる。
- ローカルディスク全体をインデックス化できるが、CPU負荷は高くなる。
- メール検索には非対応。
- 今後はWindows デスクトップサーチをベースにしたシステムに取って代わられていくと思われる。
- Google デスクトップ(Google)
- http://desktop.google.com/ja/
- わかち書きベース。
- 利点:Google web検索と同じエンジンでローカルファイルを検索できる。
- 欠点:大きなファイルの場合、後半部分がインデックス化されないなどの問題。
- 無償。
- Windows デスクトップサーチ(マイクロソフト)
- http://desktop.msn.co.jp/
- わかち書きベース
- 利点:検索対象フォルダを詳細に設定可能。ネットワークドライブにも対応。
- 欠点:単独でのリリースが企業向けのものしかされていない。
- 正式には「MSN サーチ ツールバー with Windows デスクトップ サーチ」というパッケージで配布されている。
- 無償
- サーチクロス(ビレッジセンター)
- http://www.villagecenter.co.jp/soft/searchx/
- 形態素解析によるわかち書きは採用せず。
- 詳細なアルゴリズムは不明だが、文字種により単語を分割し、インデックスに登録していくタイプと思われる。
- ひらがなは事前に辞書登録されたもの以外は検索できない。
- アルゴリズムが単純な分、インデクシングが極めて高速。
- 有償。
- コンセプトサーチ(ジャストシステム)
- http://www.justsystem.co.jp/conceptsearch/
- 自然言語による検索が可能。
- 文書管理アプリケーションDocuWorks(富士ゼロックス)のバージョン6.0より「ExpandFinder」という名称でバンドルされている。
- 有償