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

第2回 検索エンジンを形作るもの

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

はじめに

前回は,検索エンジンとはどういうもなのか?について簡単に触れました。今回は,システムとしての検索エンジンの概要を見ていきます。

検索エンジンの構成

検索エンジンは他のシステムと同様に,複数のコンポーネントから構成されています。ざっくり分けると以下のようなコンポーネントから構成されています図1)⁠

  • 索引構築部(Indexer, インデクサー)
  • 検索部(Searcher, サーチャー)
  • 索引(Index, インデックス)

図1 検索エンジンの構成

図1 検索エンジンの構成

たった3つ?と思うかもしれませんが,これは大きな枠組みで分けているからです。もちろん,各コンポーネントは複数のサブコンポーネントから構成されていますので,実際はもう少し複雑になりますが,基本はこの構成となります。

次は,それぞれのコンポーネントで具体的に何を行っているかを見てみましょう。

各コンポーネントの概要

●索引構築部(Indexer)

索引構築部では,検索したいテキスト文書を検索しやすいフォーマット(索引)に変換する作業を担当します。

転置索引や接尾辞配列などの索引構造ごとにさまざまな索引手法が提案されてきています。規模の大きい検索エンジンにおいては,結果的に同じ索引を作る場合でも,その作り方の違いにより効率が大きく変わるので,いかに効率的に索引を構築できるかというのが,この索引構築部の役割となります。詳しい手法についてには,後の回でいくつか紹介する予定です。

●索引部(Index)

索引部は,索引構築部で構築された索引そのものになります。しかし,索引といってもその構造だけでなく,形式にもさまざまなものがあります。基本的には,OS(ファイルシステム)上のファイルとして保存される場合が多いと思います。独自のバイナリ形式のファイル上に論理的に索引構造を構築する場合や,DBMSに管理させる場合などがあります(DBMSも通常はファイル上にデータを保存します)⁠

現在のコンピュータでは,ファイルはディスク上に保存される場合が多いので,多くの場合索引は圧縮されます。それは,圧縮によりディスクから読み込む転送量を削減し,処理の効率化を図るためです。とくに大規模な検索エンジンでは索引の圧縮が有効に働くので,索引の物理的な構造がこの索引部の肝になります。

●検索部(Searcher)

検索部では,索引部に対して検索処理が行われます。検索エンジンにおいて,最も速度が要求されるところになります。しかし,索引は検索しやすい形に変換されているので,検索処理自体はシンプルな場合が多くなります。

索引が圧縮されている場合は(部分的に)復元し,索引構造に応じた検索処理が行われます。よって,圧縮された索引の復元速度も高速な検索を実現するには必須となります。⁠つまり,索引部は,圧縮率の向上と復元速度の向上という相反する要求に応える必要があります。)

また検索部は,構築された索引に対して何度も呼ばれる部分なので,キャッシュを利用することにより処理の高速化を図ることがあります。検索結果自体をキャッシュする場合や索引の一部をキャッシュするなど,さまざまなレベルでキャッシュが利用されます。

その他の関連コンポーネント

以下のコンポーネントは厳密には検索エンジンの一部ではありませんが,検索エンジンに関連した非常に重要な関連コンポーネントとなります。

●クローラ (Crawler)

クローラとは,Web上の文書(HTMLファイルなど)を収集・管理するロボット(システム)のことです。

Web検索や横断ブログ検索の場合など,検索したい文書が手元に無い場合は,それらを取りに行く必要があります。Webページの場合は,HTML上のハイパーリンクを辿って世界中の文書を集めることが可能となります。世界中のWebページはものすごい勢いで増え続けているので,それらを効率的に収集することがクローラの役割となります。通常,クローラにより集められたデータは,RDBMSなどによって管理することが多いと思います。

●文書データベース(Document Database)

あらかじめ検索したい文書が手元にある場合もあります。企業内の文書や,自ドメインでのサービスのデータなどがすである場合がそれに該当します。これらをまとめて管理するデータベースを,ここでは「文書データベース」と呼びます。

データベースと言っていますが,実際にはファイルの集まりであったりする場合も多いので,文書の集合と理解してください。


これらクローラにより集められたデータや文書データベースが,検索エンジン(索引構築部)への入力となります。

これらの関連コンポーネントに関してひとつ重要なことは,全文検索エンジンはフラットなテキスト文書を扱う点です。このため,必要に応じて構造をもつ文書からフラットなテキスト文書への変換が行われます。これは,クローラから収集してきたHTMLなどを考えるとわかりやすいと思います。HTMLは内部に構造を持っているので,これを構造のないフラットな形へと変換を行う必要があるのです。クローラが収集してきたデータや文書データベースに保存されているデータはこうした変換が行われているか,取り出すときに変換が行われます。

まとめ

今回は,検索エンジンをコンポーネントに分割し,各コンポーネントの役割を理解することで,検索エンジン全体の概要をつかんでもらうのが目的です。ただ,検索エンジンならこの構成をとらなければいけないというものではありません。あくまでも多くの検索エンジンに見られる構成の傾向としてとらえてください。抽象的な話が多かったので,もしかしたら退屈だったかもしれません。ただ,全体の概要を把握しておくことは重要なので,初めに触れておきました。

次回は,検索エンジンの肝となる「転置索引」について説明していきます。

著者プロフィール

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

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

コメント

コメントの記入