Wikipedia

全文検索

（FTSから転送）
ウィキペディア ウィキペディアにおける全文検索については、「Help:全文検索」をご覧ください。

全文検索（ぜんぶんけんさく、英: Full text search）とは、コンピュータにおいて、複数の文書（ファイル）から特定の文字列を検索すること。「ファイル名検索」や「単一ファイル内の文字列検索」と異なり、「複数文書にまたがって、文書に含まれる全文を対象とした検索」という意味で使用される。

全文検索技術

編集

grep型

編集

順次走査検索、逐次検索ともいう。「grep」とはUNIXにおける文字列検索コマンドであり、複数のテキストファイルの内容を順次走査していくことで、検索対象となる文字列を探し出す。一般に「grep型」と呼ばれる検索手法は、事前に索引ファイル（インデックス）を作成せず、ファイルを順次走査していくために、検索対象の増加に伴って検索速度が低下するのが特徴である。ちなみに「grep型」とは実際にgrepコマンドを使っているという意味ではない。

索引（インデックス）型

編集
 
インデックス作成型全文検索システム

検索対象となる文書数が膨大な場合、grep型では検索を行うたびに1つ1つの文書にアクセスし、該当データを逐次検索するので、検索対象文書の増加に比例して、検索にかかる時間も長くなっていってしまう。そこであらかじめ検索対象となる文書群を走査しておき、高速な検索が可能になるような索引データを準備することで、検索時のパフォーマンスを向上させる手法が取られている。事前に索引ファイルを作成することをインデクシング（英: indexing）と呼ぶ。インデクシングにより生成されるデータはインデックス（インデクス）と呼ばれ、その構造は多くの場合、「文字列 | ファイルの場所 | ファイルの更新日 | 出現頻度…」といったようなリスト形式（テーブル構造）を取り、文字列が検索キーとなっている。検索時にはこのインデックスにアクセスすることで、劇的に高速な検索が可能となる。

索引文字列の抽出手法

編集
形態素解析
編集

英文の場合は単語と単語の間にスペースが入るため、自然、スペースで区切られた文字列を抽出していけば、索引データの作成は容易となる。しかし日本語の場合は、単語をスペースで区切る「わかち書き」の習慣がないため、形態素解析技術を用いて、文脈の解析、単語分解を行い、それをもとにインデックスを作成する必要がある。形態素解析を行うためには解析用の辞書が必須であり、検索結果は辞書の品質に少なからず影響を受ける。また、辞書に登録されていないひらがな単語の抽出に難があるなど、技術的障壁も多く、検索漏れが生じることが欠点とされる。

N-Gram
編集

「N文字インデックス法」「Nグラム法」などともいう。検索対象を単語単位ではなく文字単位で分解し、後続の N-1 文字を含めた状態で出現頻度を求める方法。Nの値が1なら「ユニグラム（英: uni-gram）」、2なら「バイグラム（英: bi-gram）」、3なら「トライグラム（英: tri-gram）」と呼ばれる。たとえば「全文検索技術」という文字列の場合、「全文」「文検」「検索」「索技」「技術」「術（終端）」と2文字ずつ分割して索引化を行ってやれば、検索漏れが生じず、辞書の必要も無い。形態素解析によるわかち書きに比べると、2つの欠点がある。意図したものとは異なる検索結果（いわゆる検索ノイズ）の発生と、インデックスサイズの肥大化である。検索ノイズの一例として、「京都」で検索すると「東京都庁」という適合しない検索結果、「＊＊＊が含まれる物は見つかりませんでした」という文章が返ってくる場合が挙げられる。

形態素解析とN-gramの比較
  形態素解析 N-gram
インデクシング速度 遅い 速い
インデックスサイズ 小さい 大きい
検索ノイズ 少ない 多い
検索漏れ 多い 少ない
検索速度 速い 遅い
言語依存 辞書が必要 辞書が不要
その他
編集

他に日本語文書から索引文字列を抽出する手法として、文字種による切り分け、接尾辞配列、シグネチャ法などがありそれぞれに特長があるが、先の2種に比べると大規模なシステムには適用しづらく、精度の問題もあり主流とはなっていない。

文書フィルタ

編集

検索対象文書がプレーンテキスト以外、たとえばHTML文書ならばタグの除去等の処理を行ってテキストを抽出できるが、特定メーカーのワープロ独自形式などバイナリ形式の場合、インデクサは直接ファイルからテキストを抽出することが出来ないため、文書フィルタを利用して該当ファイルからテキストを抜き出す必要が生じる。文書フィルタ機能はインデクサが内包しているものもあれば、アドインなどの機能拡張によって実装する場合もある。

転置ファイル

編集

