はじめに
検索エンジンと聞くと、みなさんは何を思い浮かべるでしょうか？
GoogleやYahoo!などの検索ページを思い浮かべる方がほとんどだと思います。近年は、それら企業の努力によって検索エンジンというものが非常に身近になり、私たちの生活に欠かせないものとなりつつあります。
しかし、検索エンジンと一言で言っても、上記のような一般の方々へのUI（ユーザインターフェース）を指す場合もあれば、そのUIの裏側（バックエンド）にあるシステムを指す場合もあります。
本連載では、Google,Yahoo!などを代表とする検索エンジンの裏側のしくみに着目し、検索エンジンというシステムのアーキテクチャやその内部で使われているデータ構造やアルゴリズムを、近年の手法や研究事例などを交えて解説していきたいと思っています。
検索エンジンとは
検索エンジンには、さまざまな種類があります。GoogleのWeb検索のようなものは、一般的に全文検索エンジンと呼ばれます。その他にも、画像検索エンジン、動画検索エンジンなど、多くの検索エンジンが存在します。本連載で紹介するのも、もちろん全文検索エンジンについてです。
では、この「全文」とはどういう意味でしょうか？
答えは単純で、全文とは「全」部の「文」という意味になります。つまり、検索を行いたい対象はテキスト文書の全部の文であるという場合は全文検索と呼びます。そして、そのような全文検索を実現するシステムが全文検索エンジン／全文検索システムと呼ばれます（英語では、full-text search engine/full-text search systemと呼ばれます）。全部の文を検索するといっても、普段Google、Yahoo!などを使って指定したキーワードを含むWeb上のあらゆるページを検索している私たちにとっては、あたりまえのことだと感じるのではないでしょうか。
また、補足になりますが、画像／動画検索エンジンでは、画像・動画の特徴量を使って検索を行うといった処理が行われているようです。しかし、画像検索・動画検索と呼ぶ場合でも、画像や動画の周辺のテキスト情報や画像のメタ情報を使って検索している場合はテキスト情報を検索していることになるので、正確には全文検索エンジンとなります。
以降本連載では、「検索エンジン」と書いた場合は全文検索エンジンを指します。
さまざまな全文検索エンジン
近年、検索エンジンはいろいろな場面で使われています。
もっとも身近なWeb検索をはじめ、メール検索やデスクトップ検索、そして特許検索やブログ検索などのドメイン特化型検索などが挙げられます（図1）。
図1 検索の用途と規模
これらはすべて検索エンジンとしての基本となる仕組みは同じですが、規模やユースケースの違いから異なるアーキテクチャやデータ構造をとることがあります。
たとえば、メール検索やデスクトップ検索では、保存・検索したい文書量はそれほど多くありませんが、新しいメールや文書が追加されたら、それらをすぐに検索できるようしたいと思います。一方、Web検索では、大量の文書を保存しなければなりませんが、Web上にHTMLページが1つ追加されても、それが検索できるまでには多少の時間がかかっても許容できると思います。
このように、一言に全文検索エンジンと言っても、さまざまな形態や種類があります。本連載では、中規模から大規模の検索エンジンに主に焦点を当てて、解説を行っていきたいと思います。
全文検索とは
そのような全文検索エンジン（以降、検索エンジン）の根幹となる全文検索とは、どのような仕組みで実現されているのでしょうか？ 全文検索には大きく分けて2つの手法が存在します。
それぞれについて簡単に説明します。
grep型
grep型検索は、逐次検索とも呼ばれます。UNIXの文字列検索コマンドである「grep」が名前の由来となっています。
grepコマンドと同様、検索したい文字列を文書の先頭から探していきます。よって、あらかじめ検索したい文書に対して前処理を行う必要などはありませんが、文書が増えると、それに従い検索時間も増加してしまうという問題点もあります。つまりgrep型検索は、小さい文書、一時的な文書などに向いた検索手法であると言えます。また、次に説明する索引型手法と一緒に使われる場合もあり、現在でも広く使われている手法となります。
索引型（インデックス型）
grep型とは対照的に、あらかじめ検索しやすいように文書から索引（インデックス）を作ることにより、検索速度を向上させる手法となります。索引の構築に時間が掛かりますが、文書が増えても検索速度の低下を防ぐことが可能となり、中規模から大規模の文書に向いた検索手法と言えます。
一般的に検索エンジンといえば索引型の手法を採用したもののこと指し、転置索引（転置インデックス）や接尾辞配列（サフィックスアレイ）などの索引が広く使われています。本連載では、GoogleやYahoo!などでも使われている転置索引を対象に解説していきます。
今後の予定
本連載では、検索エンジンという（データベース）システムに焦点を絞り、解説を行っていきます。よって一般的なWeb検索に見られるような、検索結果をどういう基準で並び替えるかといったこと（適合率と再現率の話）などにはほとんど触れない予定です。スペースの都合上、プログラムコードはあまり載せることができませんが、物理的なしくみや実装方法などがある程度想像できるように努力していきたいと思います。
予定する内容の大枠は以下の通りです（あくまでも予定ですので、変更する場合もあります）。
