形態素解析器(3) - sileのブログ

前回、形態素解析のステップを大まかに二つに分けた。

入力テキストを形態素列に分割する。一般に、入力テキストは複数の形態素列に変換可能なので、その全てのパターンを列挙する
それらの分割にコスト(優先順位)を付与する。コストが最小の形態素列が、入力テキストの最適な形態素解析結果となる。

今回は、この内の2番目を扱う。

グラフへのコスト付与と、最小コストのパス選択

この段階で行うことを、順を追って簡単に説明する。

まず初めに、前回までの手順に従って、入力テキストから形態素分割グラフを作成する。
入力テキストには前回と同様に(面白くない例だが)「目玉焼きを食べる」を使うことにする。

次に、このグラフのノード(正確にはノードの単語)とエッジ(単語同士の連接)にコストを付与する。
ノードのコストには一番初めに用意した単語辞書(word.csv)内の単語コスト値を、エッジのコストにはこれも初めに用意した連接コスト表(matrix.def)内のコスト値を、単純に当てはめていけば良い*1。
上のグラフにコストを付与すると次のようになる。

最後は、BOSノードからEOSノードまでの(ノード+エッジの)コストが最小のパスを求める。
これには、ダイナミックプログラミングの一種のviterbiアルゴリズム *2というものを使えば良く、入力テキストの長さに対して線形時間で解を求めることができる。
viterbiアルゴリズムについては、以降のソースコードを見て理解してもらうとして、とりあえずそれを適用した結果のグラフだけを載せておく。(何だかすごく大きくなってしまっているが...)

このグラフのEOSから赤色のエッジを逆順に辿っていけば、最小コストのパス=適切な形態素分割、が得られる(赤色のエッジと青色の数字の意味は後述)。
今回の場合は「目玉焼き/を/食べる」が適切な形態素分割となっている。

実装

この段階で書く必要のあるコードはそれほど多くはない。

まずは、後で使う補助関数を定義する。

