Wikipediaで言葉の距離を測る

火曜の三森です。僕は一応自分のブログもやっていますが、こんなに毎週続けるのは初めてです。もはや自由研究と化していますが、前回のWikipediaネタの続きをやってみたいと思います。

前回は、適当に選んだ単語のWikipediaのページにあるキーワードリンクを全て拾ってくる事をやってみました。今回はそのアイディアを使って、単語同士がどれぐらい関係しているのかを調べてみました。「友達の友達が6人先まで行くと世界中の人がつながる」というのは有名な話ですが、単語の場合はどうなっているのか？というのは興味深いところです。方法は単純で、スタートの単語とゴールの単語を決め、その間に必要なジャンプの数を数えます。ただし

・スタート、ゴールの単語にあたるWikipediaのページがなければアウト
・ページ・リクエスト回数の上限を越えてもゴールに着かない、またはどこにも行けなくなったらアウト
・「7月15日」、「1600年」のように数字を含むものはキーワードと見なさない（多過ぎるから）

という設定にしてあります。ジャンプの回数はAPIを叩きすぎないようにMAX_COUNTSで決めてあります。
この条件でいかに単語間距離を稼げるか・・・を対戦してみたら面白いかもしれません。
やり方は、ブログの下に貼ったソースコードをwikisurf.pyで保存し、コマンドラインから

$ ./wikisurf.py 単語1 単語2

または

$ python wikisurf.py 単語1 単語2

のように実行します。すると単語1から単語2に至るまでの距離が分かります。例えば「相対性理論」から「川端康成」までの距離は3ワードでした。

$ ./wikisurf.py 相対性理論 川端康成
No.1 Distance: 0 Word: 相対性理論
No.2 Distance: 1 Word: 翻訳
No.3 Distance: 1 Word: 相対性原理
...
No.243 Distance: 2 Word: ユダヤ人
No.244 Distance: 2 Word: フリッツ・ハーバー
No.245 Distance: 2 Word: コロンビア大学
川端康成 found!
245 words searched.
Distance from 相対性理論 is 3

このように245単語のリンクを調べた結果、コロンビア大学と関係していることが分かりました。また、Graphvizというソフトで読めるDOT言語形式で、単語の経路をグラフ化する機能も付けてみました。このグラフを作るにはコマンドを

$ python wikisurf.py 相対性理論 川端康成 ファイル名.dot

にします。

ただ、これは取得したデータのほんの一部分しか表示していません。全てをグラフ化すると、情報量が多すぎてGraphvizが落ちてしまうからです。このグラフは「川端康成」に「相対性理論」との最短距離と同じ距離で到達するノードだけを表示したものです。実際には「相対性理論」からあらゆるノードへの経路があります。

今回作ったのは、以下のプログラムです。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from xml.dom import minidom
import re, urllib, urllib2, sys, time

def encode(str):
 return urllib.urlencode({"": str})[1:]

def quote(str):
 return str.replace('"', '\\"')

SPECIAL = encode("特別:データ書き出し")
USER_AGENT = "Mozilla/5.0"
MAX_COUNTS = 1000

class Timer:
  def __init__(self):
    self.time = time.time()
  def wait(self, sec):
    diff = time.time() - self.time
    if diff < sec:
      time.sleep(sec - diff)
    self.time = time.time()

class Counter:
  def __init__(self):
    self._count = 0 
  def count(self):
    self._count += 1
    return self._count
  def getCount(self):
    return self._count

TIMER = Timer()
COUNTER = Counter()

class KWQueue:
  def __init__(self):
    self.queue = []
  def enqueue(self, elt):
    self.queue.append(elt) 
  def dequeue(self):
    if len(self.queue):
      elt = self.queue[0]
      del self.queue[0]
      return elt 
    else:
      return None

class KWMap:
  def __init__(self):
    self.map = {}
  def hasKey(self, key):
    return (key in self.map)
  def getMap(self):
    return self.map
  def get(self, key):
    if key in self.map:
      return self.map[key]
    else:
      return None
  def set(self, key, value):
    if key:

class KWLinkMap(KWMap):
  def add(self, key, value):
    if self.hasKey(key) and key: #keyが空でない場合
      self.map[key].add(value)
    else:
      self.map[key] = set([value])

