Node.js + MongoDBでWikipediaのリンクを辿ってみる

はじめに

チーム内で雑談をしているとき、「ある人から知り合いを6人辿ると全世界の人に辿り着けるらしい」という話を聞き、調べてみるとこのような仮説は六次の隔たりという名前がついているようです。Wikipediaの記事に対しても同様の仮説が語られており、ソーシャルメディアや某掲示板等でたまに話題に挙がったりしているようでした。

Wikipediaの記事総数は2022年12月17日現在で1,354,638件であり、1記事あたり平均して100件リンクを含むのだと仮定すると、リンクを4回辿れば全ての記事に辿り着ける計算です。（もちろん記事によってリンク数の多寡には大きく開きがあるので超ざっくり推定です）

これを自動化できたら面白いかもねと思い立ち、始点と終点の記事を指定したら自動でその経路を調べてくれるツールをNode.jsとMongoDBで作ってみました。その過程について本記事でお話していきたいと思います。

前提条件

以下のミドルウェアバージョンを用いて本記事を執筆しています。

• Node.js v18.12.0
• MongoDB v6.0.3

記事のリンクを収集する

Wikipediaの記事ダンプを取得する

自動化に先立って、まずは記事とそれが含むリンクを保持しておく必要があります。Wikipediaではプログラムによる記事の取得（クローリング）は禁止されているため、代わりに記事を取得する手段としてXML形式のダンプを利用することになります。今回は記事執筆時点で最新版である、jawiki-20221201-pages-meta-current.xml.bz2を使用しました。bzip2で圧縮されており、これを解凍するとなんと19.6GBもあります。

XML形式のままではプログラムから検索するにはあまりに使い勝手が悪いので、Node.jsでXMLファイル内の記事から正規表現でリンクを抽出し、それをMongoDBに登録していくこととしました。

ちなみに、XML形式をCSV形式やJSON形式等に変換する既存のツールとしてwikiextractorというものもあり、これを使えば自作プログラムなしにMongoDBにデータを登録できる可能性もありましたが、私の環境ではインストール時にエラーが発生し解消できなかったため今回は使用しませんでした。

記事ダンプからリンクを抽出しMongoDBに登録する

今回作成するリンク抽出プログラムの流れは次のようになります。

1. XMLファイルをStreamを利用して開く
2. 記事を表す<page>タグの本文を取得する。
3. 各本文に対し、Wikipediaで用いられるMediaWikiの記法では[[...]]で括られる文字列がリンクとして扱われるので、これを正規表現で抽出する。
4. MongoDBに記事のタイトルとその記事が含むリンク先記事を登録する。

ポイントとして、XMLファイルがあまりに大きいので、メモリからの読み込みとDBへの書き込みを並行に実施することでメモリ消費量をおさえています。方法についてはこちらの別記事に記載しているのでご興味があればぜひご一読ください。

展開してリンク抽出プログラムのソースを見る

init.js

const fs = require('fs')
const MongoClient = require('mongodb').MongoClient
const Parser = require('node-xml-stream')

const FILE_PATH = '.\\jawiki-20221201-pages-meta-current.xml'

const DB_URL = 'mongodb://127.0.0.1:27017'
const DB_NAME = 'wikipedia'

const DB_COLLECTION_NAME = 'links'

class Initializer {
    async execute() {
        this.count = 0

        this.mode = {
            page: false,
            title: false,
            text: false,
        }
    
        this.currentPage = {
            title: null,
            text: null,
        }

        this.connector = new MongoClient(DB_URL)
        this.database = this.connector.db(DB_NAME)
        this.collection = this.database.collection(DB_COLLECTION_NAME)
        await this.connector.connect()
        await this.collection.deleteMany({})

        this.parser = new Parser()
        this.parser.on('opentag', async name => await this.onOpenTag(name))
        this.parser.on('closetag', async name => await this.onCloseTag(name))
        this.parser.on('text', async text => await this.onText(text))
        this.parser.on('error', async err => await this.onError(err))
        this.parser.on('finish', async () => await this.onFinish())

        const stream = fs.createReadStream(FILE_PATH)
        stream.pipe(this.parser)
    }

