簡易クローラの作成

4. 簡易クローラの作成#

クローラ (crawler)とは、複数のウェブページを巡回しながら情報を収集するプログラムを指す。本節では、日本語版のWikipediaを対象に、記事のリンク関係を調べるクローラを作成してみよう。

4.1. 本クローラの目的#

読者の皆さんは、人と人との関係を表すとき、知り合いを6人たどると、おおよそ世界中のどんな人にもたどり着ける、という話を聞いたことがあるだろうか。この話は「六次の隔たり」と呼ばれ、Wikipediaの記事としてもまとめられている。

六次の隔たり - Wikipedia

この話と同様のことを、ウィキペディアの英語ページに対して行えるウェブサイトに以下のようなものがある。いくつかの記事名を入力して試してみると、すぐに思いつくような記事名であれば、おおむね3回くらいリンクを辿ると一方の記事からもう一方の記事までたどり着けるだろう。

https://www.sixdegreesofwikipedia.com/

なお、このウェブサイトのソースコードはGitHub上に公開されており、クローリング済みのデータを使用して経路を計算しているため、動作が非常に速い。実際にHTTP通信を行ないながら経路を探す場合には、どのくらいの時間がかかるのか。ぜひ以下の課題を通して体験してみてほしい。

本項では、日本語版のWikipediaを対象に「2つの記事が何次の隔たりにあるか」を調べるプログラムを作成する。実装するクローラのプログラムは目安として100行前後になる。

4.2. ステップ0: スクリプトの作成#

今回は独立したスクリプトファイルとしてクローラを作成するので、まずはcrawler.pyのような名前でPythonスクリプトを作成しよう。

スクリプトファイルが作成できたら、まずは、以下のように記述して、コマンドラインから実行した際にプログラム中からmain関数が呼び出されるようにしておく。

def main():
    # 空のメイン関数
    pass

if __name__ == "__main__":
    main()

次に、コマンドライン引数から、スタートの記事名とゴールの記事名を指定できるようにしておく。これにはsysモジュールのargvを用いる。

# 追加
import sys

def main():
    # 追加
    argc = len(sys.argv)

sys.argvは最低で長さが1となっており、sys.argv[0]には実行したスクリプトファイル名が入る。以降、sys.argv[1]、sys.argv[2]、...には、コマンドライン引数が順に格納される。

例えば、シェル環境から

python crawler.py arg1 arg2

のようにプログラムを実行すると、sys.argv[0]がcrawler.py、sys.argv[1]がarg1、sys.argv[2]がarg2というようになる。

今回のクローラはスタートとゴールの記事名を必ず引数に取るので、argc = len(sys.argv)は必ず3でなければならない。従って、コマンドライン引数の数が異なる場合には、エラーメッセージを出力しておく。

def main():
    argc = len(sys.argv)
    # 追加
    if argc != 3:
        print(f"[USAGE] python {sys.argv[0]} START GOAL")
        sys.exit(0)

    start = sys.argv[1]
    goal = sys.argv[2]

4.3. ステップ1: 記事内容の取得#

日本語のWikipediaの記事は https://ja.wikipedia.org/wiki/[記事名] というURLを持っている。記事名のところにはURLエンコードされた記事名が入る。

例えば、「日本」というWikipediaの記事は、以下のように取得できる。

# Wikipedia - 日本
base_url = "https://ja.wikipedia.org/wiki/"
title = "日本"
url = base_url + urllib.parse.quote(title)
print(f"URL: {url:s}")

URL: https://ja.wikipedia.org/wiki/%E6%97%A5%E6%9C%AC

HTMLページの取得方法については、前節、HTTP通信で説明したとおりである。

headers = {
    "User-Agent": "Mozilla/5.0",
    "Accept-Language": "ja",
    "Accept-Charset": "utf-8",
}

req = urllib.request.Request(url, headers=headers, method="GET")
with urllib.request.urlopen(req) as resp:
    body = resp.read().decode("utf-8")

<!DOCTYPE html>
<html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" dir="ltr" lang="ja">
 <head>
  <meta charset="utf-8"/>
  <title>
   日本 - Wikipedia
  </title>
  <script>

