はじめに

Webサービスのプログラミングに必要なことのだいたいは、スクレイピングに学んだ - Line 1: Error: Invalid Blog('by Esehara' )

この前↑の記事をみかけました。クローリングやスクレイピングは、色々と応用が効きそうなのでしっかり勉強したい。 PythonではScrapyという有名なクローリング・スクレイピング用のライブラリがあるけど、今回は勉強としてScrapyを使わずに実装してみる。流れとしては以下のとおり

• Webクローラの構築
• Mecabで日本語の形態素解析
• 検索エンジンの構築
• データをMongoDBに格納
• FlaskでWebアプリ作成

作成したプログラムはgithubにあげています。実際のクローラや検索エンジンでは、高速化や検索結果の最適化などまだまだ多くの事を考慮する必要があるようです。今回書いたプログラムは最低限の機能しか持たないものですが、それでも考えなければならないことがたくさんありました。

• https://github.com/mejiro/SearchEngine

Webクローラの構築

Webクローラの構築方法はUdacityのレッスンを見ながら勉強したので、これから書くコードの意味がわからなければUdacityのレッスンをやっていくといいです。今回は実装しませんでしたがこのチュートリアルのLesson5,6では高速化や検索エンジンの最適化などさらに踏み込んだことも解説されています。

• コンピュータ･サイエンス入門 | UDACITY on Edmaps

URLリンクの抽出

クローラはWebページ間のリンクをたどることによってウェブサイトを自動的に検出してスキャンしていく。そのためにはページの中からURLリンクを見つけ出す必要があります。いきなりWebクローラを書こうとすると大変なので、まずはURLリンクの抽出方法を考える。

Udacityの講師によるとHTMLリンクの形式は<a href="URL"となっているので、findメソッドや文字列のスライスを上手く使うと↓のようなコードでページ内のリンクを抽出できる。

# 引数のpageは、html文書を格納した文字列
def get_next_target(page):
    start_link = page.find('<a href=')
    if start_link == -1:
        return None, 0    
    start_quote = page.find('"', start_link)
    end_quote = page.find('"', start_quote + 1)
    url = page[start_quote + 1:end_quote]
    return url, end_quote

def print_all_links(page):
    while True:
        url, endpos = get_next_target(page)
        if url:
            print url
            page = page[endpos:]
        else:
            break

if文やwhile文の条件は、True or Falseだけでなく「None」や「空リスト」、「空文字列」も入れれることを利用すると簡潔にコードがかけていい感じ。

クローラの作成

クローラを書くときには、Webページに循環リンク(相互リンク等)が存在するということに気をつけないといけない。そのためには巡回済みのページをもうクロールしないように工夫する必要がある。

def get_page(url):
    try:
        import urllib
        return urllib.urlopen(url).read()
    except:
        return ""

def get_next_target(page):
    start_link = page.find('<a href=')
    if start_link == -1: 
        return None, 0
    start_quote = page.find('"', start_link)
    end_quote = page.find('"', start_quote + 1)
    url = page[start_quote + 1:end_quote]
    return url, end_quote

def union(p,q):
    for e in q:
        if e not in p:
            p.append(e)

def get_all_links(page):
    links = []
    while True:
        url,endpos = get_next_target(page)
        if url:
            links.append(url)
            page = page[endpos:]
        else:
            break
    return links

