猫はうろうろ - yasuhisa's blog

にゃーにゃー、ではなくてw。情報学類(今名前変わったんだっけか)のほうで出ている自然言語処理の講義ほうで、形態素解析をするための「wikipedia:ビタビアルゴリズム(Viterbi algorithm)」というのを勉強しました(GWの前くらいに)。なんか全然分かっていなかったので、書いてみることにしました。アルゴリズムの種類としては動的計画法(Dynamic Programming)に入るので、アルゴリズムデザインのほうの勉強にもなるし(という合理化)。

「猫はうろうろ」という文字列は「猫、はう、ろう、ろ」や「猫、は、うろうろ」など様々な形で形態素解析することができます。これをある基準で分解したいのですが、ここでは一番単純そうな単語数最小法と呼ばれる方法でやります。

このやり方で「猫はうろうろ」と「家におくりました」を形態素解析すると結果は次のようになります。

/tmp% ruby viterbi.rb
N(x) = [0, 1, 2, 2, 3, 3, 3]
W(x) = [, 猫, は, はう, ろ, ろう, うろうろ]
w_prime [うろうろ, は, 猫]
left [2, 1, 0]
最終的な形態素解析の結果 -> [猫, は, うろうろ]
==================================================
N(x) = [0, 1, 2, 3, 4, 2, 3, 3, 3]
W(x) = [, 家, に, お, く, におくり, ま, まし, ました]
w_prime [ました, におくり, 家]
left [5, 1, 0]
最終的な形態素解析の結果 -> [家, におくり, ました]

「猫はうろうろ」のほうはきちんと形態素解析できていますが、「家におくりました」のほうはきちんとできていません。そこで「この品詞があの品詞と連結するコストは…」というのも考えようとすると、それはコスト最小法を用いたBiterbiアルゴリズムとなります(いくつ前を見るかで、複雑さが変わってきます。一つ前、二つ前とか)。が、それは次回以降ということで。

コード

アルゴリズムを勉強してて最初分からなかったところとして、「〜で終わる単語の辞書があると仮定して」というのを忘れていた、というのがありますw*1。というわけで時前で

back_dic = {
  "猫" => ["猫"],
  "は" => ["は"],
  "う" => ["う", "はう", "ろう"],
  "ろ" => ["ろ", "うろうろ"]
}

こんな感じの辞書をハッシュで用意しました。実用段階になるとこれを機械的に作る&高速に引けるというのが重要になってきますが、その方法については明日の講義でやるようです(Patrica木と呼ばれるものを使うそう)。

# -*- coding: utf-8 -*-

class String
  def japanse_length
    self.split(//u).length 
  end
end

def viterbi(sl, back_dic)
  nx = []
  wx = []
  l = sl.japanse_length

  # initialization
  nx[0] = 0
  (1..l).each{|i|
    nx[i] = 1.0/0
  }

  (1..l).each{|x|
    min = 1.0/0
    argmin = ""
    back_dic[sl.split(//u)[x-1]].each{|w| # 位置xで終わる単語w
      i = x - w.japanse_length
      if sl.split(//u)[i..x-1].join("") == w
        min = nx[i] + 1
        argmin = w
      end
    }
    nx[x] = min
    wx[x] = argmin
  }

  puts "N(x) = [#{nx.join(", ")}]"
  puts "W(x) = [#{wx.join(", ")}]"

  w_prime = []
  left = []

  w_prime[0] = wx[l]
  left[0] = l - wx[l].japanse_length

  # backtrack
  m = nx[wx.length-1]

  (1..m-1).each{|k|
    w_prime[k] = wx[left[k-1]]
    left[k] = left[k-1] - w_prime[k].japanse_length
  }
  puts "w_prime [#{w_prime.join(", ")}]"
  puts "left [#{left.join(", ")}]"

  return w_prime.reverse
end

sl = "猫はうろうろ"
back_dic = {
  "猫" => ["猫"],
  "は" => ["は"],
  "う" => ["う", "はう", "ろう"],
  "ろ" => ["ろ", "うろうろ"]
}

puts "最終的な形態素解析の結果 -> [#{viterbi(sl, back_dic).join(", ")}]"

puts "=" * 50

sl = "家におくりました"
back_dic = {
  "家" => ["家"],
  "に" => ["に"],
  "お" => ["お"],
  "く" => ["く"],
  "り" => ["おくり","におくり"],
  "ま" => ["ま"],
  "し" => ["まし"],
  "た" => ["た","ました"],
}

puts "最終的な形態素解析の結果 -> [#{viterbi(sl, back_dic).join(", ")}]"