ページの内容が取得できたら、正規表現を使用して、リンクされているWikipedia日本語版の記事を取得する (プログラムは自分で考えること)。

%E5%95%86%E5%BA%97%E8%A1%97
%E9%9A%A0%E5%B2%90%E5%B3%B6
%E3%82%AB%E3%83%8A%E3%83%80
%E5%AF%BE%E9%A6%AC
%E5%85%AC%E5%AE%89%E5%A7%94%E5%93%A1%E4%BC%9A
%E3%83%A4%E3%83%9E%E3%83%88
%E3%83%AB%E3%83%8A%E3%83%91%E3%83%BC%E3%82%AF
%E6%98%A5%E5%88%86%E3%81%AE%E6%97%A5
%E3%81%8B%E3%82%8B%E3%81%9F
%E3%83%AD%E3%82%B7%E3%82%A2%E9%80%A3%E9%82%A6%E6%86%B2%E6%B3%95

ここで得られる記事名はURLエンコードされているので、urllib.parse.unquote関数を用いて、元の日本語の記事名を復元しておく。

商店街
隠岐島
カナダ
対馬
公安委員会
ヤマト
ルナパーク
春分の日
かるた
ロシア連邦憲法

記事内容の取得

ここまでの内容を元に、1つの記事名titleを引数に取り、その記事にリンクされている、全ての記事名をリストとして返す関数get_pagesを作成しよう。

def get_pages(title):
    """
    指定されたタイトルのページからリンクされているページのタイトルを取得
    """
    # 以下にコードを実装
    ...

4.4. ステップ2: 記事を幅優先探索#

幅優先探索それ自体についてはWikipedia等、ウェブ上の記事を参考にしてほしい。Wikipediaの該当記事にはPython実装のソースコードも示されている。

幅優先探索 - Wikipedia

以下では、標準的なFIFO (first-in-first-out)型のキューを用いた実装を用いる。PythonではqueueモジュールのSimpleQueueが使用できる。

from queue import SimpleQueue

幅優先探索による記事探索のアルゴリズムの概要は以下のようになる。

# キューは現在の記事とリンク元の記事を管理
que = SimpleQueue()
que.put((start, None))
checked = {}  # チェック済みなら、記事名をキー、リンク元の記事を値とする要素を持つ

# キューが空になるまで処理を継続
while not que.empty():
    # スロットリング
    time.sleep(0.1)

    # ノードの取り出し
    node = que.get()
    page, prev = node

    # 既にチェック済みの記事かどうかを調べる
    # !!! 実装する !!!

    # 未チェックの記事なら、リンクされた記事を取得
    next_pages = get_pages(page)

    # 新しい記事の中にゴールが見つかったら終了
    # !!! 実装する !!!

    # 取得した記事名をキューに追加
    # !!! もう少し早くできる !!!
    for next_page in next_pages:
        que.put((next_page, page))

上記のように、幅優先探索では、まずキューに開始点となるノードを追加する。その後、順次、キューの先頭からノードを取り出して、そのノードと隣接するノードを調べ、キューに追加していく。

今回のクローラの例では、最後に、スタートからゴールの記事へと遷移するリンクを復元したいので、キューには記事名と、リンク元の記事を追加しておくと良い。その上で、辞書型のcheckedにチェック済みの記事を記録しておく。checkedは記事名をキーに取り、その記事がチェック済みなら、リンク元の記事名を値として持つようにしておけば良いだろう。

なお、上記の疑似コードでは、新しく見つかった記事について、単純に全ての記事をキューに追加しているが、この部分はもう少し高速化できるので、各自考えてみてほしい。

記事の幅優先探索

上記の内容を元にmain関数内に幅優先探索のプログラムを実装しよう。実装の内容については、前述の疑似コードの!!! ... !!!の部分に適切なコードを与えていけば良い。

スロットリング (throttling)

クローラのプログラムを作成する際、一つのウェブサーバに何度もリクエストを送ると、ウェブサーバの処理が低下するなどの問題が発生する。従って、クローリングのマナーとして、リクエストを頻繁に送りすぎないよう、待ち時間を設定しなければならない。

このように意図的にネットワークの速度を下げる処理をスロットリングと呼び、上記の疑似コードにおいては、リクエストが0.1秒に1回以上送られないように制御している。