    async onOpenTag(name) {
        if (name === 'page' || name === 'title' || name === 'text') {
            this.mode[name] = true
        }
    }

    async onCloseTag(name) {
        if (name === 'page' || name === 'title' || name === 'text') {
            this.mode[name] = false
        }

        if (name === 'page') {
            this.count++
            try {
                await this.extract(this.currentPage.title, this.currentPage.text, this.count)
            } catch (err) {
                console.error(err)
            }
        }
    }

    async onText(text) {
        if (this.mode.page && this.mode.title) {
            this.currentPage.title = text
        } else if (this.mode.page && this.mode.text) {
            this.currentPage.text = text
        }
    }

    async onError(err) {
        console.log(err)
        await this.onFinish()
    }

    async onFinish() {
        await this.connector.close()
    }

    async extract(title, text, count) {
        const regex = /\[\[(.*?)\]\]/gm
        const matches = text.match(regex)

        if (!matches || matches.length <= 0) {
            console.log(`${this.count}: ${title} => link does not found`)
            return
        }

        const links = []
        for (const match of matches) {
            const extracted = match.substr(2, match.length - 4)
            if (extracted.substr(0, 1) === '#') {
                continue
            }
            const link = extracted.split('|')[0]
            if (link.startsWith(':画像:') || link.startsWith(':ファイル:') || 
                link.startsWith('Image:') || link.startsWith('File:')) {
                continue
            }
            links.push(link)
        }

        const uniqueLinks = [...new Set(links)]

        if (links.length > 0) {
            const doc = {
                title: title,
                links: uniqueLinks,
            }
            await this.collection.insertOne(doc)
        }
        console.log(`${count}: ${title} => ${uniqueLinks.length} link(s) found`)
    }
}

new Initializer().execute().catch(err => console.error(err))

このプログラムを実行開始してから約20時間程度で全記事からリンクを抽出することができました。統計情報は次のような感じです。

• ストレージ容量: 1.86GB
• 抽出した記事の総数: 3,783,582件（ただしリンクを1件も含まない記事を除く）
• 1記事あたりの平均リンク件数: 80～120件（1,000件のサンプリングによる数値）

コレクションにインデックスを張る

それなりな件数のレコードをDBに登録できたので、当たり前ですがインデックスを張っていきます。記事名にインデックスを張らない状態では、記事1件の取得になんと約14秒も掛かりますが、ユニークなインデックスを貼れば走査回数は1回で済むので劇的にレスポンスが改善します。

Before:

After:

収集したリンクから記事を辿る

記事を辿る元データが出来上がったので、あとは記事を辿るプログラムを作るだけです。その探索の方法ですが、辿る必要のある記事数が大分多いので、深さ優先で探索を行いメモリ消費量をおさえながらリンクを辿れるようにしました。

ごく普通な深さ優先探索のプログラムなので特筆すべきポイントはあまりありませんが、一度探索した記事を再度辿らないように辿った記事を覚えておくようにしています。このとき、Setを用いるとハッシュテーブルのように1回のデータ走査でレコードを取得できるため、配列を用いる場合に比べ記事を一度辿ったことがあるかどうかの確認が圧倒的に早く済みます。

展開して検索プログラムのソースを見る

find.js

const fs = require('fs')
const MongoClient = require('mongodb').MongoClient

const DB_URL = 'mongodb://127.0.0.1:27017'
const DB_NAME = 'wikipedia'
const DB_COLLECTION_NAME = 'links'

const MAX_DEPTH = 6

