Viterbiアルゴリズムによる単語分割を実装してみた - Topics Related to Computers and NLP例によってNLPチュートリアル資料に沿って、Viterbi(ビタビ)アルゴリズムを実装してみた。 参考：単語分割に関するチュートリアル 一言で言うと「分割しうる全ての部分文字列について、その単語分割らしい確率を計算する」アルゴリズムである。 Pythonで実装したものはここ チュートリアルでは各単語に対しての重みがあらかじめ計算された辞書を用いている。 入力文字列をグラフで表すとわかりやすい。各ノードが文字を表し、各エッジが単語を表している。 Viterbiアルゴリズムは以下の2つのステップを踏む。 前向きステップ このステップでは最短経路を動的計画法を用いただけである。この実装では単語ユニグラムに対して重みが割り当てられている。 イメージ図としてはこんな感じ。 図は圧倒的にチュートリアル資料がわかりやすいため、自分で描くのは億劫になる。 ただ、このチュートリアルの資料の前向きステップの説
