DPマッチング

C/C++で　DPマッチングのプログラムを作成しなさい

•任意の2つの文字列を入力とする
•2つの文字列の与え方は自由
•文字列は授業の例題と同様のものとする．ただし任意の文字列できちんと動作すること
•距離（正規化※したもの）と，各文字の編集作業置換・一致，挿入，脱落を出力する
•※2つの文字列のうち⻑い方で割る

•出力例）
•比較元：ABCDEFG
•比較対象：AVCEFZG

•出力例：
•A(一致)V(置換,B→V)C(一致)D(脱落)E(一致)F(一致)Z(挿入)G(一致)
•編集距離：0.429

すみません！
よろしくお願いします！

質問者からの補足コメント

• 

  編集距離＝文字列Aから文字列Bに変換するのに必要な最小の編集作業の回数

    補足日時：2016/07/14 15:23

• 

  アルゴリズムを教えていただけるとありがたいです(T_T)

    補足日時：2016/07/14 19:00

No.6 回答者： siffon9 回答日時： 2016/07/15 19:02

> アルゴリズムを教えていただけるとありがたいです

↓の説明でどうですか？
http://web.tuat.ac.jp/~tuatmcc/contents/monthly/ …

比較元の文字列を縦に、比較対象の文字列を横に置いて最小ルートを求める。
あとはそのルートを辿って
・斜めの移動は、一致
・上への移動は、脱落
・横への移動は、挿入
・ただし、上→横の移動の並び、または、横→上の移動の並びがある場合はまとめて、置換にする。

で、できそうだと思います。

No.5 回答者： Tacosan 回答日時： 2016/07/15 12:34

実質アルゴリズムも出しているような状況で「あとはよろしくおねがいします(笑)」と言われると, こっちとしては苦笑するしかないんだが＞#4.

余談だけど「Levenshtein」で「レーベンシュタイン」はなんか違和感あるなと思って調べてみたらロシア人だったので, ドイツ系ロシア人を仮定して
・発音はドイツ語のまま
・表記はドイツ語からロシア語経由英語着
とみなすのが合理的だなと思ってみたりする. 人名 (や地名など, いわゆる固有名詞) って難しいんだよね.

No.4 回答者： cametan_42 回答日時： 2016/07/15 08:18

ちょっとだけ。

「DPマッチング」っつーより「レーベンシュタイン距離」でしょう、これ。

レーベンシュタイン距離:
https://ja.wikipedia.org/wiki/レーベンシュタイン距離

キーワードっつーか、用語正確に書いた方が良いと思いますよ(もちろんDP = 動的計画法用いてますが)。

そもそも、

> 編集距離＝文字列Aから文字列Bに変換するのに必要な最小の編集作業の回数

って事なんで、「編集距離」(っつーかレーベンシュタイン距離)は正の整数の筈なのに、

> •編集距離：0.429

ってなってるんで食い違ってるんですよね〜(まあ、正規化って書いてるけど)。
こういう「仕様の杜撰さ」ってのはプログラマを混乱させます。
そもそも、動作確認が行いづらい。
幸い、

Python:
http://www.python.jp

って言語にpython-Levenshteinって言う外部ライブラリがあったんで、ちと調べてみたんですが、

>>> import Levenshtein
>>> Levenshtein.distance("ABCDEFG", "AVCEFZG")
3

例に挙がってる"ABCDEFG"と"AVCEFZG"のレーベンシュタイン距離は3です。
そしてここで言う正規化とは、

> 2つの文字列のうち⻑い方で割る

ことらしいんで、結局、

>>> str0 = "ABCDEFG"
>>> str1 = "AVCEFZG"
>>> Levenshtein.distance(str0, str1) / float(max([len(str0), len(str1)]))
0.42857142857142855
>>>

でやっと例示の

> •編集距離：0.429

に一致しますね。

と言うわけで、あとはよろしくおねがいします(笑)。 > Tacosan氏

No.3 回答者： Tacosan 回答日時： 2016/07/15 00:11

「DP」という基本方針は与えられているんだから, この問題をその方針にどう乗せるかを考えることになる.

そして, DP は本質的に「漸化式に従ってひたする計算する」というものだから, (この問題に関していえば) 編集距離に関する漸化式を立てればいい. どのような漸化式が書けるでしょうか?

No.2 回答者： Tacosan 回答日時： 2016/07/14 18:03

OK, 「編集距離」はわかった.

それで, あなたの「質問」はなんですか? 「プログラムを作ってほしい」というのは「質問」ではない, ということは当然理解されてますよね?

No.1 回答者： Tacosan 回答日時： 2016/07/14 14:56

この「編集距離」とやらの数値の根拠がさっぱりわからない. 何をどう計算した結果としてその数値になったんだろうか.

あと, まさかだけど「プログラムを作ってほしい」とかいう寝言を言ってるわけじゃないんだよね?