class Finder {
    async execute(args) {
        if (args.length !== 4) {
            console.log('please enter search words')
            return
        } else if (args[2] === args[3]) {
            console.log('please enter two different words')
            return
        }
        
        this.connector = new MongoClient(DB_URL)
        this.database = this.connector.db(DB_NAME)
        this.links = this.database.collection(DB_COLLECTION_NAME)
        await this.connector.connect()
        this.searched = new Set()
        
        console.log(`find ${args[2]} -> ${args[3]}`)

        if (!await this.check(args[2]) || !await this.check(args[3])) {
            console.log('no pages found for the word')
            return
        }

        this.startTime = new Date().getTime()
        const answer = await this.find(args[2], args[3], [ args[2] ])
        this.endTime = new Date().getTime()

        if (answer) {
            console.log(`route has found: ${this.stackToString(answer)}`)
            console.log(`elapsed time: ${this.endTime - this.startTime}ms, searched words: ${this.searched.size}`)
        } else {
            console.log('route does not found')
        }

        process.exit()
    }

    async find(word, goal, stack) {
        if (stack.length > MAX_DEPTH + 1) {
            return
        } else if (this.searched.has(word)) {
            return
        }

        this.searched.add(word)
        const result = await this.links.findOne({ title: word })
        if (!result || !result.links) {
            return
        }

        console.log(`depth: ${stack.length - 1}, find ${this.stackToString(stack)}`)

        for (const link of result.links) {
            const newStack = [...stack]
            newStack.push(link)

            if (link === goal) {
                return newStack
            } else {
                const child = await this.find(link, goal, newStack)
                if (child) {
                    return child
                }
            }
        }
    }

    async check(word) {
        const result = await this.links.findOne({ title: word })
        return !!result
    }

    stackToString(stack) {
        let str = ''
        for (const step of stack) {
            str += step + ' -> '
        }
        return str.substring(0, str.length - 4)
    }
}

new Finder().execute(process.argv).catch(err => console.error(err))

実際に動かしてみる

アドベントカレンダーから六次の隔たりまでをこのプログラムで辿ってみました。20秒程度で見つけられたので、自分の目で辿るよりも圧倒的に早いですね。

route has found: アドベントカレンダー -> クリスマス -> クリスマスプレゼント -> 年末 -> 年末年始 -> 日刊スポーツ新聞社 -> ソーシャル・ネットワーキング・サービス -> 六次の隔たり
elapsed time: 21137ms, searched words: 3638

ただし、深さ優先で探索しているがゆえに総当たりに近い走査を行っていまい、時間効率の悪い結果になることも多いです。アドベントカレンダーから弊社名の記事に探索では、17分弱を要し約43万件もの記事を辿ってしまっています。改善の余地は多いにありそうですね。

route has found: アドベントカレンダー -> Qiita -> エイチーム -> JPX日経中小型株指数 -> アカツキ (ゲーム会社) -> アカツキ (企業) -> ワークスアプリケーションズ -> Works Human Intelligence
elapsed time: 1002573ms, searched words: 434296

まとめ

Node.jsとMongoDBでWikipediaのリンクを辿ってみるの記事でした。業務でNoSQLを触る機会はあまりないので試しに触ってみましたが、中規模なデータセットかつ簡単なユースケースだった今回はほとんどモッサリさを感じることもなく、支持されている理由がなんとなく感じられた気がします。

探索のアルゴリズムについてはシンプルな深さ優先探索を用いたので簡単に実装できましたが、反面パフォーマンスについては難も残っています。被リンクの多い記事であれば短時間で辿れる場合もありますが、被リンクが少ない場合は時間効率があまり良くありません。記事をカテゴリから辿るアプローチや、ある記事はこの記事に辿れる可能性が高い等を探索前に測定しておくヒューリスティックなアプローチ等を実装できれば改善できる可能性も残っているので、機会があれば追加で考えてみようと思います。あるいはこんな方法ならもっと効率の良い探索ができるよ！なんてアイディアをお持ちの方がいたらご提案いただけたら非常に助かります。

最後に、弊社ではバッチで給与計算や帳票出力等で大規模データを処理したり業務改善のためにツールを作成する等の場面で、探索方法やメモリ使用効率について考える場面もあります。私自身もまだまだ勉強中の身なので、今後も手を動かした軌跡や業務中に得た知見があれば筆を執っていきたいと思っています。それらの中で少しでもご興味をお持ちいただけるものが見つかれば幸いです。ご精読ありがとうございました。