infosearch

02: 検索対象文書の収集：クローラとフィード

ウェブクローラとは

ウェブページを見つけてダウンロードし，検索対象の文書集合を集める道具

1. DNSに問い合わせることにより，ホスト名をIPアドレスに変換
2. 特定のポートによりサーバに接続
3. GET リクエストによりページを収集

• いくつかのウェブページを開始ページ（シード（種子）と呼ぶ）とし，URLリクエスト待ち行列に追加
• 待ち行列中のURLにあるページをダウンロードし，解析してリンクタグを抽出し，そこに含まれるURLをリクエスト待ち行列に追加
  • ex.) ブログの1ページ目から, ページングリンクを再帰的に取得していく
• 作法としてサイトへのアクセス負担を軽減するため，同じウェブサーバからのページのダウンロードは，一定の時間間隔を空ける
  • LibraHack事件(岡崎市立中央図書館)
• クロール拒否のサイトポリシーを尊重する
  • Robots.txtや<meta name="robots" content="noindex">

フリーの検索サーバの構築

• 全文検索サーバー Fess(Java製, OSS)
• https://fess.codelibs.org/ja/

鮮度

• HEADリクエストでのDateを読んで判定(fresh or stale)
• 以前取得したページから一定の期間立っていれば再取得するべき
• 評価尺度: 経時(Age)
  • 最後にクロールしてからn日後までの間に再度更新されてから経過する日数の期待値
    • Age(λ,n) = ∫₀ⁿP(page changed at x)(n-x)dx
  • ウェブページの更新はポアソン分布に従う
    • Age(λ,n) = ∫₀ⁿλe^λx (n-x)dx
  • ページが古くなるほど，クロールしないことのコストが大きくなる尺度
• 経時は徐々に腐っていく, 鮮度は一定期間保たれるが後完全に失われるイメージ

深層ウェブ

• クロール範囲外ページ
  • 会員制orログインが必要なページ
  • JavaScriptを使用して生成されるページ
    • 要Headlessブラウザ

サイトマップ

• URLのリストと，更新時間や更新頻度などの情報を持つ
• ウェブサーバ管理者が記述クローラに収集できるページを指示
• いつページが更新されるかの手がかりをクローラに提供
  • https://github.com/eggplants/opac/blob/master/sitemap.xml

分散クロール

• 複数のコンピュータを利用してのクロール
• ページを取得・記憶する計算資源を軽減できるという利点
• サイトURLでハッシュを計算してワーカを割り当てるといい感じ

文書の格納

目的

• ページが更新されていない時の，クロール時間を節約
• スニペットを生成する際の，テキストへの効率的アクセスが可能

要件

• ランダムアクセス
  • URL集合からそのハッシュ値などに基づきアクセス
  • 自然なアクセスを装う
• 圧縮
  • 取得したデータを効率的に保存・アクセスするため
• 更新

TREC Web

• http://www.cs.cmu.edu/~lemur/LemurGuide.html#data

<DOC>
    <DOCNO> 1 </DOCNO>
    <TEXT>Index this document text.</TEXT>
</DOC>
...
<DOC>
    <DOCNO> 100 </DOCNO>
    <TEXT>Index this document text.</TEXT>
</DOC>

• クロールした文書はバラバラに保管するよりいっそのこと1つに結合し格納したほうが便利？

BigTable

• Googleの文書格納システム
• ウェブページの格納，検出，更新
• 数百～数千台の安価なコンピュータを使い，大規模な文書集合（ペタバイト）を取り扱う
  • 巨大な分散クロール環境
• 列指向のDBMS
  • urlをキーとする
  • [<url>]-->[text]|[anchor:other.com][anchor:null.com][title][...]
  • 単純な構造で列に対しての走査を行う+多くの文書を格納できる
• 耐障害性
  • 列のURLキーに応じて, データはTablet単位に冗長化されている
  • Tabletサーバが死ぬと別のサーバがデータログから復旧

完全重複ページの検出

• Webページの3割は別サイトの模倣
  • コピー，バージョン，盗作，スパム，ミラーサイト
  • クロールするだけ無駄
• 完全に同一か確認するのは文書のチェックサムを取れば良い
  • チェックサムが衝突する可能性は存在

類似重複ページの検出

• むずかしい
• 文書間類似度を計算, 閾値で判断(Doc2Vecなど)
• 類似重複ページの全てのペアを発見するのはO(N^2)なので効率性が重要
  • FingerprintとSimhash

Fingerprint

• 文書のN-gramをいくつか抽出しハッシュを計算
• 文書間での重複を比較

Simhash

• 高次元のデータ(文書の分散表現のベクトルなど)をビットベクトルという低次元で表現したい

• 文書中の単語を固定長(len(bin(n))-2)2進数のハッシュ値に変換
  • 単語ごとにユニーク
• 各単語のハッシュ値についてビットごとに:
  • 重みV[ind]を, 0なら減算, 1なら加算
• 各単語の重みについて:
  • V[ind]負なら0, 正なら1とする
• len(bin(n))-2次元ベクトルのビットベクトルVを類似度計算に用いる

ノイズ

• リンク，画像，内容に関連しないテキスト
• ページランクを計算する際は邪魔なのでHTMLタグ、属性から判断し削除する

文書フィード

• 内容更新されにくい文書に関しての更新系列
  • 新聞記事，ブログポスト，プレスリリース，電子メール等は，一度公開されるとめったに更新されない
• pushとpull
  • pushフィードは利用者へのお知らせ
  • pullフィードは利用者が要求
    • RSS
      • 衰退？