にゃーにゃー、ではなくて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(", ")}]"
この「末尾は〜で終わる」という辞書もどうやって作るかが問題だよなー。明日聞いてみようーっと。
日本語入力を支える技術 ?変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus)
- 作者: 徳永拓之
- 出版社/メーカー: 技術評論社
- 発売日: 2012/02/08
- メディア: 単行本(ソフトカバー)
- 購入: 14人 クリック: 322回
- この商品を含むブログ (35件) を見る
*1:先生に質問した。。。