終末 A.I.

データいじりや機械学習するエンジニアのブログ

トポロジカルソートと強連結成分分解でWikipediaの特定カテゴリー配下のページをすべて取得する

グラフ理論

Wikipediaの特定カテゴリー配下のページをすべて取得するためには、整理されていないグラフデータ特有のいくつかの問題に向き合う必要があります。

一つは、Category:カツラ科と糸井の大カツラのように、サブカテゴリーにはページへのリンクが含まれているが、カテゴリー本体にはページへのリンクが含まれていないケースがあるという問題。

もう一つは、Category:インフォグラム・エンターテインメントームソフトとCategory:アタリのゲームソフトのように、お互いがお互いのサブカテゴリーに含まれてしまっているケースがあるという問題です。

これらの問題は、以下の手順を踏むことで解決できます。

  1. カテゴリーにリンクされているページだけでなく、サブカテゴリー内のリンクを順にたどって含まれるすべてのページを収集する

  2. ただし、一度たどったカテゴリーに再度到達した場合、それ以上はそのルートを探索しない

日本語Wikipediaのカテゴリー数は21万以上あります。ナイーブに上記のアプローチを実行すると、配下のサブカテゴリーの深さや数量に応じて時間がかかってしまいます。

そこで、事前にカテゴリー - サブカテゴリーのリンク構造を洗い出しておくことを検討します。グラフに関するアルゴリズムである、トポロジカルソートと強連結成分分解を使用することにより、シンプルにこの処理を実装することができます。

以下では、Wikipediaデータからカテゴリーリンクの一覧を取得する方法から、トポロジカルソートと強連結成分分解を使用して、カテゴリー配下の全てのページを取得するアプローチについて紹介します。

紹介する処理の実装は、下記のリポジトリの category.py にまとめています。

目次

Wikipediaからカテゴリーリンク一覧データを取得する

まず、Wikipediaのカテゴリーリンク構造を表すデータを取得します。Wikipediaのカテゴリー関係のデータには2種類あります。

1つ目は、カテゴリーとページ、カテゴリーとカテゴリーの親子関係を表したカテゴリーリンクデータ。
2つ目は、ページIDとページ名の一覧を含むページ一覧データです。

詳細は後述しますが、カテゴリーリンクデータだけではカテゴリーの親子関係を完全にたどることはできません。ページ一覧データも使用することにより、ようやくカテゴリーの親子関係を洗い出せます。

カテゴリーリンクデータの取得

カテゴリーリンクデータは、Wikipedia内のカテゴリーとページ、カテゴリーとサブカテゴリーのリンク関係を表すデータです。*1
SQLのテーブルデータとして提供されており、3つの重要なカラムを持ちます。

  • cl_from はリンク元（配下のページもしくはサブカテゴリー）を示すカラムで、ページIDが格納されている

  • cl_to はリンク先（親カテゴリ）を示すカラムで、カテゴリーの名称が格納されている

  • cl_type はリンク元のページ種類を示すカラムで、ページかサブカテゴリーかを示す値が格納されている

注意が必要なのは、 cl_from と cl_to とでは格納されている値の種類が異なる点です。このままでは、サブカテゴリー配下のページおよびサブカテゴリーを探索する際に問題がでてしまいます。

そこで、下記のページ一覧データを使用することにより、 cl_from と cl_to に格納されている値のマッチングを行います。

ページ一覧データの取得

ページ一覧データは、Wikipedia内のページに関する基本情報を表すデータです。このページ一覧データにはカテゴリーページのデータも含まれています。*2
カテゴリーリンクデータと同じくSQLのテーブルデータとして提供されており、2つの重要なカラムを持ちます。

  • page_id は各ページのページIDを示すカラムで、カテゴリーリンクデータの cl_from に対応する値が格納されている

  • page_titleは各ページのタイトルを示すカラムで、カテゴリーリンクデータの cl_to に対応する値が格納されている

上記からわかるように、ページ一覧データを使用してページIDとページタイトルの対応関係を取得することができます。

この情報を利用して、カテゴリーリンクデータに含まれる cl_from をページタイトルに（もしくは、 cl_to をページIDに）変換することにより、カテゴリーの親子関係をたどることができます。

カテゴリーリンク一覧データの生成

上述のカテゴリーリンクデータとページ一覧データを用いて、カテゴリーリンク一覧データを作成します。

このとき、カテゴリーからサブカテゴリーへのリンクを示すデータと、カテゴリーからページへのリンクを示すデータを別々に作成することがポイントです。理由は2つあります。

一つ目の理由は、ページとカテゴリーの名称が重複することがあるためです。
Wikipediaでは、名前空間内の名称の一意性は担保されています。しかし、ページ名称とカテゴリー名称とは、お互いに独立の名前空間を持つ運用が行われているため、名称が衝突する可能性があります。
実際に、Category:カツラ科とカツラ科のように衝突している例が多く存在します。

