検索エンジンはいかにして動くのか?

第1回 検索エンジンとは

この記事を読むのに必要な時間:およそ 1.5 分

全文検索とは

そのような全文検索エンジン(以降,検索エンジン)の根幹となる全文検索とは,どのような仕組みで実現されているのでしょうか? 全文検索には大きく分けて2つの手法が存在します。

  • grep型
  • 索引型(インデックス型)

それぞれについて簡単に説明します。

grep型

grep型検索は,逐次検索とも呼ばれます。UNIXの文字列検索コマンドである「grep」が名前の由来となっています。

grepコマンドと同様,検索したい文字列を文書の先頭から探していきます。よって,あらかじめ検索したい文書に対して前処理を行う必要などはありませんが,文書が増えると,それに従い検索時間も増加してしまうという問題点もあります。つまりgrep型検索は,小さい文書,一時的な文書などに向いた検索手法であると言えます。また,次に説明する索引型手法と一緒に使われる場合もあり,現在でも広く使われている手法となります。

補足ですが,文書に対して文字列を操作するにも,KMP法やBM法といった効率的な手法がいくつか存在し,一般的にはこれらの手法が使われます。これらについては本連載ではこれ以上扱いませんが,興味がある方はアルゴリズムの教科書などを参照ください。

索引型(インデックス型)

grep型とは対照的に,あらかじめ検索しやすいように文書から索引(インデックス)を作ることにより,検索速度を向上させる手法となります。索引の構築に時間が掛かりますが,文書が増えても検索速度の低下を防ぐことが可能となり,中規模から大規模の文書に向いた検索手法と言えます。

一般的に検索エンジンといえば索引型の手法を採用したもののこと指し,転置索引(転置インデックス)や接尾辞配列(サフィックスアレイ)などの索引が広く使われています。本連載では,GoogleやYahoo!などでも使われている転置索引を対象に解説していきます。

今後の予定

本連載では,検索エンジンという(データベース)システムに焦点を絞り,解説を行っていきます。よって一般的なWeb検索に見られるような,検索結果をどういう基準で並び替えるかといったこと(適合率と再現率の話)などにはほとんど触れない予定です。スペースの都合上,プログラムコードはあまり載せることができませんが,物理的なしくみや実装方法などがある程度想像できるように努力していきたいと思います。

予定する内容の大枠は以下の通りです(あくまでも予定ですので,変更する場合もあります)⁠

  • 導入(今回)
  • 検索エンジンのアーキテクチャ
  • 索引構造
  • 索引構築について
  • 検索方法について
  • 高度な話題

    動的な索引構築手法
    全文検索における圧縮
    分散インデックス
    近年の話題

著者プロフィール

山田浩之(やまだひろゆき)

日本IBM株式会社を経て,ヤフー株式会社等で検索エンジンの開発に従事。現在は大学院でデータベース・情報検索の研究を行う。また,オープンソースで全文検索エンジンLuxやデータベースマネージャLux IOの開発を行っている。