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.1 回答者： Tacosan 回答日時： 2016/07/14 14:56

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

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

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

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

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

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

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

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

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.5 回答者： Tacosan 回答日時： 2016/07/15 12:34

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

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

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

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

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

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

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

No.7 回答者： cametan_42 回答日時： 2016/07/16 00:36

> こっちとしては苦笑するしかないんだが

まあ、一応、この問題は既にTacosan氏の獲物なんで(笑)。

> 実質アルゴリズムも出しているような状況で

まあそれはそうなんですが(笑)、一方疑似コード読めるか読めないかってのも慣れですしねぇ。
Wikipediaで採用してる疑似コードだとちょっとPascalっぽいんで、Pascal知らないと読みづらいかもしれません。
加えると、この問題が厄介なのは、むしろ出力なんですよね。アルゴリズム自体を記述する事はそんなに難しくないでしょうが、

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

出力弄くるのが相当厄介な気がします。
何せ問題のrequirementが

•2つの文字列の与え方は自由

なんで。
どういう風に「編集情報」を記録しておいて、「任意の」文字列に落としこむのか・・・・・。
この部分が一番難しい(笑)。

割にプログラミングに慣れてない人が混乱するのが、

「何がアルゴリズムの部分なのか」
「何がアルゴリズムと関係が無い部分(この問題の場合は出力)なのか」

ってのの切り分けが出来てない部分で、多分この投稿者もそうなんじゃないかな、って思っています。
(ホント、この問題の最大の難関は「レーベンシュタイン距離」のアルゴリズムじゃなくって、こっちの「出力」ですよ・笑)
特にね〜、C言語だと、これがなかなか文字列を自在に操るのが難しい。

っつーか、Cには文字列が無いもの(笑)。

こんなクソメンドくせぇ宿題出した学校は万死に値するでしょう(笑)。

ってなわけで逃げます(笑)。

> 人名 (や地名など, いわゆる固有名詞) って難しいんだよね.

そうですね、難しいです。

No.8 回答者： siffon9 回答日時： 2016/07/16 05:24

No.6です。

すみません、置換の部分が間違っていました。

> ・斜めの移動は、一致

・斜め移動は、比較元および比較対象の、移動先の座標の文字が同じなら一致、異なるなら、置換

でした。

No.9 回答者： Tacosan 回答日時： 2016/07/17 00:36

うん? 編集距離を DP で計算する時点で「編集情報」も表にして覚えとくだけですよね＞#7. 出力は再帰でどうとでもなるし.

No.10 回答者： siffon9 回答日時： 2016/07/17 09:55

No.6, 8です。

もう見てないかもしれませんが、No.6のリンク先の説明を参考に自分の勉強がてら書いてみました。
-------------------
//
// http://web.tuat.ac.jp/~tuatmcc/contents/monthly/ …
//
#include <stdio.h>
#include <string.h>

#define MAX 32

int equalChar(char *src, char *dst, int s, int d);
void checkMinDir(int a[][MAX+1][4], int y, int x);


int main(void){
char src[MAX + 1], dst[MAX + 1];
int path[2 * MAX + 2];

// 第1要素：比較元文字列インデックス（0:ダミー）
// 第2要素：比較元文字列インデックス（0:ダミー）
// 第3要素
// 　0:最小値ルートの方向(1-3)
// 　1:左からの積算値
// 　2:左下からの積算値
// 　3:下からの積算値
int map[MAX + 1][MAX + 1][4] = {0};


// 比較元文字列
const char *srcStr = "ABCDEFG";
// 比較対象文字列
const char *dstStr = "AVCEFZG";


int srcSize, dstSize;
int x, y, i, val, min, distance;

// 比較元、対象文字列の先頭にダミーを追加
src[0] = '.';
strcpy(&src[1], srcStr);
dst[0] = '.';
strcpy(&dst[1], dstStr);
// 比較元、対象文字列長取得
srcSize = strlen(srcStr);
dstSize = strlen(dstStr);


// mapの初期化
for(i = 0; i <= srcSize; i++){
map[i][0][1] = 100;
map[i][0][2] = 100;
}
for(i = 0; i <= dstSize; i++){
map[0][i][2] = 100;
map[0][i][3] = 100;
}

// mapの各ノードの計算
for(y = 0; y <= srcSize; y++){
for(x = 0; x <= dstSize; x++){
// 最小値の方向を取得
checkMinDir(map, y, x);
// このノードの最小積算値
min = map[y][x][ map[y][x][0] ];

// 上ノードへの積算
val = 10;
if( y < srcSize){
if( !equalChar(src, dst, y+1, x) ) val *= 10;
map[y+1][x][3] = min + val;
}
// 右上ノードへの積算
val = 14;
if( y < srcSize && x < dstSize ){
if( !equalChar(src, dst, y+1, x+1) ) val *= 10;
map[y+1][x+1][2] = min + val;
}
// 右ノードへの積算
val = 10;
if( x < dstSize){
if( !equalChar(src, dst, y, x+1) ) val *= 10;
map[y][x+1][1] = min + val;
}
}
}


// 文字列末尾（map右上）から最小ルートを辿る
x = dstSize;
y = srcSize;
i = 0;
while(x > 0 || y > 0){
path[i] = map[y][x][0];
switch( path[i] ){
case 1: x -= 1; break;
case 2: x -= 1; y -= 1; break;
case 3: y -= 1; break;
}
i++;


}
path[i] = 0;


// 結果表示
printf("　比較元：%s\n", srcStr);
printf("比較対象：%s\n", dstStr);

distance = 0;
for(i--, x = 0, y = 0; i >=0; i--){
switch( path[i] ){
case 1:
printf("%c(挿入)", dst[x+1]);
distance++;
x++;
break;
case 2:
if(equalChar(src, dst, y+1, x+1))
printf("%c(一致)", src[y+1]);
else{
printf("%c(置換,%c→%c)", dst[x+1], src[y+1], dst[x+1]);
distance++;
}
x++;
y++;
break;
case 3:
printf("%c(脱落)",src[y+1]);
distance++;
y++;
break;
}
}
printf("\n");
// printf("編集回数：%d\n", distance);
printf("編集距離：%.3f\n", distance/(double)(srcSize>dstSize?srcSize:dstSize) );

return 0;
}


// 比較元と比較対象の指定位置の文字が一致するか否か
int equalChar(char *src, char *dst, int s, int d){
if(src[s] == dst[d]) return -1;
return 0;
}


// 左(1)、左下(2)、下(3)の3方向の最小値を示す方向を記録する
void checkMinDir(int a[][MAX + 1][4], int y, int x){
int i;
i = a[y][x][1]<a[y][x][2]?1:2;
i = a[y][x][i]<a[y][x][3]?i:3;
a[y][x][0] = i;
if(x == 0) a[y][x][0] = 3;
if(y == 0) a[y][x][0] = 1;
if(x == 0 && y == 0) a[y][x][0] = 2;
}