二つ目の理由は、後述するトポロジカルソートと強連結成分分解の計算量を削減するためです。
これらのアルゴリズムは、ノード数とエッジ数の合計に比例した計算量がかかります。また、入口も出口もあるようなノードを整理するために使用されるものです。
このため、確実に処理の対象にならいないことが分かっているページを表すノードは、トポロジカルソートと強連結成分分解の対象になるカテゴリーを表すノードとは、分けて管理しておく方が効率よく扱う事ができます。

GitHubの実装では、カテゴリー名からそのカテゴリー配下のページのセットを返す categorypages オブジェクトと、カテゴリー名からそのカテゴリー配下のサブカテゴリーのセットを返す categorygraph オブジェクトを生成するようにしています。

def show_category_directlinks(categorypages, category):
    if category in categorypages:
        print("Pages:", categorypages[category])

現時点では、上記の show_category_directlinks 関数を使用し、 category に「カツラ科」と入力すると、配下のページとして「カツラ_(植物)」と「カツラ科」が取得できるだけです。
「カツラ科」カテゴリーのサブカテゴリーである、「著名なカツラ」に配下のページは残念ながら取得することはできません。

def show_category_alllinks_with_dfs(categorypages, categorygraph, category):
    class Node(object):
        def __init__(self):
            self.visited = False

    V = defaultdict(Node)
    pages = set()

    def visit(v):
        nonlocal pages

        if V[v].visited:
            return
        V[v].visited = True
        if v in categorypages:
            pages |= categorypages[v]
        if v in categorygraph:
            for m in categorygraph[v]:
                visit(m)

    visit(category)
    print("Pages:", pages)

一方、深さ優先探索ですべての配下のサブカテゴリーを探索する show_category_alllinks_with_dfs 関数を使用することにより、すべての配下のページにアクセスすることができます。
しかしこの方法では、「科学」カテゴリーのようなサブカテゴリーおよび後述するSCCが大量にあるカテゴリーの探索に、それなりの時間を要してしまいます。

実際、手元のMBP環境では20秒ほどかかりました。これでは、頻繁にカテゴリー配下のページを取得する必要がある際には使い物になりません。配下のサブカテゴリー一覧を事前に洗い出しおくことを検討する必要があります。

カテゴリーリンク一覧データから配下のページ一覧を洗い出す

以下では、カテゴリーリンク一覧データから配下のページ一覧を取得する方法について説明していきます。方針は、下記の2ステップのみです。

  1. トポロジカルソートを利用して、カテゴリーをサブカテゴリーが親カテゴリーより後ろにくるようなリストに並び替える

  2. 上記で作成したリストを後ろから順に処理し、サブカテゴリーのページ一覧を親カテゴリーのページ一覧にマージする

このとき、Wikipediaのカテゴリーリンクに巡回が存在することが大きな壁として立ちはだかります。
そこで強連結成分分解を使用して、この巡回するルートを削除することにより、処理が問題なく実現できるように試みます。

グラフの基礎

グラフとは、ノードとエッジの組で表せるデータ構造のことを指す用語です。

ノードは、グラフ内の要素を表し、Wikipediaのデータではページやカテゴリーに相当します。
エッジは、ノード間の接続情報を表し、Wikipediaのデータではカテゴリーリンクデータに相当します。

グラフは、エッジに向きがあるか否かで大きく二つに分けられます。有向グラフと無向グラフです。

有向グラフは、連絡網やTwitterのフォロー関係のように、エッジに向きがあるグラフのことです。この記事で扱っているカテゴリーリンク一覧データも、まさに有向グラフの一つです。

一方、無向グラフは、路線図のように、エッジに向きがないグラフのことです。

有向グラフは、閉路と呼ばれる巡回構造を持つものがあります。一方で閉路を持たない有向グラフも存在し、このようなグラフを有向非巡回グラフ（DAG：Directed Acyclic Graph）と呼びます。

このDAGには非常に便利な性質があり、下記で説明するトポロジカルソートを適用できることもその一つです。

トポロジカルソートによるノードの並び替え

トポロジカルソートは、上述のDAGに適用することにより、グラフ内のノードを子ノードが親ノードより後ろにくるように並べ替えることができるアルゴリズムです。*3
お気持ちだけ簡単に説明すると、下記の手順でソートを実現します。

  1. グラフ内の探索されていない任意のノードを選択する
  2. 選択したノートからたどれるルートを深さ優先で探索する
  3. 子ノードがないノードは、グラフから除きリストの前方に追加する
  4. すべての子ノードをグラフから取り除いたノードも、グラフから除きリストの前方に追加する
  5. グラフからノードがなくなるまで、上記1-4の作業を繰り返す

このトポロジカルソートを、カテゴリー名からそのカテゴリー配下のサブカテゴリーのセットを返す categorygraph に適用します。期待値はソートされたカテゴリー一覧が返されることですが、残念ながらそのままではうまくいきません。

なぜなら、 categorygraph オブジェクトには、Category:インフォグラム・エンターテインメントームソフトとCategory:アタリのゲームソフトのように、お互いがお互いのサブカテゴリーであるケースを含むためです。