全文検索用のインデックスには様々な形式があるが、最も一般的なものは単語と、単語を含む文書ファイルの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検索サービス
検索サービスの中では、超大型の機能が求められる分野で、熾烈な競争が行われてきたが、2013年現在では「Google」または「Bing」のいずれかに集約されつつある。ウェブの初期から行われていたサービスのひとつで、技術の進歩もめざましい。
企業向け社内検索サービス
社内ファイルサーバの文書資産を高速全文検索するシステム。WordやExcelといったオフィススイートから、メール、データベースなどの多くのファイル形式に対応し、企業の性格に応じて、多様な検索結果を返す。近年、電子データの企業資産の重要性が増し、非常に発達してきている分野。
デスクトップ検索
個人のローカルファイルを検索するためのアプリケーションソフトウェア。Word、Excel、PDFなど様々なファイル形式に対応している。また、画像データなどの、個人の保有にあるマルチメディアデータの検索に特化したものもあり、スピードと手軽さが求められている。

代表的な全文検索エンジン

編集

サーバ/ワークステーション向け

編集

無償

編集
  • Tokyo Dystopia: a full-text search system
    • 以下の製品群と組み合わせて使用する。Tokyo Cabinet: a modern implementation of DBM、Tokyo Tyrant: network interface of Tokyo Cabinet、Tokyo Promenade: a content management system、Kyoto Cabinet: a straightforward implementation of DBM、Kyoto Tycoon: a handy cache/storage server
  • 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=誤った候補）あり。
    • 古くからあり、日本で広く使われている全文検索システム。
    • 小中規模を対象とし、大規模が苦手。
  • Apache Lucene/Solr
    • Analyzerと呼ばれるクラスを選ぶことにより、N-gramやわかち書き形式でのインデックス作成ができる。
    • Javaによる全文検索システム。
    • Luceneがクラスライブラリとして提供され、Luceneを利用した全文検索サーバーがSolrとなる。
    • IBM WebSphere Commerce, Salesforce, Microsoft Azure, SAP Hybris, 楽天などで利用されている。
    • 大規模なインデックスも作成可。スケーリングし稼働率、対障害性を高めるZookeeperを使った仕組みを備える。
  • Rast
    • わかち書きベース・N-gramベースの選択
    • 単語の出現位置情報を保持し、正確なフレーズ検索が可能。フォルスドロップなし。
  • Senna
    • わかち書きベース・N-gramベースの選択
    • 他のプログラムからライブラリとして呼び出して利用する。
    • MySQLの中に全文検索エンジンを組み込むパッチが提供されており、MySQLを利用しているプログラムであれば全文検索機能を手軽に実現できる。
    • PostgreSQLに対して、Sennaを全文検索エンジンとして組み込むためのモジュールLudiaが公開されている。
    • Perlバインディングにより、Perlスクリプトから簡単に利用することができる。PHP、Ruby、Pythonバインディングも提供されている。
    • 大規模なインデックスも作成可。ただし、分散検索の機能はない。
  • Groonga
    • Sennaの後継エンジン

有償

編集
  • jetrun®クラスター・サーチエンジン
    • 300カテゴリ700万ワードの豊富な独自辞書による高速な全文検索エンジン
    • ASP方式とアプライアンス方式のWebサービス
  • ConceptBase Enterprise Search
    • 国産のエンタープライズ検索エンジン ConceptBase シリーズの大規模対応版
    • 検索精度の高い独自技術「NL-Vgram」で、1つのインデックスで概念検索と全文検索の両方を実現可能。
  • ConceptBase Search Lite（旧 ConceptBase Search 1000）
    • 概念検索や文字列一致検索に加え、絞り込み検索など高速で多彩な検索が特徴。
    • 上位版「ConceptBase V」はビューポイント、ファセット・ナビゲーションなど独特の機能を有する。
  • Sedue
    • 圧縮サフィックスアレイを使用したインメモリ型の全文検索エンジン
    • 複数マシンでの分散検索も可能
  • FAST ESP
    • 検索パフォーマンスと検索対象データ量の両面でスケーラビリティを持ち、超大規模システムまで対応可能。
    • 形態素解析とN-gramの両方をハイブリッドに利用可能。
  • FileBlog
    • Solrベースで、ActiveDirectory連携などWindowsファイルサーバ検索に特化したGUI
    • フォルダ階層のブラウズや、フォルダによる検索範囲限定が特徴
  • Oracle Secure Enterprise Search
    • N-gramベース (V-gram)。
    • ログインしたユーザーが参照可能な結果のみを表示するセキュア検索が特徴。
  • Piranha
    • サイト内検索CGI
  • SAVVY
    • 国産のパターン認識技術をベースとし、完全一致検索のほか、あいまい検索、あるまで検索、自然語調検索など、超高速かつ多彩な検索方式が特徴。
  • SMART/InSight
    • 形態素解析、N-gram選択可。
    • ActiveDirectoryなどのACL継承機能有り。
    • Apache Solrをエンジンとして使用。
  • Neuron
    • Apache Solrベースでプラグインを組み込み、検索画面・クローラーをパッケージングした全文検索システム。
    • 形態素解析とN-Gramで日本語を分割し、辞書登録の負荷を大幅に軽減。独自開発のクローラーによるパフォーマンスの高さが特徴。
  • Vivisimo Velocity
    • クラスタリング技術による、類似した検索結果の自動カテゴライズ機能。
    • ActiveDirectoryと連携したACL検索等、企業内の既存セキュリティに適合させるカスタマイズ性の高さが特徴。
  • WiSE
  • FlexSearch
  • InfoBee/iS
    • NTTの技術を基にした純国産検索エンジン
    • 形態素解析、同義語辞書を使用したあいまい検索が可能
  • IBM OmniFind Enterprise Edition
    • 形態素解析とN-gramの両方をサポート
    • さまざまなデータソースを検索対象とすることができる
  • FAST Search Server for SharePoint
    • ファスト製品の技術を基にした検索エンジン
  • Autonomy IDOL (Intelligent Data Operating Layer)
    • オートノミーはMeaning-Based Computing (MBC) を提唱しており、その中核となるコア技術
  • QuickSolution
    • 住友電工情報システムによって提供されている全文検索エンジン。
  • Microsoft SharePoint Server

