IIR20章まとめ

勉強 IIR

20章は、クローラについて。

Web検索システムはドキュメントセットをクロールし、ページを取得している。

シンプルなクローラ

基本的なクローラは、以下のように動作する。Webはよくリンクされていると仮定する。

  1. まず、起点となるURLをエンキューする。
  1. 以下を繰り返す。
    • URLをデキューする。
    • ページをフェッチし、パースする。
    • ページ中のURLを抽出する。
    • そのURLをエンキューする。

しかし、Webには膨大な数のドキュメントがあり、全てをインデキシングするのは不可能。また、クロールには非常に時間がかかる。

そこで、これらの中に大量に含まれている重複したものやスパムを検出し、まとめてあけることで、数を減らしたい。

クローラは以下の性質の持っている必要がある。

  • 洗練されている
    • サーバににヒットしすぎてはならない
    • 許可したページのみをクロールする
  • 頑健である
    • スパイダートラップ、重複、大きいページ、動的なページなどに強い

実際のクローラ

基本的なクローラの構造は、以下のようになっている。

URL frontier

URLは取得しているが、まだクロールしていない段階。

以下に注意する。

  • 同時に全てのURLをフェッチするのは避ける
  • スレッドに空きがないようにする
URLの正規化

相対URLは、絶対URLに正規化しなければならない。

例えば、http://mit.edu上でaboutsite.htmlが見つかれば、http://mit.edu/aboutsite.htmlに正規化してあげる。

Content seen

ページをフェッチした時、その内容がすでにインデックス内にないかをチェックし、もしあればそのドキュメントはスキップする。

マルチスレッド化

ノードを分割し、各々をクロールする。