プロが教える店舗&オフィスのセキュリティ対策術

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

A 回答 (16件中1~10件)

No.10ですが、最適でないルートを示す場合があったのでパラメータ調整をしました。


その他
・文字をキーから入力するようにした
・ノード情報を構造体にした

--------------------------------
//
// http://web.tuat.ac.jp/~tuatmcc/contents/monthly/ …
//
#include <stdio.h>
#include <string.h>

#define MAX 32

typedef enum Dir_t {Left = 1, LeftLow, Low} Dir;
typedef struct Node_t {
  Dir minDir; // 積算値が最小となる方向
  int minVal; // 最小積算値
  int leftVal; // 左から来た場合の積算値
  int leftLowVal; // 左下から来た場合の積算値
  int lowVal; // 下から来た場合の積算値
} Node;;

void input(char buf[], int size);
int equalChar(char *src, char *dst, int s, int d);
void setMinDir(Node *node, int y, int x);


int main(void){
  char src[MAX + 1], dst[MAX + 1];
  Dir path[2 * MAX + 2];
  Node map[MAX + 1][MAX + 1];
  
  int srcSize, dstSize;
  int x, y, i, val, min, distance;

  // 比較元、対象文字列の先頭にダミーを追加
  src[0] = '.';
  dst[0] = '.';

  // 文字入力
  printf(" 比較元:");
  input(&src[1], MAX);
  printf("比較対象:");
  input(&dst[1], MAX);
  srcSize = strlen(src) - 1;
  dstSize = strlen(dst) - 1;


  // mapの初期化
  map[0][0].minDir = LeftLow;
  map[0][0].leftLowVal = 0;
  map[0][0].minVal = 0;


  // mapの各ノードについて経路の積算値の計算
  for(y = 0; y <= srcSize; y++){
    for(x = 0; x <= dstSize; x++){
      // 積算値が最小となる、このノードへの方向を設定
      setMinDir(&map[y][x], y, x);
      // このノードの最小積算値
      min = map[y][x].minVal;
      
      // 上ノードへの積算
      val = 2;
      if( y < srcSize){
        if( !equalChar(src, dst, y+1, x) ) val *= 5; // ペナルティ
        map[y+1][x].lowVal = min + val;
      }
      // 右上ノードへの積算
      val = 1;
      if( y < srcSize && x < dstSize ){
        if( !equalChar(src, dst, y+1, x+1) ) val *= 10; // ペナルティ
        map[y+1][x+1].leftLowVal = min + val;
      }
      // 右ノードへの積算
      val = 2;
      if( x < dstSize){
        if( !equalChar(src, dst, y, x+1) ) val *= 5; // ペナルティ
        map[y][x+1].leftVal = min + val;
      }
    }
  }


  // 終了地点(map右上)からスタート地点へ最小ルートを辿る
  x = dstSize;
  y = srcSize;
  i = 0;
  while(x > 0 || y > 0){
    path[i] = map[y][x].minDir;
    switch( path[i] ){
    case Left : x--; break;
    case LeftLow : x--; y--; break;
    case Low : y--; break;
    }
    i++;
  }


  // 結果表示
  distance = 0;
  for(i--, x = 0, y = 0; i >=0; i--){
    switch( path[i] ){
    case Left:
      printf("%c(挿入)", dst[x+1]);
      distance++;
      x++;
      break;
    case LeftLow:
      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 Low:
      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;
}



// 左、左下、下の3方向の最小値を示す方向と積算値を
// 保存する。
void setMinDir(Node *node, int y, int x){
  int i;
  Dir d;
  if( y == 0 || x == 0){
    // mapの左辺および底辺のノードは規定値を設定する
    if(x == 0 && y == 0){
      node->minDir = LeftLow;
      node->minVal = node->leftLowVal;
    } else if(x == 0){
      node->minDir = Low;
      node->minVal = node->lowVal;
    } else if(y == 0){
      node->minDir = Left;
      node->minVal = node->leftVal;
    }
  } else {
    // その他のノードは最小積算値の方向を設定する
    if(node->leftVal < node->leftLowVal){
      i = node->leftVal;
      d = Left;
    } else {
      i = node->leftLowVal;
      d = LeftLow;
    }
    if( node->lowVal < i){
      i = node->lowVal;
      d = Low;
    }
    node->minDir = d;
    node->minVal = i;
  }
}

// 文字列入力
void input(char buf[], int size){
  char *p;

  fgets(buf, size, stdin);
  // 改行コード削除
  for(p = buf; *p != '\n'; p++) ;
  *p = '\0';
}
    • good
    • 0

あ, 書き間違えた.



#14 最後の「ただし #13 も~」は「ただし #10 も~」の間違いです.
    • good
    • 0

「逆向きに辿っても同じ値があるじゃないか!」って突っ込まれないようにするには, #10 のように「どこから来たのか」を記録しておくのが常道でしょうなぁ>#13. あと


https://oshiete.goo.ne.jp/qa/9347824.html
にも注意.

ただし #13 も配列を使うのはちょっと本筋ではない. 自然に構造体を使うべきだ.
    • good
    • 0

ああ、ちなみに。

言い忘れてました。

「逆向きに辿っても同じ値があるじゃないか!」

とか思うかもしれませんが、ルール的には

*上、左斜め上、左の値のうち、最小値が左斜め上を含み、なおかつ2つ以上が同値な場合、左斜め上が優先される

ってのがあります。
これはレーベンシュタイン距離を測る行列が、最小値を辿って出来た行列なんで、最小値が複数あって左斜め上が含まれる場合「挿入も脱落も行われなかった」って解釈するのが妥当だ、と言う理由によります。
「DPマッチング」の回答画像13
    • good
    • 0

まず、Wikipediaの疑似コードに従って書いたのが関数LevenshteinDistanceで、これのロジックは基本的にはWikipediaのモノそのまま、です。


あそこの疑似コードはちょっとPascalっぽくって慣れないと読みづらいんですが、あれを基本的にCに移すとこういう風になります。
ちょっとだけの変更点としては

1. Wikipediaでは返り値をi1行i2列行列dのd[i1][d2]の値としてるが、こっちはvoid関数として設計して、eval関数で用意された行列の値を弄くるようにしている。
つまり、コメントの

(* lenStr1+1 行 lenStr2+1 列のテーブル d を用意する *)

って部分はevalが担っていて、LevenshteinDistance自体は単に受け取った行列の値を変更していく、と言うカタチにしています。
(本当は多次元行列を返り値としてやり取りしたかったんですが、Cだとクソメンド臭いです・笑)
2. 文字列操作は、基本的にPascalなんかは「1番目」から弄くりますが、Cだと「0番目」から数えるように設計されてるんで、文字列の参照はC風に直して(つまり-1して)います。

の二点だけ、です。
この部分は本当に、Wikipediaの疑似コードに従って実装していくと、そんなに難しくないです。

なお、C99以降だとmath.hにfmin、fmaxって言う最小値/最大値を返してくれる関数が提供されてるんですが、(恐らく)Visual C++辺りだと仕様に準じて無いだろうな、ってんで敢えてminimum関数とmaximum関数をユーティリティ関数として作っています。

さて、厄介な出力の問題です。
単純には、LevenshteinDistanceと言うアルゴリズムは文字列1の長さと文字列2の長さを受け取ってそれらから行列を作る、ってものなんですね。
ちなみに、例示の"ABCDEFG"と"AVCEFZG"と言う文字列を受け取ると次のような行列を生成するのがLevenshTeinDistanceのアルゴリズムです。

0 1 2 3 4 5 6 7
1 0 1 2 3 4 5 6
2 1 1 2 3 4 5 6
3 2 2 1 2 3 4 5
4 3 3 2 2 3 4 5
5 4 4 3 2 3 4 5
6 5 5 4 3 2 3 4
7 6 6 5 4 3 3 3

縦が"ABCDEFG"、横が"AVCEFZG"に対応しています。
それで・・・まあ、この行列をLevとでも呼びますか。Lev[1, 1]からスタートしてLev[7, 7]にたどり着けば良いわけです。
Lev[7, 7]の値は3、それでこの値が「編集距離」になるわけですね。
だから基本的には「右斜め下」に向かってルートを取ってく、ってカタチになるわけです。そして「斜め移動」の場合、前の値と同じだと「一致」、違うと「置換」、加えて右に移動すると「挿入」、下に移動すると「脱落」です。
一つのマス目からは三方向に移動出来るんですが、その三方向の中で「最小値」を踏んでいきます。
この例示の場合、オチのルートを言ってしまうと、

Lev[1,1](一致) -> Lev[2, 2](置換) -> Lev[3, 3](一致) -> Lev[4, 3](脱落) -> Lev[5, 4](一致) -> Lev[6, 5](一致) -> Lev[6, 6](挿入) -> Lev[7, 7](一致)

になる筈なんですが・・・。
ところが計算でLev[7, 7]の値を返す事自体は全然簡単なんですが、この「ルート」が、今のアルゴリズムに則って見てみてもサッパリ分からないんですよ(笑)。
これ、ちょっと指で辿っていけば分かると思いますが、

Lev[3, 3]からの移動 -> 3方向とも全部2
Lev[6, 5]からの移動 -> 3方向とも全部2

なんで、「ルートを選ぶ」根拠がこの時点で無くなっちまうんですよね。
あら困った。
「編集距離」は出るけど「ルートが分からん」って状態になるわけです(笑)。

んでこういう場合にどうするか、っつーと

「逆向きに辿る」

ってのが一つのやり方ですよね。始点をLev[7, 7]にしてL[0, 0]を目指して逆に辿っていって「編集情報」をピックアップしていく。
その役目を担うのがbacktrace関数です。逆向きで最小のマス目を踏みつつ、その時の「編集作業」を記録していく・・・っつーかここでは文字列に変換していってるわけですが。
まあ、いずれにせよ、evalが持ってる二次元配列を今度はbacktraceが逆向きに走査して、文字列を生成して、最後の出力関数に手渡せば、題意を満たす筈です。
    • good
    • 0

んじゃ、やってみますか。



実は #9 で指摘されてる通り、レーベンシュタイン距離の計算の為の行列を作成した自体で情報は記録されてるんですよね。
ただ、それを取り出すのがちと厄介なんです。

まず、取り敢えずコードを提示します。

// ここから

#include <stdio.h>
#include <stdarg.h>
#include <stddef.h>
#include <string.h>
#include <limits.h>

#define BUF_SIZE 2048

typedef enum key_tag { SUBSTITUTE, MATCH, INSERT, DELETE, DISTANCE } Key;

typedef struct tmp_tag {
 Key keyword;
 char* val;
} Tmp;

char* backtrace(char* str1, char* str2, int d[][strlen(str2)], Tmp msg[], size_t n);
char* eval(char** arg, Tmp msg[], size_t n);
void LevenshteinDistance(char* str1, char* str2, int d[][strlen(str2)]);
char* lookup(Key keyword, Tmp tbl[], size_t n);
int maximum(int count, ...);
int minimum(int count, ...);
char** read(void);

int main(void) {
 Tmp message[] = { { SUBSTITUTE, "%c(置換,%c->%c)" },
          { MATCH, "%c(一致)" },
          { INSERT, "%c(挿入)" },
          { DELETE, "%c(脱落)" },
          { DISTANCE, "編集距離:%.3f" } };
 puts(eval(read(), message, sizeof(message)/sizeof(message[0])));
 return 0;
}

char* backtrace(char* str1, char* str2, int d[][strlen(str2)+1], Tmp msg[], size_t n) {
 static char buffer[BUF_SIZE];
 char str[BUF_SIZE];
 char cpdStr[BUF_SIZE];
 int i1 = strlen(str1)-1;
 int i2 = strlen(str2)-1;
 while (i1 != 0 && i2 != 0) {
  if (d[i1-1][i2] < d[i1][i2-1] && d[i1-1][i2] < d[i1-1][i2-1]) {
   sprintf(str, lookup(DELETE, msg, n), str1[i1-1]);
   i1--;
  }
  else if (d[i1][i2-1] < d[i1-1][i2] && d[i1][i2-1] < d[i1-1][i2-1]) {
   sprintf(str, lookup(INSERT, msg, n), str2[i2-1]);
   i2--;
  }
  else {
   if (d[i1][i2] == d[i1-1][i2-1])
    sprintf(str, lookup(MATCH, msg, n), str1[i1-1]);
   else
    sprintf(str, lookup(SUBSTITUTE, msg, n), str2[i2-1], str1[i1-1], str2[i2-1]);
   i1--;
   i2--;
  }
  sprintf(buffer, "%s%s", str, strcpy(cpdStr, buffer));
 }
 return buffer;
}

char* eval(char** arg, Tmp msg[], size_t n) {
 static char buffer[BUF_SIZE];
 char str[BUF_SIZE];
 size_t lenStr1 = strlen(arg[0]);
 size_t lenStr2 = strlen(arg[1]);
 int d[lenStr1+1][lenStr2+1];
 LevenshteinDistance(arg[0], arg[1], d);
 sprintf(str, lookup(DISTANCE, msg, n), d[lenStr1-1][lenStr2-1]/(double)maximum(2, strlen(arg[0])-1, strlen(arg[1])-1));
 sprintf(buffer, "%s\n%s", backtrace(arg[0], arg[1], d, msg, n), str);
 return buffer;
}

/* Wikipedia 参照 */
void LevenshteinDistance(char* str1, char* str2, int d[][strlen(str2)+1]) {
 size_t lenStr1 = strlen(str1);
 size_t lenStr2 = strlen(str2);
 int i1, i2, cost;
 for (i1 = 0; i1 < lenStr1; i1++)
  d[i1][0] = i1;
 for (i2 = 0; i2 < lenStr2; i2++)
  d[0][i2] = i2;
 for (i1 = 1; i1 < lenStr1; i1++)
  for (i2 = 1; i2 < lenStr2; i2++) {
   cost = (str1[i1-1] == str2[i2-1] ? 0 : 1);
   d[i1][i2] = minimum(3,
             d[i1-1][i2] + 1,
             d[i1][i2-1] + 1,
             d[i1-1][i2-1] + cost
   );
  }
}

char* lookup(Key keyword, Tmp tbl[], size_t n) {
 int i;
 for (i = 0; i < n; i++)
  if (keyword == tbl[i].keyword)
   return tbl[i].val;
 return "";
}

int maximum(int count, ...) {
 va_list args;
 int val = INT_MIN;
 int i, n;

 va_start(args, count);
 for (i = 0; i < count; i++) {
  n = va_arg(args, int);
  if (val < n)
   val = n;
 }
 va_end(args);
 return val;
}

int minimum(int count, ...) {
 va_list args;
 int val = INT_MAX;
 int i, n;

 va_start(args, count);
 for (i = 0; i < count; i++) {
  n = va_arg(args, int);
  if (val > n)
   val = n;
 }
 va_end(args);
 return val;
}

char** read(void) {
 char buf0[BUF_SIZE];
 char buf1[BUF_SIZE];
 static char* string_pair[2];
 fputs("比較元:", stdout);
 fgets(buf0, BUF_SIZE, stdin);
 fputs("比較対象:", stdout);
 fgets(buf1, BUF_SIZE, stdin);
 string_pair[0] = buf0;
 string_pair[1] = buf1;
 return string_pair;
}

// ここまで
    • good
    • 0

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;
}
    • good
    • 1

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

    • good
    • 0

No.6です。


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

> ・斜めの移動は、一致

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

でした。
    • good
    • 0

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

そうですね、難しいです。
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!