Ahogrammer

Deep Dive Into NLP, ML and Cloud

Wikipedia内ページランクを計算して、重要なページを抽出する

自然言語処理をする際、データソースとして Wikipedia を使用することがあります。 Wikipedia を使う際、ページによっては内容が薄いので、ページを選択することがあります。 そのための方法として、Wikipedia 内のページランクを計算して、重要ページを抽出する方法が提案されています。

本記事では、Wikipedia 内のページランクを計算して、重要なページを抽出する方法を紹介します。 ツールとしては Project Nayuki で公開されているツールを使います。 このツールは StanfordSQuAD のデータセットを作成する際にも使われています。

では、日本語版 Wikipedia を用いて、ページランクを計算してみます。

準備

まずはページランクの計算に使うソースコードWikipedia のダンプデータをダウンロードします。 ファイルをダウンロードする前に、作業用のディレクトリを作成しておきましょう。

$ mkdir workspace

以降では、このディレクトリの中で作業を進めていきます。

データのダウンロード

ここでは Wikipedia のダンプデータをダウンロードします。 以下の2つのファイルをダウンロードして、作業用ディレクトリに入れてください。

ソースコードのダウンロード

次に、Wikipedia 内のページランクを計算するためのコードをダウンロードします。 Project NayukiComputing Wikipedia’s internal PageRanks から以下のソースコードをダウンロードして、作業用ディレクトリに入れてください。

  • WikipediaPagerank.java (main program)
  • Pagerank.java (core numerical algorithm)
  • PageIdTitleMap.java (boring I/O)
  • PageLinksList.java (boring I/O)
  • SqlReader.java (ugly FSM)
  • SortPageTitlesByPagerank.java (secondary program)

これで必要なデータとソースコードは揃いました。 では日本語版 Wikipediaページランクを計算してみましょう。

ページランクの計算

ページランクの計算は、ダウンロードした WikipediaPagerank.java を使って行います。 ただし、そのままだと動かないため、コードを少し書き換える必要があります。 以下の2つのファイルを書き換えることで、正常に動作させることができます。

  • PageIdTitleMap.java
  • PageLinksList.java

PageIdTitleMap.java43行目 を以下のように書き換えてください。

...
for (List<Object> tuple : multipleRows) {
    // if (tuple.size() != 12)
    if (tuple.size() != 14)
        throw new IllegalArgumentException("Incorrect number of columns");
    Object namespace = tuple.get(1);
...

同様に、PageLinksList.java46行目 を以下のように書き換えてください。

...
for (List<Object> tuple : multipleRows) {
    // Get tuple fields
    // if (tuple.size() != 3)
    if (tuple.size() != 4)
        throw new IllegalArgumentException("Incorrect number of columns");
    Object srcId = tuple.get(0);
...

上記のように変更すると動く理由として、以下が考えられます。(要検証)

  • プログラムを書いたとき(2014)と今ではダウンロードしたファイルのデータ構造が違う
  • 日本語版に特有なファイル構造になっている

また、WikipediaPageRank.javaの30行目と33行目を以下のように書き換えます。

// new File("enwiki-20140102-page.sql.gz"); 
new File("jawiki-yyyymmdd-page.sql.gz"); 
// new File("enwiki-20140102-pagelinks.sql.gz"); 
new File("jawiki-yyyymmdd-pagelinks.sql.gz");

書き換え終わったら、プログラムをコンパイルして実行します。20〜30分で実行完了します。

$ javac WikipediaPagerank.java
$ java WikipediaPagerank

プログラムの実行が完了すると、以下の3つのファイルが生成されていることが確認できます。

wikipedia-pagerank-page-id-title.raw には、ページIDとタイトルの対応関係が格納されています。 wikipedia-pagerank-page-links.raw には、ページのリンクが格納されています。 wikipedia-pageranks.raw がお目当てのファイルです。このファイルには各ページのページランクが格納されています。なお、行数がページIDに対応しています。

ページランクとタイトルの対応付け

最後に、ページランクとタイトルを対応付けてみます。 そのために、wikipedia-pagerank-page-id-title.rawwikipedia-pageranks.raw を使います。 2つのファイルを用いて、ページランクとタイトルを結びつけることができます。

まずは、wikipedia-pageranks.raw からページランクを読み込んでみましょう。 このファイルはバイナリファイルなので、読み込みを少々工夫する必要があります。 python_java_datastream から data_input_stream.py をダウンロードして、以下のスクリプトを書けばOKです。

pageranks = []
with open('wikipedia-pageranks.raw', 'rb') as f:
    stream = DataInputStream(f)
    while True:
        try:
            val = stream.read_double()
            pageranks.append(val)
        except struct.error:
            break

各ページIDに対するページランクが格納されていることを確認できます。

>>> print(pageranks[:10])
[0.0, 0.0, 0.0, 0.0, 0.0, 5.776048392073801e-06, 0.0, 0.0, 0.0, 0.0]

次に、wikipedia-pagerank-page-id-title.raw からページIDとタイトルを読み込んでみましょう。 このファイルは普通のテキストファイルなので、読み込みは簡単です。 以下のスクリプトを実行して、ページIDとタイトルの対応付けを読み込みましょう。

id_title = {}
with open('wikipedia-pagerank-page-id-title.raw') as f:
    for title in f:
        page_id = int(f.readline())
        id_title[page_id] = title.rstrip()

最後に、ページランクと紐付ければ完了です。以下のスクリプトを実行しましょう。

with open('wikipedia-pagerank-title.txt', 'w') as f:
    for page_id, pagerank in enumerate(pageranks):
        title = id_title.get(page_id, '')
        f.write('{}\t{}\n'.format(pagerank, title))

ページランクの大きい順にタイトルを表示してみましょう。以下のコマンドを実行します。

$ sort -k1gr -t $'\t' wikipedia-pagerank-title.txt | head -10
0.0021740206527864217   日本
0.0015469106504595721   英語
0.0013633067437804802   アメリカ合衆国
0.0008778096763338723   典拠管理
0.0006934665842026948   イギリス
0.0006744463667220464   地理座標系
0.0006707419372096121   バーチャル国際典拠ファイル
0.0006570742501433739   国立国会図書館
0.0006510205158963063   2006年
0.0006499682058763622   東京都

上位100位は日付が結構多めです。

以上で完了です。

おわりに

本記事では、日本語版Wikipediaに対してページランクを計算する方法を紹介しました。本記事が皆様のお役に立てば幸いです。

また、2017年10月01日のダンプに対してページランクを計算したファイルを公開しています。以下のリンクからダウンロードすることができます。

私のTwitterアカウントでも機械学習自然言語処理に関する情報をつぶやいています。

この分野にご興味のある方のフォローをお待ちしています。

参考資料