;; 入力テキストへのマッチ位置がend-posで終わるノードのリストを返す
;; 呼び出し毎にO(n)の処理が必要なので非効率。だけど簡単。
(defun nodes-end-at (node-list end-pos)
  (remove end-pos node-list :key #'node-end :test #'/=))

;; keyを適用した結果が最小となるlist内の要素を返す
;; 既に同じような関数がありそうな気がするが、見つからなかったので自分で作成
(defun select-min (list key)
  (if (null list)
      (values nil nil)
    (let ((min-elem  (car list))
          (min-value (funcall key (car list))))
      (dolist (elem (cdr list))
        (let ((value (funcall key elem)))
          (when (< value min-value)
            (setf min-elem  elem
                  min-value value))))
      (values min-elem min-value))))

;; 例 ;;
> (select-min '((:key 1 :value a) (:key 0 :value b) (:key 3 :value c)) 
              (lambda (x) (getf x :key))) 
--> (:KEY 0 :VALUE B)
    0

次は、品詞の連接コスト表を操作するための関数を定義。

;;; 連接コスト表読込み関数
(defun load-matrix.def (file)
  (with-open-file (in file)
    ;; 連接コスト表の一行目には、表のサイズが書かれている
    (let* ((left-size (read in))  ; 表の縦のサイズ
           (right-size (read in)) ; 表の横のサイズ
           (matrix (make-array (list left-size right-size)
                               :element-type 'fixnum)))
      ;; 二行目以降には、"[左側の品詞のID] [右側の品詞のID] [二つの品詞が連接するコスト]"形式の行が続く
      (dotimes (lft left-size)
        (format t " # ~A~%" lft)  ; 進捗表示
        (dotimes (rgt right-size)
          (read in) (read in)     ; この二つは、lftとrgtと同じ値になるので今回は読み飛ばす
          (let ((cost (read in))) ; コスト値読込み
            (setf (aref matrix lft rgt) cost))))
      matrix)))
;;; 連接コスト表のデータを*matrix*変数に保存
(defparameter *matrix* (load-matrix.def "data/matrix.def"))

;;; 連接コスト取得関数
(defun link-cost (left-word right-word &optional (matrix *matrix*))
  (aref matrix (word-right-id left-word)
               (word-left-id  right-word)))

;; 例 ;;
;; "目玉"の後に"焼き"が続く可能性(コスト)
> (car (get-words "目玉"))
--> ["目玉":名詞,一般,*,*,*,*,目玉,メダマ,メダマ]

> (car (get-words "焼き"))
--> ["焼き":動詞,自立,*,*,五段・カ行イ音便,連用形,焼く,ヤキ,ヤキ]

> (link-cost ** *)
--> -579

最後が、最小コストパス計算を行う関数定義。

;;; viterbiアルゴリズムを使って、最初コストのパスを求める
;;;
;;; コメント中にある部分最小コストとは、特定のノードを終端とした場合の最適パスのコスト。
;;; ノードがEOSの場合は、それが最適な解となる。
;;;
;;; viterbiアルゴリズムは、おおざっぱに云えば
;;;  1] 初期ノード(BOS)の部分最小コストを設定する
;;;  2] 前方に連接するノードの部分最小コスト(計算済み) + 現在のノードのコストを求める
;;;  3] 2で求めたコストを現在のノードの部分最小コストに設定する
;;;  4] 2と3を全てのノードに対して繰り返す  ## 繰り返しは一度で済むのでO(n)
;;;    みたいなことを行うアルゴリズム(だと理解している)。
(defun viterbi (text &optional (*wdic* *wdic*) (*matrix* *matrix*) (*da* *da*))
        ;; 入力テキストからグラフを作成
  (let ((nodes (lattice text)))
    (dolist (cur (cdr nodes)) ; BOS以外の全てのノードを、テキストへのマッチ位置順に処理する
      (multiple-value-bind (prev-node min-cost)
          ;; curノードの前方に連接する全てのノードの中から、
          ;; 以下で計算するコスト(部分最小コスト)が最小になるものを選択する
          ;; # ちなみに、BOSの部分最小コストは0に設定されている
          (select-min (nodes-end-at nodes (node-beg cur))
                      (lambda (prev)
                        ;; 部分最小コストの計算式
                        ;; prevノードの部分最小コスト + curの単語コスト + prevとcurの連接コスト
                        (+ (node-cost prev) 
                           (word-cost (node-word cur))
                           (link-cost (node-word prev) (node-word cur)))))
        (setf (node-cost cur) min-cost     ; curの部分最小コストを設定 ## 上のグラフの青い数字
              (node-prev cur) prev-node))) ; curに最適なprevを設定     ## 上のグラフの赤色エッジ
    ;; 最小コストのパスを返す (EOSノードから辿れるパスが最小コストとなっている)
    (car (last nodes))))

;; 例 ;;
;; 必要な情報は揃っているが、表示が不親切
> (viterbi "目玉焼きを食べる")
--> {8-9 ["EOS":*,*,*,*,*,EOS] {5-8 ["食べる":動詞,自立,*,*,一段,基本形,食べる,タベル,タベル] {4-5 ["を":助詞,格助詞,一般,*,*,*,を,ヲ,ヲ] {0-4 ["目玉焼き":名詞,一般,*,*,*,*,目玉焼き,メダマヤキ,メダマヤキ] {-1-0 ["BOS":*,*,*,*,*,BOS] NIL}}}}}

ただ、これだけだと、最後の例にもあるように結果が分かりにくいので、いくつか補助用の関数を追加で定義する。

;;; 次の二つは分かち書き表示用の関数
(defun extract-surface (node &optional acc)
  (if (null node)
      acc
    (extract-surface (node-prev node) 
                     (cons (word-surface (node-word node)) acc))))

(defun wakati (text &optional (*da* *da*) (*wdic* *wdic*) (*matrix* *matrix*))
  (extract-surface (viterbi text)))

;;; 次の二つは(MeCabで)スタンダードな形態素解析結果表示用の関数
(defun extract-info (node &optional acc)
  (if (null node)
      acc
    (with-slots (prev word) node
      (extract-info prev
                    (cons `(,(word-surface word) ,(word-info word)) acc)))))

(defun parse (text &optional (*da* *da*) (*wdic* *wdic*) (*matrix* *matrix*))
  (extract-info (viterbi text)))


;; 例 ;;
>(wakati "目玉焼きを食べる")
--> ("BOS" "目玉焼き" "を" "食べる" "EOS")

>(format t "~{~A~%~}" (parse "目玉焼きを食べる"))
(BOS *,*,*,*,*,BOS)
(目玉焼き 名詞,一般,*,*,*,*,目玉焼き,メダマヤキ,メダマヤキ)
(を 助詞,格助詞,一般,*,*,*,を,ヲ,ヲ)
(食べる 動詞,自立,*,*,一段,基本形,食べる,タベル,タベル)
(EOS *,*,*,*,*,EOS)
--> NIL

;; 未知語=単語辞書に登録されていない語は、"_"で表示される。
>(wakati "関数型言語ocamlを勉強する")
--> ("BOS" "関数" "型" "言語" "_" "_" "_" "_" "_" "を" "勉強" "する" "EOS")

以上で、当初予定していたタスクは終了。
初めに書いたように未知語処理には対応していないが、それ以外はMeCabと(確認した限りでは)同じ結果を返す形態素解析器を、コメントなどを入れても200行前後で作ることが出来た*3 *4。

もしかしたら、未知語処理と処理速度向上用に、あと二つくらい記事を書くかもしれないが、その辺はまだ未実装なので、やるかやらないかは未定。

*1:単語辞書と連接コスト表の詳細については、MeCabのサイトを参照

*2:負のコスト(weight)を持つ有向グラフの最短パスを求めるアルゴリズムといった方が分かりやすいかもしれない。bellman-ford

*3:ライブラリは行数に含めないという原則(?)に従い、DoubleArray関連のソースコードはカウントから除外している。

*4:処理速度はMeCabに比べてかなり遅い。ただし、その原因は主にcommon-prefix-searchの際に毎回、文字列<->バイト列変換を行っていることと、nodes-end-atが非効率な実装になっていることにある。この2点を改良するだけでも、少なくともMeCabの数倍遅い程度までには持っていけるのではないかと予想している。