Viterbiアルゴリズムによる単語分割を実装してみた

例によってNLPチュートリアル資料に沿って、Viterbi(ビタビ)アルゴリズムを実装してみた。
参考：単語分割に関するチュートリアル

一言で言うと「分割しうる全ての部分文字列について、その単語分割らしい確率を計算する」アルゴリズムである。
Pythonで実装したものはここ

チュートリアルでは各単語に対しての重みがあらかじめ計算された辞書を用いている。
入力文字列をグラフで表すとわかりやすい。各ノードが文字を表し、各エッジが単語を表している。
Viterbiアルゴリズムは以下の2つのステップを踏む。

前向きステップ

このステップでは最短経路を動的計画法を用いただけである。この実装では単語ユニグラムに対して重みが割り当てられている。
イメージ図としてはこんな感じ。
図は圧倒的にチュートリアル資料がわかりやすいため、自分で描くのは億劫になる。
ただ、このチュートリアルの資料の前向きステップの説明スライドにおいて、状態0から状態3へのエッジ（すなわち文字列が全てつながっている単語、例：文字列「り　ん　ご」に対する単語「りんご」。）がないのが少し気になった。

後ろ向きステップ

最短経路を最後のノードから辿るだけ。

大層な名前が付いてはいるが、実は大したことはしていない。
「Viterbiアルゴリズム？ただの動的計画法じゃない？」と思っていたけど、チュートリアル見ないと、実装できなかった。基礎=簡単、とは限らないことを思い知った。

以下計算量に関する簡単な雑記

単語分割における計算量は入力文字数をNとすると、全ての始まるノードと、終わりのノードのペアx（すなわちエッジ）を元に、そのエッジを使った単語分割らしい可能性を計算しているので、O(N^2)である。

ノードを主体にした計算量を考えてみる。以下ノード数をNとする。
各ノードに到達するための最小な重みxは、

各ノードに入ってくるエッジの重み + 入ってきたエッジの反対側のノードにたどり着くまでの重み

である。
各ノードに入ってくるエッジの数はN-1であり（全ての可能性を考慮するため）、一つのノードの重みを計算するにはO(N-1)必要である。
これを各ノードに対して計算するので、O(N) * O(N -1) = O(N^2)と言える。

2013年6月3日追記：
古い記述に対し、ぐちゃぐちゃ言うウザイ奴かもしれませんが、気になるので念のため。
「ビタビアルゴリズムは線形時間」（Mozcソースコード徹底解説より）、とありますが、「探索時(=後ろ向きステップ時)は線形時間だけど、探索のために構築するグラフ構築の計算量はラベル（ノード）数に対して二乗に比例する」と言うのが正しいはず。参考：自然言語処理における系列ラベリング問題のための高速で厳密な漸次的復号化アルゴリズム