つまり、グラフに閉路が存在するため、非巡回なグラフにのみ適用できるトポロジカルソートが上手く機能しないのです。

この問題を解決するためには、なんとかしてグラフ内から閉路を検出して取り除いてやる必要があります。その方法として、下記の強連結成分分解を使用します。

強連結成分分解による閉路の検出と除去

強連結成分（SCC：Strongly Connected Components）分解は、有向グラフ内の強連結成分を検出し、それらを一つにまとめるために用いることができる手法です。

強連結とは、互いから互いにたどり着くためのルートが存在するノードのペアを指す用語です。SCCは、強連結である全てのノードを含んだノード群のことを指します。

つまり、グラフ内に閉路がある場合、その閉路上の任意のノードのペアは強連結になります。また、お互いが強連結なノード同士を集めたものがSCCに当たります。

そして、グラフ上のすべてのSCCをもれなく洗い出す方法が強連結成分分解です。*4簡単に説明すると、下記の手順でSCCを洗い出します。

  1. グラフ内の探索されていない任意のノードを選択する
  2. 選択したノートからたどれるルートを深さ優先で探索し、マークを付けていく
  3. ノードを探索中にすでに探索済みのノードを検出した場合、ノードのマークを更新してそのルートの探索を終了する
  4. ルートをたどれるノードがなくなった場合、同じマークのついたノードをSCCとしてリストに追加する
  5. 上記1-4の手順を、探索されていないノードがなくなるまで繰り返す

Tarjan's Algorithm Animation.gif
By LynX - Own work, CC BY-SA 3.0, Link

SCCと閉路は異なる概念ですが、すべての閉路は何らかのSCCに含まれます。そのため、SCCをすべて抽出できれば、すべての閉路を構成するノード群を抽出できます。

また、このSCCを一つのノードとして扱うことにより、有向グラフを閉路の存在しないDAGに変換できます。

振り返りになりますが、上記のトポロジカルソートで問題になっていたのは、有向グラフに閉路が含まれているせいで、アルゴリズムがうまく機能しないことでした。

つまり、強連結成分分解を適用しDAGに変換した後の有向グラフであれば、トポロジカルソートを問題なく適用することができるのです。

配下のページ一覧の取得

ここまでくればあと一息です。下記の手順でカテゴリーリンク一覧データを変換することにより、配下のページをいつでも簡単に引き出す事ができるようになります。

  1. カテゴリーリンク一覧データを、強連結成分分解する
  2. カテゴリーリンク一覧データを、強連結成分分解した結果を元にDAGに変換する
  3. 変換したDAGのノードを、トポロジカルソートする
  4. カテゴリーリンク一覧データを、トポロジカルソートの結果を元に更新する

GitHubコード内の update_categorygraph 関数を呼び出すことによりこれらの処理を実現できます。

この関数では3つのオブジェクトを出力とします。

  • Wikipediaに記載のカテゴリー名から、内部的に付与したカテゴリーIDに変換する category2indices オブジェクト

  • カテゴリーIDから、すべての配下のサブカテゴリーセットを返すように更新した categorygraph オブジェクト

  • カテゴリーIDから、カテゴリー配下のページセットを返す categorypages オブジェクト

categorypages オブジェクトはWikipediaに記載の情報のままです。しかし、 categorygraph オブジェクトで簡単に全てのサブカテゴリーを取得できるため、すべての配下のページに短い時間でアクセスすることができます。

def show_category_alllinks(categorypages, categorygraph, category2indices, category):
    if category in category2indices:
        index = category2indices[category]
        pages = [categorypages[index]]
        for sub_c in categorygraph[index]:
            pages.append(categorypages[sub_c])
        pages = set().union(*pages)
        print("Pages:", pages)

上記の show_category_alllinks 関数を使用し、 category に「カツラ科」と入力すると、「カツラ_(植物)」と「カツラ科」だけでなく、サブカテゴリーである「著名なカツラ」の配下のページも取得できます。

また、大量にサブカテゴリーやSCCが存在する「科学」カテゴリーでも、一瞬で配下のページすべてを取得できるようになっています。
手元のMBP環境では500msほどで処理が完了します。これは、深さ優先探索を逐一適用していた時に比べ、40分の1程度の時間です。

まとめ

この記事では、トポロジカルソートと強連結成分分解を使用することにより、Wikipediaの特定カテゴリー配下のサブカテゴリーを洗い出す方法を紹介しました。

また、洗い出したサブカテゴリー情報を使用することにより、現実的な時間でカテゴリー配下のすべてのページを洗い出す事ができることも示しました。

今回、紹介した方法は任意の有向グラフに適用することができます。巡回構造がある、入口と出口が入り組んでいるような有向グラフに出会った際はぜひ活用してみてください。

*1:カテゴリーリンクデータの最新版はこちら

*2:ページ一覧データの最新版はこちら

*3:深さ優先探索によるトポロジカルソートアルゴリズムの詳細はこちら

*4:Tarjan's algorithm による強連結成分分解の詳細はこちら