異なる文字列のマッチングを、DPマッチングを用いて行うプログラム

プログラミング初心者です。C言語でこの問題を行いたいです。
異なる文字列のマッチングを、DPマッチングを用いて行うプログラムという課題が出ているのですが初心者でどのような考え方があるのかすらわからない状況です。出力の仕方としてはJAPAN JPANと入力するとD 削除誤りやJAPAN JAEPANと入力するとI 挿入誤りなどとしたいです。考え方だけでももしよければわかる方教えていただきたいです、よろしくお願いします。
(なんとなく横を正解の文字列縦をテキスト認識結果として表を作り同じ文字、異なる文字で判断を付けるやり方があると聞きました。)

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

• おそらくレーベンシュタイン距離で考えると思います。c++とかJavaでも全然大丈夫です

  No.2の回答に寄せられた補足コメントです。 補足日時：2021/05/24 03:43

• 

  cametanさんのプログラムはうまく作動できていたのですが私がやりたいこととしてはプログラムを実行した後に正しい文字JAPAN、微妙に違う文字JAPNなどと入力すると挿入誤り Iなどとしたいということです。同じ文字なら1違う文字なら2を返す表をつくりました
  
  J A P A N
  J 1 2 2 2 2
  A2 1 2 1 2
  P2 2 1 2 2
  N2 2 2 2 1
  
  わかりにくいかもしれませんが課題のヒントをもらったので問題説明のために書かせていただきます。この表の対角線上の斜め移動→1なら正解、2ならS置換誤り
  この対角線で進む経路を考えて、横移動(JAPNのPとJAPANのPの1から
  JAPNのPとJAPANのAの2に行くこと)だとD排除誤り、縦移動だとI挿入誤りとかんがえて判断したいということです。長く時間がかかってしまいましたね（笑）
  質問の仕方が悪く申し訳なかったです

    補足日時：2021/05/27 04:38

• 

  すみません表のことは忘れてくださいすみません。やりたいことを画像で書いてみました。よろしくお願いします。

  
    補足日時：2021/05/27 15:12

• 

  JAPANを正解とした時、JPAN,JAAPAN,などでそのまま順にマッチングすると具合が悪い
  例えば
  JAPAN　　　　　　　　　　
  JPAN
  〇××××　　　頭しかあっておらずそれ以外は×
  そのため
  JAPAN　　　　　　　　　　
  JPAN D:削除誤り
  D
  
  JAPAN
  JAAPAN 　I: 挿入誤り
  　I
  
  JAPAN
  JA AP　　　S: 置換誤り
  　D　S
  のようにしたい
  誰が見ても「なるほど」と言う2つの文字列をマッチングするということです。
  
  
  
  
  ヒントを画像に添付しました。ヒントを見れば
  kitten、sittingみたいな2つの文字列の場合もたぶんわかると思います。いろいろと手間をかけさせて申し訳ないです。

  
  No.8の回答に寄せられた補足コメントです。 補足日時：2021/05/27 23:41

• 経路の問題なのでどっちでもいいのですが今回は3でお願いします。画像を添付しました。

  
  No.9の回答に寄せられた補足コメントです。 補足日時：2021/05/28 00:10

• この問題は最適な経路を通る要するになるべく1をたくさん通るように進むという問題です。自分が書いた経路の合計値は９、もし(P,P)＝(2,3)に進むとそのあと(3,3),(4,3)と進むしかなくなり合計値は12となり最短距離ではないんです。
  cametanさんの問題としても(2,2)→(2,3)→(3,4)と進めば最短距離になります。問題は斜めにも進めて横縦も使い最短距離を求めます。言い方が悪かったのだと思いますが3でも踏むことができます。

  No.10の回答に寄せられた補足コメントです。 補足日時：2021/05/28 01:12