def getWordsForKeyword(keyword):
  opener = urllib2.build_opener()
  opener.addheaders = [('User-agent', USER_AGENT)]

  TIMER.wait(1)
  try:
    data = opener.open("http://ja.wikipedia.org/wiki/" + SPECIAL + "/" + encode(keyword))

    lines = data.read()
    dom = minidom.parseString(lines)
    textDom = dom.getElementsByTagName("text")

    if textDom: #記事がある場合
      textData = textDom[0].firstChild.data
      #print "Text data length: " +  str(len(textData)) 
      return set([w.split("|")[0].split("#")[0].encode("utf-8") for w in KW_PAT.findall(textData)])
  except: #urlアクセスが失敗した場合
    pass

  return set() #記事がない場合

#GraphVizで表示できるdot形式のファイルを作る
def createDotFile(file, map, start, goal):

  def loop():
    key = queue.dequeue()
    if not key:
      return False

    kid = nodeIds[key]

    for word in map[key]:
      if word: #空文字の場合は除く
        if word in nodeIds:
          wid = nodeIds[word]
        else:
          wid = "node" + str(len(nodeIds))
          nodeIds[word] = wid

        file.write("%s -> %s\n" % (wid, kid))
        if (word not in words) and (word != start):
          queue.enqueue(word)
        words.add(word)
   
    if start in map[key]: #このif文を省くとグラフが複雑になりすぎる
      return False

    return True 

  words = set([goal])
  nodeIds = {goal:"node0"}
  queue = KWQueue()
  queue.enqueue(goal)

  file.write("digraph g {\n")
  file.write("graph [rankdir=LR]\n")

  while loop():
    pass

  for key in nodeIds:
    prop = "label=\"%s\"" % (quote(key))
    if key == start:
      prop += " color=red style=filled"
    elif key == goal:
      prop += " color=blue style=filled"
    file.write("%s [%s]\n" % (nodeIds[key], prop))

  file.write("}")


def main():

  def loop():
    word = kwQueue.dequeue()
    if word:
      level = kwLevelMap.get(word)
      if cycle(word, level + 1):
        return False
    else:
      print "A dead end!"
      return False
    return True

  def cycle(searchWord, level):
    print "No.%d Distance: %d Word: %s" % (COUNTER.count(), level-1, searchWord)
    words = getWordsForKeyword(searchWord)
    if COUNTER.getCount() >= MAX_COUNTS:
      print "Reached to maximum access counts %d" % (MAX_COUNTS)
    if goalWord in words:
      kwLevelMap.set(goalWord, level)
      kwLinkMap.add(goalWord, searchWord)
      return True
    else:
      for word in words:
        if word and (not kwLevelMap.hasKey(word)): #空白文字は除外
          kwQueue.enqueue(word)
          kwLevelMap.set(word, level) #最も早くでたlevelを採用
        kwLinkMap.add(word, searchWord)
    return False

  file = None  # dot file

  try:
    if len(sys.argv) > 2:
      startWord = sys.argv[1]
      goalWord = sys.argv[2]
      if len(sys.argv) == 4: # When create dot file
         file = open(sys.argv[3], "w")
    else:
      raise Exception
  except Exception, e:
    if e:
      print e.message
    print "USAGE: " + sys.argv[0] +  " start-word goal-word [dot-file-name]"
    exit()

  kwLevelMap = KWMap()
  kwLinkMap = KWLinkMap()
  kwQueue = KWQueue()

  kwLevelMap.set(startWord, 0)
  kwLinkMap.add(startWord, None)
  kwQueue.enqueue(startWord)

  if len(getWordsForKeyword(goalWord)) == 0:
    print "Cannot find " + goalWord + " on Wikipedia"
  else:
    # main loop
    while loop():
      pass

  if kwLinkMap.hasKey(goalWord):
    print goalWord + " found!"
    print str(COUNTER.getCount()) + " words searched."
    print "Distance from " + startWord + " is " + str(kwLevelMap.get(goalWord))

    map = kwLinkMap.getMap()
    if file:
      createDotFile(file, map, startWord, goalWord)
  else:
    print "You Lose!"


if __name__ == "__main__":
  main()

結局テーマの結論はまだ出ていないのですが、スタートとゴールの両方から攻めていった方がずっと効率的なことに後で気づきました。