動的計画法による2文間の単語の対応付け

動的計画法で2文間の単語の対応付けをしたいのですが，テーブルや漸化式の設定のイメージができません．

具体的には，例えば

x=「彼女は元気です」
y=「彼女なんかは元気よ」

という2文があったとき，それぞれを形態素解析し

xx=[「彼女」，「は」，「元気」，「です」]
yy=[「彼女」，「なんか」，「は」，「元気」，「よ」]

と単語に分割し，動的計画法を使うことで

「彼女」，「は」，「元気」はxxとyyでそのまま対応
「なんか」は追加される（もしくは「は」が「なんかは」に置換される？）
「です」は「よ」に置換される

というような対応付けをしたいのですが，動的計画法を用いる際にどのように設計すればいいのかが解りません．
編集距離で漸化式を作るのか，程度のぼんやりとした考えはあるのですが……．

なにか少しでも良いので知恵をお貸しいただけますでしょうか．

行動規範の内容に同意します

回答1件

ベストアンサー

「距離」や「置き換え」をどう定義するか、また、語順が変わったとき。
例: 今日はいい天気だ。といい天気だ今日は。
をどう扱うか、等と大きな問題はいろいろあると思いますが、それを除いて少しだけ。

まずは、日本語で形態素解析をした後の場合は、「単語」が英語で言う「文字」ひとつに相当すると言えるでしょう。文字の配列(=文字列) の代わりに、単語の配列を使って考えることになります。
その上で普通に編集距離を求めるというのが、まず、1つのアプローチとして考えられます。

個人的には、もう少しいろいろ状況を考えた上で「DP マッチング」を考えたらよいと思います。編集距離は DP マッチングの特別な場合と言ってよく。DP マッチングの手法に対する理解は、助けになると思います。
DP マッチングでは「単語」と「単語」の間に距離のようなものを定義して(例えば、単語の中の文字の一致度を距離とするとか)、また、「語の飛ばし」や「ジャンプ」に対するコストを定義することで、置き換えと考えるか、飛ばしと考えるか…を制御すること等もできます。
ざっくりすぎて分からないかと思いますが、調べてみることをお勧めします。

投稿2015/05/27 09:41