• ヒントでは直感的に最適と思われる経路と書いてあったのでじゃあこれはヒントじゃなかったのか...
  ヒント以外の方法ってないですかね？
  この記事とか結構似ていると思うのですが
  レーベンシュタイン距離を完全に理解した！(c++編)
  https://qiita.com/odenmonster/items/db443d580878 …
  記事ではレーベンシュタイン距離を求めているようですがこれを自分が言っていた表示にすることはできないですか？

  No.11の回答に寄せられた補足コメントです。 補足日時：2021/05/28 02:06

• 画像の意味がよくわかっていないのですが表の数字は何でしょうか？あとたくさん出てきている～誤りの奴は何を表しているのですか？

  
  No.12の回答に寄せられた補足コメントです。 補足日時：2021/05/28 03:29

No.4 回答者： cametan_42 回答日時： 2021/05/26 04:04

> エラー C2131 式は定数に評価されませんでした というエラーが起こりました。

少し調べたところ配列の中に変数は使えないということだったのですが何か解決方法はないのでしょうか？

うーん、C言語がどーの、っつーよりVisual C++がどーの、ってカンジっぽいエラーなんだけど。
いずれにせよ、コンパイラはMicrosoftのVisual Studioのブツでしょ？エラー C2131ってのはCと言うよりC++のエラーっぽいんだよなぁ。
試しに19行目を

int* d = new int[lenStr1 + 1][lenStr2 + 1];

と書き換えてみてください。
Cとしては間違いなんだけど、Visual Studioだと本質的にはCコンパイラじゃなくってC++コンパイラを使ってる状態なので、これで上手く動くかも。

No.3 回答者： cametan_42 回答日時： 2021/05/24 21:40

> c++とかJavaでも全然大丈夫です

各言語で「実装しやすさのレベル」ってのがあるんですよ。
実はC++もJavaも大して実装しやすくはありません。

レーベンシュタイン距離の実装levは、単純に言うと、文字列aとbがあったとして、また文字列a、 bの先頭以外の部分をtail(a)、tail(b)と表現するとして(例えば文字列"JAPAN"のtailは"APAN"である)、