def crawl_web(seed):
    # seed : 一番最初の元となるページ(クローリングにおいてとても重要)
    # clawled : クロールが終了したページ
    # tocrawl : クロールするページ

    tocrawl = [seed]
    crawled = []
    while tocrawl:
        page = tocrawl.pop()
        if page not in crawled:
            union(tocrawl, get_all_links(get_page(page))
            crawled.append(page)
    return crawled

これで最低限の機能しか持たないがクローラの完成！

最大ページ数を指定する

実際のWebページは多くのリンクをもっており、全てをクローリングすることは不可能。最大ページ数を指定するには↓のように書き換える。

def crawl_web(seed, max_pages):
    tocrawl = [seed]
    crawled = []
    while tocrawl:
        page = tocrawl.pop()
        if page not in crawled and len(crawled) < max_pages:
            union(tocrawl, get_all_links(get_page(page)))
            crawled.append(page)
    return crawled

最大の深さを指定する

これまで書いていたプログラムはWebページの最後のリンクを次々と巡回していく深さ優先探索となっていた。最大の深さを指定することでまんべんなくクローリングできる。

def crawl_web(seed,max_depth):    
    tocrawl = [seed]
    crawled = []
    next_depth = []
    depth = 0
    while tocrawl and depth <= max_depth:
        page = tocrawl.pop()
        if page not in crawled:
            union(next_depth, get_all_links(get_page(page)))
            crawled.append(page)
        if not tocrawl:
            tocrawl, next_depth = next_depth, []
            depth = depth + 1
    return crawled

GitHubにあげているプログラムも、最大の深さを指定できるものにしています。

Mecabで日本語の形態素解析

検索エンジンの構築に入る前に形態素解析について勉強。英語と違って日本語の形態素解析はかなり難しい。１から実装するのは無理なのでMecabというライブラリを使用する。

Mecabのインストール

参考：Homebrew + virtualenv 環境でMeCabのインストール - さりんじゃーのプログラミング日記

$ brew install mecab mecab-ipadic
$ mecab
すもももももももものうち
すもも   名詞,一般,*,*,*,*,すもも,スモモ,スモモ
も 助詞,係助詞,*,*,*,*,も,モ,モ
もも  名詞,一般,*,*,*,*,もも,モモ,モモ
も 助詞,係助詞,*,*,*,*,も,モ,モ
もも  名詞,一般,*,*,*,*,もも,モモ,モモ
の 助詞,連体化,*,*,*,*,の,ノ,ノ
うち  名詞,非自立,副詞可能,*,*,*,うち,ウチ,ウチ
EOS

次にPythonバインディングのダウンロード

MeCab: Yet Another Part-of-Speech and Morphological Analyzer から最新版のソースを確認して↓のようにインストール

$ wget https://mecab.googlecode.com/files/mecab-python-0.996.tar.gz
$ workon search_engine
$ pip install mecab-python-0.996.tar.gz # これでいれれる!
$ rm mecab-python-0.996.tar.gz

tar.gzのままインストール出来るの初めて知った。

PythonからMecabを使う

インタプリタからさわってみた。

$ python
>>> # coding: utf-8
>>> import MeCab
>>> m = MeCab.Tagger("-Ochasen") # 出力をChasenモードにする
>>> string = u'Pythonで作る検索エンジン'
>>> string = string.encode("utf-8")
>>> node = m.parseToNode(string)
>>> while node:
...     print node.surface, node.feature
...     node = node.next
...
 BOS/EOS,*,*,*,*,*,*,*,*
Python 名詞,一般,*,*,*,*,*
で 助詞,格助詞,一般,*,*,*,で,デ,デ
作る 動詞,自立,*,*,五段・ラ行,基本形,作る,ツクル,ツクル
検索 名詞,サ変接続,*,*,*,*,検索,ケンサク,ケンサク
エンジン 名詞,一般,*,*,*,*,エンジン,エンジン,エンジン
 BOS/EOS,*,*,*,*,*,*,*,*

MeCabでUnicode文字列を扱う場合は、一度エンコードする必要がある。この際、node = tagger.parseToNode(string.encode("utf-8"))とすると、stringがパース中にガベコレされてしまって、変な挙動になる場合があるので注意。このように一度変数に代入すれば問題ない。

Homebrew + virtualenv 環境でMeCabのインストール - さりんじゃーのプログラミング日記

これは気をつけないと...

文書を単語に切り分ける

# coding: utf-8
import Mecab

def split_to_word(text):
    words = []
    m = MeCab.Tagger("-Ochasen")
    text = text.encode("utf-8")
    node = m.parseToNode(text)
    while node:
        words.append(node.surface)
        node = node.next
    return words

MeCab手軽に使えていいですね。

検索エンジンの構築

クローラが完成したら検索エンジンの構築方法について考える。

インデックスのデータ構造

Udacityのチュートリアルでは、リストオブジェクトを使って↓のようにデータ構造を定義していた。

[
  [<keyword1>, [<url1-1>,<url1-2>]],
  [<keyword2>, [<url2-1>]],
  ...
]

但し要素にアクセスする時は、要素数ではなく連想配列のようにキー値を用いたほうがいいように思うので辞書型を使って↓のように定義する。

[
  {
    keyword:'keyword1',
    url:[<url1-1>,<url1-2>],
  },
  {
    keyword:'keyword2',
    url:[<url2-1>],
  },
]

こうするとMongoDBにそのまま格納できて便利。

インデックスに要素を追加する関数

要素を追加する際には、すでに同じkeywordを登録してあるか確認する。

def add_to_index(index,keyword,url):
    for entry in index:
        if entry['keyword'] == keyword:
            entry['url'].append(url)
            return
    index.append({'keyword':keyword,'url':[url]})

但しこのままだと同じページ内でキーワードが2回以上出てきた場合、登録されるURLも重複してしまうため、先程定義したadd_to_indexを↓のように書き加える。

def add_to_index(index, keyword, url):
    for entry in index:
        if entry['keyword'] == keyword:
            if not url in entry['url']:
                entry['url'].append(url)
            return
    # not found, add new keyword to index
    index.append({'keyword':keyword,'url':[url]})

インデックスの構築

Webページを形態素解析してインデックスを作成する。日本語の場合、これはかなり難しいからMecabを利用する。

def add_page_to_index(index,url,content):
    """contentを形態素解析してindexにurl登録"""
    for keyword in split_to_word(content):
        add_to_index(index, keyword, url)

クローラとインデックスの構築を連携させる

インデックスを構築する関数が完成したので、crawl_web()メソッドを書き換えて先ほどのクローラと連携させる。

def crawl_web(seed):
    tocrawl = [seed]
    crawled = []
    index = []
    while tocrawl:
        page = tocrawl.pop()
        if page not in crawled:
            content = get_page(page)
            add_page_to_index(index, page, content)
            union(tocrawl, get_all_links(content)
            crawled.append(page)
    return index

これでクローリングをしながら、インデックスを構築出来るようになった。

データをMongoDBに格納

pymongoの使い方まとめは(pymongo使い方まとめ(Python, MongoDB) - Programming Log) を書いたのでそちらを参照してください。

インデックスをデータベース上に構築する

add_to_index()を書き換える。

def add_to_index(index, keyword, url):
    for entry in index:
        if entry['keyword'] == keyword:
            if not url in entry['url']:
                entry['url'].append(url)
            return
    # not found, add new keyword to index
    index.append({'keyword':keyword,'url':[url]})

↓

from search_engine import collection as col

def add_to_index(keyword, url):
    entry = col.find_one({'keyword': keyword})
    if entry:
        if not url in entry['url']:
            entry['url'].append(url)
            col.save(entry)
        return
    # not found, add new keyword to index
    col.insert({'keyword': keyword, 'url': [url]})

find_one()メソッドを使うとfor文が消えていい感じで書ける。

動作確認

以下のように指定して実行してみました。

• シードページ : Sphinxドキュメント — Sphinx 1.2.3 ドキュメント
• 最大の深さ : 2

これでクローリングや検索エンジンの最低限の機能が実装できたので、動かしてみました。ものすごく遅いけど、MongoDBの中身を見てみると順調に追加されておりちゃんと動いていることが確認できました。 リクエストを投げすぎると攻撃とみなされる危険もあるようですが、このプログラムはMeCabで切り分けた単語を順番にMongoDBにinsertしていっているので、ページを1つ解析するのも多くの時間がかかっており、攻撃とみなされる心配は無さそうです。

スクレイピングが必要になった際には、このプログラムでは効率が悪すぎるのでScrapy等の優れたライブラリを使うことになりますが、その時はちゃんとリクエストの回数に気を遣う必要がありそうですね。

FlaskでWebアプリ作成

せっかくなのでGoogleのように検索エンジンをWebブラウザから使う。

キーワードの検索

インデックスにkeywordがあればurlのリストを返し、無ければ空文字列を返す。 MongoDBを使わない場合は↓のようなコードになる。

def lookup(index, keyword):
    for entry in index:
        if entry['keyword'] == keyword:
            return entry['url']
    return []

今回はMongoDBを使うので、↓のようなコードになる。

def lookup(keyword):
    return col.find_one({'keyword': keyword})

Flaskのコード

@app.route('/', methods=['GET', 'POST'])
def index():
    """Return index.html
    """
    if request.method == 'POST':
        keyword = request.form['keyword']
        if keyword:
            return render_template('index.html',
                                   query=col.find_one({'keyword': keyword}),
                                   keyword=keyword)
    return render_template('index.html')

今作ったWebアプリを動かすと↓のようにちゃんと動作しているのが確認できます。

おわりに

本当に最低限の機能しかありませんが、とりあえず検索エンジンのようなものが完成しました。実際にクローリングとかをする場合には、Scrapy等のライブラリを使うことになると思うので、次はScrapyをいじってみようと思います。

参考資料

• コンピュータ･サイエンス入門 | UDACITY on Edmaps
• 話題のクローラー・スクレイピング！PythonならScrapyが超優秀な件 | Wizard In The Market
• PythonによるWebスクレイピング入門
• PythonとかScrapyとか使ってクローリングやスクレイピングするノウハウを公開してみる！ - orangain flavor
• Python で Twitter からの情報収集 (MeCab による形態素解析編) - Qiita
• エキスパートPythonプログラミング