そろそろChaIMEについて一言いっておくか

　2月は割とガンガンと開発をしてきたのだが、3月に入ってさすがにエネルギーが切れてきたので、一旦、気分転換にエントリに書いてみることにする。
　ChaIMEというのは主に研究目的のかな漢字変換エンジンである。奈良先の小町さん(id:mamoruk)がメインで開発していて、自分もここしばらくはアクティブに開発している。こちらでデモを試すことができる。ChaIMEの特徴はひたすらに統計情報で変換をするところなのだが、今回はそういった話ではなく、もうちょっと一般的なかな漢字変換についての話をダラダラと書いてみようと思う。
　デモを見て分かる通り、今までのChaIMEはステートレスで、ひらがな列を入力に対してそれっぽい変換候補を複数出力してさぁ選べ、という形だった。文節境界を変更したり、文節毎に候補を出すことはできない。これは単に実装コストの問題で、研究用途で実験をする際には文節境界を変更してどうたらこうたらと言うのはあまりやらないので後回しになっていた。
　実験には使わないとはいえ、実用的にはやっぱり文節毎に変換候補を出したりできた方がうれしいので、最近そこら辺の機能を実装してみた。ので、今回は文節区切りとかの話しについて書く。
　誤変換を訂正する際の操作には、変換候補の入れ替えと、文節区切りの変更の2種類がある。変換候補の入れ替えは2番目以降の変換候補を出せば良いだけの話であるが、もう一つの操作である文節区切りの変更というのは、実際にはどういう風にして実現すればいいのか。知ってしまえば当たり前の話なのだが、知らないと意外とわからないものかもしれないので、ちょっと考えてみるとおもしろいと思う。
　あまり引っ張る話でもないのでさっさと答えを書いてしまうと、文節区切りを変更しての再解析は、「ここで文節を切れ」「ここでは文節を切るな」という2種類の制約をつけた上で変換を行えばよい。最小コスト系（最近は大体これだと思ってよい）のかな漢字変換アルゴリズムでは、ひらがな列に対応して考えうる漢字列の中でもっともコストが小さくなるものを選択してくるのだが、制約をつけるという事は、考えうる漢字列の中で、さらに制約を満たすものの中からもっともコストが小さくなるものを選ぶという話になる。具体的には、辞書引きを行う時点で、制約を満たさないかな列に対しては辞書引きを行わなければよい。
　最小コストという話をちょっとしたので、さらにそちらの方も少し掘り下げてみる。最もコストが小さい漢字列を選択するという問題は、コストモデルが複雑になってしまうと、実用的な時間で解くことは難しい。そこで、計算量を落とすために、コストをノードコストとパスコストの2つのみに絞った場合を考えてみよう。前者は単語と単語の間の接続が強いほど低くなるコストであり、後者は単語の出現確率が高いほど低くなるコストである。ここまでモデルを単純化しても、ナイーブな方法では変換文字列の長さの指数乗の時間がかかってしまう。指数乗では使い物にならない。しかし、ちょっと工夫をすると、計算時間を劇的に短くする事ができるのである。ちょっとした工夫とはあるノードにたどり着くまでの最小のコストを表に記録していくというもので、これだけで変換文字列の長さに比例する計算時間で問題を解く事ができる。小さな問題の解を使って大きな問題の解を求めているわけなのでこれは動的計画法の一種であるが、Viterbi Algorithmという大仰な名前で呼ばれている。
　Viterbi Algorithmで求まるのは最もコストが低い経路だけで、2番目、3番目の変換候補はビタビだけでは求めることができない。こういう、それっぽい上位N件の結果をよくN-best解と呼ぶが、N-bestを出すためにはViterbiアルゴリズムで前からコストをつけた後に、後ろからA*サーチをすれば良い。
　普通はA*サーチというと最短経路を求めるためのアルゴリズムであって、N-bestを求めるためのものとしては扱われていないのだが、ゴールまでたどり着いた後にも優先度付きキューから次のノードを取り出して探索を続けることで、N-best解を好きなだけ求めることができる。
　実際のところ、前向きViterbi + 後ろ向きA*などという面倒くさいやり方ではなく、いきなり前向きA*を走らせるだけでもN-best解は求められるのだが、これは効率的な手法であるとは言えない。A*探索においては現在ノードからゴールまでの推定コストが実際のコスト以下になっている事を保証する必要があるが、これは難しい問題で、どうしても推定値が低くなりすぎてしまう。そうすると、スタートに近いノードの展開が非常に多くなってしまい、計算量が膨らんでしまうので遅くなってしまう。前向きViterbiでゴールまでのコストを正確につけておけば、後ろ向きA*の際に効率的に探索を進めることができる。
　数日前までは厳密なコストがわからなければ正しいN-best解を出力できない気がしていたが、よく考えてみると、別にそんなことはなく、普通にA*の条件さえ守っていれば、N-best解は出力できる。前向きにViterbiでコストづけを行うのはあくまでも高速化のためである。
　明日以降気力が持てば、実際に変換コンテキストを実装するにあたってどういう点が面倒くさかったのか、といった苦労話も書いてみるよ。