1. 文字列bの長さが0の時 => 文字列aの長さを返す(ここが削除誤りを表す)
2. 文字列aの長さが0の時 => 文字列bの長さを返す(ここが挿入誤りを表す)
3. 文字列aの先頭の文字と文字列bの先頭の文字が一致した時 => lev(tail(a), tail(b))を呼び出す
4. その他の場合、1 + min(lev(tail(a), b), lev(a, tail(b)), lev(tail(a), tail(b))を返す。ここでminは与えられた引数の内、最小の値を返す関数とする。

と言う単純なアルゴリズムに支えられます。
やるこたぁ単純なんだけど、この流れ見ると分かるんですが、再帰的定義なんですよね。
つまり、プログラミング言語が「再帰的定義のサポートが得意」な方が良い、と言う事が一つ。この辺、実は(C++もそこまで得意じゃないにせよ)Javaがあまり得意じゃないのです。
そして手順4.が至極厄介なのです。結局、

1 + min(lev(tail(a), b), lev(a, tail(b)), lev(tail(a), tail(b))

ってのが厄介な計算で、再帰を3つ呼び出しつつ、そこでの最小値を求めたヤツに1を加算せねばならない。フツーのプログラミング言語を使ったプログラミングだとここの計算コストが物凄くかかるのです。
まぁ、この辺面倒なんで、遅延評価を使える言語、例えばHaskellとかOCamlとか、Cの言語族で言うと良く知らんけどC#を使うとか(C++でも外部ライブラリでStreamsと言うライブラリがある模様 => https://jscheiny.github.io/Streams/ )。
あるいはメモ化

メモ化:
https://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%A2 …

とか、プログラミングする際に工夫して上記のややこしい再帰の計算コストを低減するようにするわけです。

あるいは、ロジックは再帰でシンプルなんだけど、敢えて人間コンパイラになってみる。つまり前述の

「共通語度」を用いたGAJのクラスター分析:
http://repository.tufs.ac.jp/bitstream/10108/514 …

レーベンシュタイン距離:
https://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC …

で紹介されてる疑似コードをCに直してみる、と。
これは「プログラムのやり方」自体は紹介されてるわけで、要は貴方に読解力っつーか、Cのプログラムへの翻訳能力が試されてる、ってわけですよ。
例えばWikipedia版だと、Cで翻訳すれば多分次のようになる。

/* ここから */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare_int(const void *a, const void *b) {
　return *(int*)a - *(int*)b;
}

int minimum(int n0, int n1, int n2) {
　int d[] = {n0, n1, n2};
　qsort(d, 3, sizeof(int), compare_int);
　return d[0];
}

int LevenshteinDistance(char str1[], char str2[]) {
　int cost;
　int lenStr1 = strlen(str1);
　int lenStr2 = strlen(str2);
　int d[lenStr1 + 1][lenStr2 + 1];

　for (int i1 = 0; i1 <= lenStr1; i1++) { d[i1][0] = i1; }
　for (int i2 = 0; i2 <= lenStr2; i2++) { d[0][i2] = i2; }

　for (int i1 = 1; i1 <= lenStr1; i1++) {
　　for (int i2 = 1; i2 <= lenStr2; i2++) {
　　　cost = (str1[i1] == str2[i2]) ? 0 : 1;
　　　d[i1][i2] = minimum(
　　　　　　　　　　　　　d[i1-1][i2] + 1,　　 /* 文字の削除 */
　　　　　　　　　　　　　d[i1][i2-1] + 1,　　 /* 文字の挿入 */
　　　　　　　　　　　　　d[i1-1][i2-1] + cost /* 文字の置換 */
　　　　　　　　　　　　　);
　　}
　}
　return d[lenStr1][lenStr2];
}

int main(void) {
　int p = LevenshteinDistance("JAPAN", "JPAN");
　printf("%d ", p);
　printf("\n");
　return EXIT_SUCCESS;
}

/* ここまで */

Wikipediaの疑似コードと比較してください。
まぁ、Cだとminimum関数なんかも無いんで、自作してやらなアカン辺りがメンド臭いわけですけどね。

この回答へのお礼

プログラムまでありがとうございます！！
実行してみたのですが19行目のint d[lenStr1 + 1][lenStr2 + 1];の部分で
エラー C2131 式は定数に評価されませんでした というエラーが起こりました。少し調べたところ配列の中に変数は使えないということだったのですが何か解決方法はないのでしょうか？

お礼日時：2021/05/26 02:16

No.2 回答者： cametan_42 回答日時： 2021/05/24 03:26

うーん、多分向かう先はこれなんじゃないかなぁ。

共通語度」を用いたGAJのクラスター分析:
http://repository.tufs.ac.jp/bitstream/10108/514 …

多分最終的にはレーベンシュタイン距離、ってヤツに向かうと思うんだけど。

実はアルゴリズム的にはそんなに難しくないんだけど、厄介なのは「C言語を使う」って辺り。
C使わなければ割に簡単に実装出来るんだけど、「Cが故に」メンド臭くなる典型例かもしんない。

例えば、Lisp言語族のRacket

Racket:
https://racket-lang.org/

なんかだと

# ここから

(require srfi/41)

(define (lev a b)
　(define string->stream (compose list->stream string->list))
　(define (lev$ a b)
　　(cond ((stream-null? b) (stream-length a))
　　　　((stream-null? a) (stream-length b))
　　　　((char=? (stream-car a) (stream-car b))
　　　　　(lev$ (stream-cdr a) (stream-cdr b)))
　　　　(else (+ 1 (min (lev$ (stream-cdr a) b)
　　　　　　　　　　　(lev$ a (stream-cdr b))
　　　　　　　　　　　(lev$ (stream-cdr a) (stream-cdr b)))))))
　(lev$ (string->stream a) (string->stream b)))

# ここまで

こう簡単に実装出来るんだけど、Cだとリンク先の疑似コードか、あるいはWikipediaの

https://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC …

に書かれてる疑似コードをマジメに実装するしか無いんじゃないかしらん。

No.1 回答者： Tacosan 回答日時： 2021/05/23 17:34

「DPマッチングを用いて」って書いているくらいだから, 素直にそのまますればいい.