/ 
/ 
全文検索
出典: フリー百科事典『ウィキペディア（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 | |
|---|---|---|
| インデクシング速度 | 遅い | 速い |
| インデックスサイズ | 小さい | 大きい |
| 検索ノイズ | 少ない | 多い |
| 検索漏れ | 多い | 少ない |
| 検索速度 | 速い | 遅い |
| 言語依存 | 辞書が必要 | 辞書が不要 |
[編集] その他
他に日本語文書から索引文字列を抽出する手法として、文字種による切り分け、Suffix Array、シグネチャ法などがありそれぞれに特長があるが、先の2種に比べると大規模なシステムには適用しづらく、精度の問題もあり主流とはなっていない。
[編集] 文書フィルタ
検索対象文書がプレーンテキスト以外、たとえば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はソート済みでなければならない
[編集] 再現率と適合率
全文検索システムの評価指標のひとつとして「再現率 recall」と「適合率（精度） precision」が用いられる。前者は「いかに検索漏れが少ないか」をあらわし後者は「いかに検索ノイズが少ないか」をあらわす。一般的に両者はトレードオフの関係にあるといわれている。（→「情報検索#検索性能の評価」）
[編集] ランク付け（スコアリング）
検索された文書は「更新順」「ファイル名順」「文書のタイトル順」などにソートされる。一般的な検索エンジンでは独自のランク付けルールも適用し「重要度」などと呼んでいるものもある。ランク付けの基本的な考え方は「ユーザーにとって重要と思われる文書を上位に表示する」ことであり、以下のような手法が採られることが多い。
- 文書中の検索単語出現頻度
- HTMLタグの解析
- <title>タグや<H1>タグを重視する。
- TFとは単語の出現頻度、IDFは全文書中において単語が一部の文書に集中している度合いをあらわし、両者を掛け合わせることでランク付けを行う。
- 「重要度の高いページからリンクされているページは重要である」という原理に基づいてランク付けを行う。Googleで採用されている。
[編集] 主な用途
- WWW検索サービス
- 検索サービスの中では、超大型の機能が求められる分野で、一握りのプレーヤーによる熾烈な競争が行われている。ウェブの初期から行われていたサービスのひとつで、技術の進歩もめざましい。
- 企業向け社内検索サービス
- 社内ファイルサーバの文書資産を高速全文検索するシステム。WordやExcelといったオフィススイートから、メール、データベースなどの多くのファイル形式に対応し、企業の性格に応じて、多様な検索結果を返す。近年、電子データの企業資産の重要性が増し、非常に発達してきている分野。
- デスクトップ検索
- 個人のローカルファイルを検索するためのアプリケーションソフトウェア。Word,Excel,PDFなど様々なファイル形式に対応している。また、画像データなどの、個人の保有にあるマルチメディアデータの検索に特化したものもあり、スピードと手軽さが求められている。
[編集] 代表的な全文検索エンジン
[編集] サーバ／ワークステーション向け
[編集] 無償
- Hyper Estraier
- N-gramベース(N.M-gram)。わかち書き方式も併用可。
- 分散インデクス、Webクローラ、検索用CGIなど標準添付のプログラムが充実。
- N.M-gram方式とは、N文字に続くM文字のハッシュ値を計算し保持することによって、フレーズ検索が可能。フォルスドロップあり。類似検索あり。
- 大規模なインデックスも作成可。
- msearch
- インデックスは「ファイル名|タブコード|本文|改行コード」の単純なもので、これにGrep検索をかけることで対象文書を抽出する。
- 設置が非常に容易であり、root権限が無くてもインデックスの更新が可能なため、個人の小規模サイトを中心に用いられている。
- UTF-8などUnicodeにも対応したUnicode版msearchがある。
- Namazu
- わかち書きベース。
- 2単語によるフレーズからハッシュ値を計算し保持することによって、フレーズ検索が可能。フォルスドロップ（false drop=誤った候補）あり。
- 古くからあり、日本で広く使われている全文検索システム。
- 小中規模を対象とし、大規模が苦手。
- Lucene
- Analyzerと呼ばれるクラスを選ぶことにより、N-gramやわかち書き形式でのインデックス作成ができる。
- Javaによる全文検索システム。
- Wikipediaの検索に使われている。
- 大規模なインデックスも作成可。
- Rast
- わかち書きベース・N-gramベースの選択
- 単語の出現位置情報を保持し、正確なフレーズ検索が可能。フォルスドロップなし。
[編集] 有償
- jetrun®クラスター・サーチエンジン
- 300カテゴリ700万ワードの豊富な独自辞書による高速な全文検索エンジン
- ASP方式とアプライアンス方式のWebサービス
- ConceptBase V
- ConceptBase Enterprise Search
- 国産の検索エンジン ConceptBase シリーズの大規模対応版
- 1つのインデックスで概念検索と全文検索の両方を実現可能。
- ConceptBase V
- 概念検索や文字列一致検索に加え、絞り込み検索など高速で多彩な検索が特徴。
- ビューポイント、ファセット・ナビゲーションなど独特の機能を有する。
- Accela BizSearch
- FAST
- FileBlog
- HyperEstraierベースで、ActiveDirectory連携などWindowsファイルサーバ検索に特化したGUI
- フォルダ階層のブラウズや、フォルダによる検索範囲限定が特徴
- Oracle Secure Enterprise Search
- N-gramベース(V-gram)。
- ログインしたユーザーが参照可能な結果のみを表示するセキュア検索が特徴。
- Piranha
- サイト内検索CGI
- QuickSolution
- 類似検索、曖昧検索、クラスタリング機能など
- SAVVY
- 国産のパターン認識技術をベースとし、完全一致検索のほか、あいまい検索、あるまで検索、自然語調検索など、高速かつ多彩な検索方式が特徴。
- Sedue 24
- 関連記事自動抽出エンジン『Hotate』などが関連商品にあり。
- SMART/InSight
- 形態素解析、N-gram選択可。
- ActiveDirectoryなどのACL継承機能有り。
- 非常に高速なFastDataSearchをエンジンとして使用。
- Vivisimo Velocity
- クラスタリング技術による、類似した検索結果の自動カテゴライズ機能。
- ActiveDirectoryと連携したACL検索等、企業内の既存セキュリティに適合させるカスタマイズ性の高さが特徴。
- WiSE
- FlexSearch
[編集] 個人向け
[編集] 無償
- Windows デスクトップサーチ（マイクロソフト）
- わかち書きベース
- Windows Vista標準搭載。
- 検索対象フォルダを詳細に設定可能。ネットワークドライブにも対応。
- 正式には「MSN サーチ ツールバー with Windows デスクトップ サーチ」というパッケージで配布されている。
- Spotlight（アップルコンピュータ）
- Google デスクトップ(Google)
- わかち書きベース。
- Google web検索と同じエンジンでローカルファイルを検索できる。
- 欠点は、大きなファイルの場合、後半部分がインデックス化されないなどの問題。[1]
- DesktopHE
- N-gramベース(N.M-gram)。わかち書き方式も併用可。
- Hyper EstraierにGUIをつけた物。
- Google デスクトップなどの常駐型とは異なり、インデックスを張ったあとはコンピュータが重くなったりしない。
- インデックスサービス（マイクロソフト）
- Windows2000/XPに標準搭載。
- デフォルトではオフとなっている。
- ローカルディスク全体をインデックス化できるが、CPU負荷は高くなる。
- メール検索には非対応。
- Vistaでは、Windows デスクトップサーチをベースにしたシステムになった。
- FindFast（マイクロソフト）
- MS Office95~2000に標準搭載。
- Officeファイルが対象であり、メール検索などはできない。
- Office XP以降は、インデックス検索に置き換わった。
- Beagle
[編集] 有償
- サーチクロス（ビレッジセンター）
- 形態素解析によるわかち書きは採用せず。
- 詳細なアルゴリズムは不明だが、文字種により単語を分割し、インデックスに登録していくタイプと思われる。
- ひらがなは事前に辞書登録されたもの以外は検索できない。
- アルゴリズムが単純な分、インデクシングが極めて高速。
- コンセプトサーチ（ジャストシステム）