[1]個人向け

編集

無償

編集
  • Windows Search（マイクロソフト）
    • わかち書きベース
    • Windows Vista以降に標準搭載。
    • 検索対象フォルダを詳細に設定可能。ネットワークドライブにも対応。
    • 当初は「MSN サーチ ツールバー with Windows デスクトップ サーチ」というパッケージで配布されていた。
  • Spotlight（Apple）
  • GrepWin
    • GrepのWindows移植。
    • GUI付き。
  • Googleデスクトップ (Google)
    • わかち書きベース。
    • Google web検索と同じエンジンでローカルファイルを検索できる。
    • 欠点は、大きなファイルの場合、後半部分がインデックス化されないなどの問題。[1]
    • 2008年を最後に開発停止済。
  • DesktopHE
    • N-gramベース (N.M-gram)。わかち書き方式も併用可。
    • Hyper EstraierにGUIをつけた物。
    • Google デスクトップなどの常駐型とは異なり、インデックスを張ったあとはコンピュータが重くなったりしない。
    • 2010年を最後に開発停止済。
  • インデックスサービス（マイクロソフト）
    • Windows 2000 / XPに標準搭載。
    • デフォルトではオフとなっている。
    • ローカルディスク全体をインデックス化できるが、CPU負荷は高くなる。
    • メール検索には非対応。
    • Vistaでは、Windows デスクトップサーチをベースにしたシステムになった。
  • FindFast（マイクロソフト）
    • MS Office95~2000に標準搭載。
    • Officeファイルが対象であり、メール検索などはできない。
    • Office XP以降は、インデックス検索に置き換わった。
  • Beagle
  • MetaTracker
    • LinuxなどのUnix系OS向け
  • butterfly_search（バタフライサーチ）
    • アルファベットは空白区切り、それ以外の文字はN-gramベースでインデックス化。
    • 検索対象はテキストファイルのみ。

有償

編集

アルゴリズム

編集

リニアサーチ(通称「馬鹿サーチ」)やバイナリーサーチ(二分法)、ハッシュ法などがあるが、それぞれ得失があり、「辞書の登録語彙数が多くなると手間数が増えて遅くなる」という問題がある。

一般的な検索エンジンではダブル配列法が用いられているようだが、ダブル配列法は主記憶領域が狭い過去の環境に合わせて開発されたらしいので、現在では可読性が悪いため採用するのはお奨めできない ダブル配列法の解析から、その祖形であるトリプル配列法が発見（おそらくは再発見）されたが、発明者は知られていない。 トリプル配列は、辞書登録語彙に関わらず、最長の登録語彙の長さ l に比例した手間数しかかからないのでお手軽なあるアルゴリズムだが、最長語彙 l が増えるとヒットする語数が減るので、途中でリニアサーチに切替えるとコンパクトになる。また、プログラミング言語の予約語のように数が限られていて頻出する語については、ハッシュ法を使ったほうが簡単である。

脚注

編集
[脚注の使い方]
  1. ^ a b http://desktop.google.co.jp/support/bin/answer.py?answer=12764[リンク切れ]

関連項目

編集

外部リンク

編集
「https://ja.wiki.x.io/w/index.php?title=全文検索&oldid=100485548」から取得