3. ページ収集部の実装

ページ収集部の実装について簡単に説明します。

3.1. 動作原理

大抵のページにはリンクがありますが、そのリンクをクリックすると他のページに移ることができます。移動した先のページにもリンクが含まれていて、そこからまた同じようにして他のページに移ることができます。このようにリンクをどんどんたどっていくと、たくさんのページを移動することができます。

この原理を利用して、いくつかのページをスタート地点として自動的にどんどんリンクをたどっては、そのページの内容を手元に保存していくという処理を行ないます。

3.2. 動作アルゴリズム

(1) 初期状態

• S₁ 〜 S_n : 収集のスタート地点となるスタートページのURL
• C : ページを収集する上限値
• U : 取得すべきURLを含む集合。初期値は空集合。

(2) 処理手順

1. i = 1〜n まで次のことを実行する。
   1. S_i の指すページ内容をまだ取得していない場合は、集合 U に入れる。ただし、この S_i のスコア値は0点とする。
2. 集合 U が空になるか、または収集したページの数が上限値 C を超えるまで次のことを実行する。
   1. 集合 U から最もスコア値の小さいURL T を取りだす
   2. T の指すページの更新時刻を取得する。
   3. T の指すページ内容をまだ取得していないか、取得後に更新されているようであれば、取得して保存する。
   4. T のの指すページ内容を解析してリンクを抽出する。
   5. 抽出したリンクをスコア付けして集合 U に入れる。ただし、このスコア値は0点より大きい値をとるものとする。

3.3. リンクをたどる順番の決定

ページの収集量が多ければ多いだけ検索可能なページが多くなります。よって、イントラネット内の全てのページを収集してしまうというのが最も良いのですが、規模がある程度大きい場合は、収集したページの保存領域や収集に要する時間などの制約から、一度に全てのページを収集することは出来ません。

そこで、限られた数のページをいかに効率よく収集するかという戦略をたてることが必要になります。

先に説明したように、ページの収集はリンクをたどることで行ないますので、どのようにリンクをたどるかが重要になります。

たとえば収集の最初のページを上から見ていって、最初にみつけたリンクで、他のページに移り、また移った先のページを頭からみていって、最初にみつけたリンクをたどるということを繰り返して収集していくことにすると、どんどん階層の深いページをたどることになりがちです。

もし収集対象のページが木構造をとっていたとすると、深さ優先探索でページを収集することになります。

厳密には、他のサーバへのリンクがあったり、同じ階層の他のページにリンクされていて、木構造ではなくグラフ構造なのですが、大抵のページは木構造に近い構成をとっています。

さきの方法だと、全体と比較してかなりかたよりのある情報収集になることが予想できます。全文検索サーバとしては良い情報の持ちかたではないですね。

全文検索サーバが持つ情報としては、狭く深くよりは浅く広く持っていた方が良いでしょう。では、どうすれば限られたページ数でこのような情報を収集することができるでしょうか？

たとえば、大抵のページ構成だと一番最初のページに、ここにはどういった情報を提供していますといった事が書かれていますね。このようなトップページを優先して取得すれば、浅く広い情報を取得できそうです。
具体的には、次のような形のURLを優先して内容を取得していけば良さそうだということになります。

http://foo.bar.com/
http://foo.bar.com/~user/

また、他には階層の浅いページの方が、目次のように、それ以下の階層の情報についてのなんらかの情報が埋めこまれていることが多いです。
これについては、URLの中にスラッシュ'/'が少ないものを優先して内容を取得していけば良さそうだということになります。

上のような経験則をいくつか組みあわせて、URLにスコアづけをします。このスコアをもとにして、次に取得すべきURLを決定しています。