4.5. ステップ3: リンクを復元#

スタート (start)から、幅優先探索でゴール (goal)にたどり着いたら、checkedに保存された、リンク元の記事の情報を使って、スタートからゴールに至る記事の遷移を復元しよう。

checkedは「現在の記事」をキーとして、「リンク元の記事」を値に持つ辞書型であったので、goalの記事から逆順にリンク元の記事を辿っていき、startのリンク元であるNoneにたどり着いたら、経路が復元できたことになる。

ただし、この処理を単純に実行すると、経路が逆順になるので、スタートからゴールに至る経路を得るには、最後に配列をreversed等で逆順にする必要があることに注意すること。

# 経路の取り出し
path = [goal]
# !!! 実装する !!!

# 結果の表示
print("")
print("Answer:")
print(" -> ".join(path))

4.6. ステップ4: HTTP通信の高速化#

ここまでプログラムを書き進めると、一応のクローラが完成する。しかし、実際に実行してみると、スロットリングの時間を考慮しても、HTTP通信に少々時間がかかっていることに気がつくかもしれない。

これは、urllibを用いて送信されるリクエストが、接続と切断を繰り返すためであり、今回のクローラがおおよそ同一と考えられるWikipediaのサーバーに接続・切断を繰り返すのは効率が良いとは言えない (実際には、負荷分散されているため物理的に同じサーバーに接続するわけではない)。

この問題を防ぐには、urllibの代わりに、より低レベルなhttp.clientモジュールを用いる必要がある。http.clientモジュールにはHTTPConnectionとHTTPSConnectionというクラスが用意されており、これらのクラスは指定されたURLに接続後、明示的にclose関数が呼ばれるか、通信のエラーが発生しない限りは接続が切られることがない。

以下にhttp.clientモジュールを用いたHTTPリクエストの送信とレスポンスの処理の一例を示すので、これを参考にHTTP通信の高速化を試みてほしい。

import http.client

headers = {
    "User-Agent": "Mozilla/5.0",
    "Accept-Language": "ja",
    "Accept-Charset": "utf-8",
}

# サーバに接続
conn = http.client.HTTPSConnection("ja.wikipedia.org")

# 一つ目の記事の読み込み
title1 = "日本"
conn.request("GET", "/wiki/" + urllib.parse.quote(title1), headers=headers)
resp1 = conn.getresponse()
print(resp1.status, resp1.reason)
data1 = resp1.read().decode("utf-8")
resp1.close()

# 二つ目の記事の読み込み
title2 = "Python"
conn.request("GET", "/wiki/" + urllib.parse.quote(title2), headers=headers)
resp2 = conn.getresponse()
print(resp2.status, resp1.reason)
data2 = resp2.read().decode("utf-8")
resp2.close()

# 切断
conn.close()

4.7. 課題#

問1

本節の内容に従い、Wikipedia日本語版のクローラを作成せよ。クローラが作成できたら、いくつかの記事のペア(3例程度)について、各記事ペアを結ぶ記事の遷移を調べよ。

例1:

python crawler.py "伊藤博文" "紫式部"
Answer: 伊藤博文 -> 日本銀行券 -> 紫式部

例2:

python crawler.py "ドラえもん" "東京スカイツリー"
Answer: ドラえもん -> 月刊コロコロコミック -> 東京スカイツリー

問2

作成したクローラを改良し、適当な単語から3次以上の隔たりを持つ記事を探しなさい。実装にあたっては、スタートの記事からの距離もキューに追加するようにし、ゴールに存在しない記事名 (例えば __DUMMY_PAGE__など)を与えるようにすると、実装が容易になるだろう。

ただし、リンクがつながった記事の数が指数関数的に増えていくため、3次以上の隔たりを持つ記事を探すには相当時間がかかるので注意すること。

なお、ここでの「3次の隔たり」とは、仮にスタートの単語を「日本」とすると、

日本 -> 記事A -> 記事B -> 記事C

の「記事C」に相当するものとする。

例1: 「渋沢栄一」からスタート

渋沢栄一 -> 火星 -> 火星探査 -> 地球

例2: 「清少納言」からスタート

清少納言 -> 百人一首 -> 手事物 -> 千鳥の曲