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

Question

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

cametan_42 · Accepted Answer

> 画像の意味がよくわかっていないのですが表の数字は何でしょうか？それがレーベンシュタイン距離、です。例えばJAPANとJAAPだと一文字目(J)は編集距離が0だ、って事ですね。最終的にJAPANとJAAPの編集距離は2となります。JAAPを「なんかして」も一回「なんかすれば」JAPANと一致する。ただし、その「何か」が全く分からんのですよねぇ。 > たくさん出てきている～誤りの奴は何を表しているのですか？レーベンシュタイン距離を計算する為の表を作る際に行う「作業」ですよ。もうちょっとわかりやすくするなら、 /* ここから */ #include #include #include int minimum(int n0, int n1, int n2) { 　if (n0 <= n1 && n0 <= n2) { 　　puts("D: 削除"); 　　return n0; 　} else if (n1 <= n0 && n1 <= n2) { 　　puts("I: 挿入"); 　　return n1; 　} else { 　　puts("S: 置換/据置"); 　　return n2; 　} } int LevenshteinDistance(char str1[], char str2[]) { 　int cost, val; 　int lenStr1 = strlen(str1); 　int lenStr2 = strlen(str2); 　int* d = malloc(sizeof(int) * (lenStr1 + 1) * (lenStr2 + 1)); 　for (int i1 = 0; i1 <= lenStr1; i1++) { d[i1 * lenStr1] = i1; } 　for (int i2 = 0; i2 <= lenStr2; i2++) { d[i2] = i2; } 　for (int i1 = 1; i1 <= lenStr1; i1++) { 　　for (int i2 = 1; i2 <= lenStr2; i2++) { 　　　cost = (str1[i1] == str2[i2]) ? 0 : 1; 　　　printf("(%d, %d) => ", i1, i2); 　　　d[i1 * lenStr1 + i2] = minimum( 　　　　　　　　　　　　　　　　　　d[(i1 - 1) * lenStr1 + i2] + 1, 　　　　　　　　　　　　　　　　　　d[i1 * lenStr1 + i2 - 1] + 1, 　　　　　　　　　　　　　　　　　　d[(i1 - 1) * lenStr1 + i2 - 1] + cost 　　　　　　　　　　　　　　　　　　); 　　} 　} 　/* 出力用 */ 　printf(" "); /* 空白四文字分 */ 　for (int i = 0; i < lenStr2; i++) { printf("%c ", str2[i]); } 　printf(" "); 　for (int i1 = 0; i1 <= lenStr1; i1++) { 　　if (i1 == 0) { printf(" "); } else { printf("%c ", str1[i1-1]); } 　　　for (int i2 = 0; i2 <= lenStr2; i2++) { 　　　　printf("%d ", d[i1 * lenStr1 + i2]); 　　} 　　printf(" "); 　} 　val = d[lenStr1 * lenStr1 + lenStr2]; 　free(d); 　return val; } int main(void) { 　LevenshteinDistance("JAPAN", "JAAP"); 　return EXIT_SUCCESS; } /* ここまで */

Tacosan · Answer

「ある文字列から別の文字列へ, どのように操作すれば変形できるのか」は, 距離を求めたときの表をじっと見ればわかる.

距離の計算方法から
どのような操作をしたのか
が 1か所確定しているので, それを足掛かりにして表をたどっていけばいい.

cametan_42 · Answer

> ヒントでは直感的に最適と思われる経路と書いてあったのでじゃあこれはヒントじゃなかったのか...

そういう事です。
そもそも、プログラミングする時点で「直感的」っておかしいでしょ(笑)。
人間には直感があるけど、コンピュータには直感なんざありません。

いやね、実際にはこういうのは「探索」って言う問題に分類されるんですが。
要するに最適の経路を探せ、ってのは昔っからの研究テーマである程度技法は確立してはいるんだけど、貴方が初心者ならとてもじゃないけど解けない。
例えばね。その先生簡単に「直感」って言うかもしれないけど。左上隅から右下隅に向かっていくとして。
初手で3つ取り得る方向がありますよね。じゃあ次手は何なのか、と言うとそれぞれ3方向に行けるので3*3=3^2が進める先になる。じゃあ次はどうなのか、ってぇと9つの枝先がまたそれぞれ3つ進める先なので、9×3 = 3^3に分岐する。その先は・・・とn手で3^n上の「可能性があるルート」がある、って話になる。
そしてその最大3^n個のルートに対して得点加算して全部比較する、んですよ。マトモにやればね。こういうのを「総当り」と言うんだけど、計算量が半端ないでしょ？人間だったら「直感的」に分かってもコンピュータには「総当り」しか原則出来ないのです。だから「直感的」なんつーアドバイスはおかしい。とてもプログラミングの教師たぁ思えない発言ですよ(笑)。
要するにプログラミングの場合は、この「総当り」をベースにして、如何に計算量を減らしていくのか、と言う研究が行われてきたわけです。バックトラッキングとかそういうテクニックが開発されてきたわけですが、まぁ、何度も言いますが、C言語でプログラミング初心者とかがとてもじゃないけどプログラム可能な方法論ではないですよ。

> 記事ではレーベンシュタイン距離を求めているようですがこれを自分が言っていた表示にすることはできないですか？

いや、結局レーベンシュタイン距離は定義上、変換にいくらコストがかかるのか、数え上げてるだけで、「どんな変換が要り用なのか」を教えてくれる手法じゃないですからねぇ。
表を出力したり、表を作る際にどんな「作業」が用いられたかを表示する事は可能ですが、単にそれだけ、でしょう。

/* 改造版の例 (でもあまり意味がない) */

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

int minimum(int n0, int n1, int n2) {
　if (n0 <= n1 && n0 <= n2) {
　　puts("D: 削除誤り");
　　return n0;
　} else if (n1 <= n0 && n1 <= n2) {
　　puts("I: 挿入誤り");
　　return n1;
　} else {
　　puts("S: 置換誤り");
　　return n2;
　}
}

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

　for (int i1 = 0; i1 <= lenStr1; i1++) { d[i1 * lenStr1] = i1; }
　for (int i2 = 0; i2 <= lenStr2; i2++) { d[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 * lenStr1 + i2] = minimum(
　　　　　　　　　　　　　　　　　　d[(i1 - 1) * lenStr1 + i2] + 1,
　　　　　　　　　　　　　　　　　　d[i1 * lenStr1 + i2 - 1] + 1,
　　　　　　　　　　　　　　　　　　d[(i1 - 1) * lenStr1 + i2 - 1] + cost
　　　　　　　　　　　　　　　　　　);
　　}
　}
　/* この辺印字処理であまり本質的じゃない */
　printf(" ");
　for (int i = 0; i < lenStr2; i++) { printf("%c ", str2[i]); }
　printf("\n");
　for (int i1 = 0; i1 <= lenStr1; i1++) {
　　if (i1 == 0) { printf(" "); } else { printf("%c ", str1[i1-1]); }
　　for (int i2 = 0; i2 <= lenStr2; i2++) {
　　　printf("%d ", d[i1 * lenStr1 + i2]);
　　}
　　printf("\n");
　}
　val = d[lenStr1 * lenStr1 + lenStr2];
　free(d);
　return val;
}

int main(void) {
　LevenshteinDistance("JAPAN", "JAAP");
　return EXIT_SUCCESS;
}

cametan_42 · Answer

> この問題は最適な経路を通る要するになるべく1をたくさん通るように進むという問題です。

ところがそうなるとだね。
JAPANとJAANの組み合わせだと(A, A) = (1, 1)の次の一手をどうするのか、と言う話がある。
ここで選択肢は3つなんだけど、最小になるのは(A, A) = (1, 2)、つまり下に進む事。これが最小手になります。
次が(P, P) = (2, 3)へ進む。この時点で得点が4点で最小点になってるの。
この経路だと最終的に得点が10点になって最小値にはならない。ただし、経路の途中で最小点を生み出してるのは確かで、そうすると、途中までは貴方の示した経路を選ぶ必然性が全くないんだ。

要するにね、アルゴリズム、と言うのはキチンと次の一手もトータルで計算した時に矛盾無く組み立てられてなければならない、と言う事。言い換えるとこのヒントはアルゴリズムでも何でもないんですよ。
「人間が見た時」自明で簡単でも、コンピュータにとってはそうじゃないんです。キチンと次の一手が最終手で正しくなる事を保証してやんなきゃならない。
まぁ、少なくとも、その「ヒント」とやらは全くヒントになっていないですねぇ。

cametan_42 · Answer

うーん、それでもかなり曖昧なんだよな、このヒント。

今、文字列がJAPAN、JAAPと2つある。
規則的には表にした時、(J, J)を(0, 0)とした時、(N, P) = (4, 3)を目指すとする。
まぁ、ここまでは良いとしよう。
原則(J, J)から3が出てくるまで右下に向かって対角線上を移動していく、と。
で(P, A) = (2, 2)のマスが3なんで方向を変えるわけなんだけど。
ここで(A, A) = (3, 2)に移動する「根拠」はなんだろ？(P, P) = (2, 3)に進んじゃダメだ、って言う根拠は？
要するに、進める方向が2方向あるわけですよ、実は。このヒントだと「当たり前のように」横(右)に進んでるけど、その根拠がない。

これは次のように考えてみれば自明なんです。
正解がJAAP、間違った列がJAPANだとする。あくまで仮に、ですが。
そうすると表はこうなるよね。

1 3 3 3
3 1 1 3
3 3 3 1
3 1 1 3
3 3 3 3

そうすると、(0, 0) -> (1, 1) -> (2, 2)と進んで3に接触する。右に進む？下に進む？
このヒントのように「右に進む」ならそこで1に出会って終り、です。右下隅には到達出来ない。
というように、この「ヒント」だとロジックに穴があるのね。

それと、右下隅が3だった場合、決してそこに到達出来ないわけじゃない(何故なら対角線上を右下に向かって、1がある限り進む、と言うのが基本ロジックだから、言い換えると1じゃない時は「永久にそこは踏めない」)。そこをどう解決するのか、このロジックだとそこにも穴があるのよね。

さぁ、どうします？

cametan_42 · Answer

画像が小さいは線が薄いわ、で全然読めないんですが。

そもそも3ってなんだろ？2じゃなかったの？

cametan_42 · Answer

> やりたいことを画像で書いてみました。

いやまぁ、それはいいんですが。
ところがそれだとJAPANとJPANとか、JAPANとJAAPANとか、誰が見ても「なるほど」と言う2つの文字列にしか適用出来ないんじゃないですか？
「誰が見ても」ってのは、極論、プログラムにわざわざするような事ではない、と言う事です。
問題は、

kitten
sitting

みたいな2つの文字列の場合、どういう結果を出力するのか、またそのためのアルゴリズムです。
この辺はどう考えてる、って言うのか、その課題のヒントはどうしろ、って言ってるのか。
その辺が分からんのですよ。

cametan_42 · Answer

> プログラムを実行した後に正しい文字JAPAN、微妙に違う文字JAPNなどと入力すると挿入誤り Iなどとしたいということです。

同じ文字なら1違う文字なら2を返す表をつくりました。

いや、それだけならレーベンシュタイン距離なんか考えなくて良いですよ。
表を出すだけだったら、例えば、

/* ここから */

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

char* foo(char str1[], char str2[]) {
　int lenStr1 = strlen(str1);
　int lenStr2 = strlen(str2);
　char* matrix = malloc(sizeof(char) * (lenStr1 + 1) * (lenStr2 + 1));
　matrix[0] = ' ';
　for (int i1 = 0; i1 <= lenStr1; i1++) { matrix[i1 + 1] = str1[i1];}
　for (int i2 = 0; i2 <= lenStr2; i2++) { matrix[(i2 + 1) * (lenStr1 + 1)] = str2[i2];}

　for (int i2 = 1; i2 <= lenStr2; i2++) {
　　for (int i1 = 1; i1 <= lenStr1; i1++) {
　　　matrix[i1 + i2 * (lenStr1 + 1)] = (str2[i2 - 1] == str1[i1 - 1])? '1' : '2';
　　}
　}
　for (int i2 = 0; i2 <= lenStr2; i2++) {
　　for (int i1 = 0; i1 <= lenStr1; i1++) {
　　　printf("%c ", matrix[i1 + i2 * (lenStr1 + 1)]);
　　}
　　printf("\n");
　}
　return matrix;
}

int main(void) {
　char* str1 = "JAPAN", *str2 = "JAPN";
　char* p = foo(str1, str2);
　free(p);
　return EXIT_SUCCESS;
}

/* ここまで */

とやるだけで済みます。

> この対角線で進む経路を考えて、横移動(JAPNのPとJAPANのPの1から
JAPNのPとJAPANのAの2に行くこと)だとD排除誤り、縦移動だとI挿入誤りとかんがえて判断したいということです。

うん、ぶっちゃけ何書いてるかサッパリ分からんのですが(笑)。
縦とか横とか何だろ？そもそも対角線だって2つあるんで、これだと動作を規定出来ません(JAPANだってAが2つあるんで、方向を規定せんと意味がないです)。
ただ、表さえ入手すれば、その辺は条件式ツッコんで書けるんじゃないですかね。

> それにしてもC言語は非常に使いにくいものですね。

使いづらいです。
どういう目的か知らんのですが、フツーに何らかの実験目的でやるならわざわざCなんざ使わん方がマシです。
商用ソフトとかゲーム作るならいざ知らず、この富豪の時代、Cでスクリプトを書く必然性って全然ないですよ。

> こういう2次元配列系はmatlabでやったほうが簡単に書けるのでしょうか

まぁ、MATLAB自体がニッチだし、フツー誰も個人で所有してないんであまりうん、とは言いたくないですが(笑)。
ただ、行列扱うのは得意なのは事実なんで(と言うか行列扱う為に開発されてるんで)、質問に単純に答えると"YES"でしょうね。

例えば同じ題意を、MATLAB互換と言われてるGNU Octaveで書くと、

function d = foo(str1, str2)
　row = length(str2);
　col = length(str1);
　d = zeros(row, col);
　for r = 1:row
　　for c = 1:col
　　　if str2(r) == str1(c)
　　　　d(r, c) = 1
　　　else
　　　　d(r, c) = 2
　　　endif
　　endfor
　endfor
endfunction

みたいになって、Cよりは遥かにシンプルに書けはしますね・・・ラベルさえ考えなければ。

cametan_42 · Answer

Oops!!!

なんだ、MSのVisual Studio 2019ってVLAサポートしとらんのかい。

C11 and C17 Standard Support Arriving in MSVC:
https://devblogs.microsoft.com/cppblog/c11-and-c …

"Astute readers will note that VLAs are also not supported. Variable length arrays are generally less efficient than comparable fixed sized arrays, and generally inefficient compared to equivalent malloc(), when safely and securely implemented. VLAs provide attack vectors comparable to those of the infamous gets() — deprecated and destined to removal — for opportunities of “shifting the stack” and other exploits. For these reasons we intend not to support VLAs as an optional feature in C11."

意訳: 「可変長配列は固定配列や動的配列より効率が悪いし、遅いんで、今後も実装しないつもりだよ！」

Fuck!
うるッせぇわ(怒

まさかここでコンパイラの互換性に悩まされるたぁ思ってなかったなぁ。

orz

ってこたぁ面倒だけど、動的配列で実装するしかないんか。
こういうのってあんま本質的じゃないトコでのテクニックで悩まされるから嫌なんだけどなぁ。
だから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, val;
　int lenStr1 = strlen(str1);
　int lenStr2 = strlen(str2);
　int* d = malloc(sizeof(int) * (lenStr1 + 1) * (lenStr2 + 1));

　for (int i1 = 0; i1 <= lenStr1; i1++) { d[i1 * lenStr1] = i1; }
　for (int i2 = 0; i2 <= lenStr2; i2++) { d[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 * lenStr1 + i2] = minimum(
　　　　　　　　　　　　　　　　　　/* 文字の削除 */
　　　　　　　　　　　　　　　　　　d[(i1 - 1) * lenStr1 + i2] + 1,
　　　　　　　　　　　　　　　　　　/* 文字の挿入 */
　　　　　　　　　　　　　　　　　　d[i1 * lenStr1 + i2 - 1] + 1,
　　　　　　　　　　　　　　　　　　/* 文字の置換 */
　　　　　　　　　　　　　　　　　　d[(i1 - 1) * lenStr1 + i2 - 1] + cost
　　　　　　　　　　　　　　　　　　);
　　}
　}

　val = d[lenStr1 * lenStr1 + lenStr2];
　free(d);
　return val;
}

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

/* ここまで */

良くある動的配列の手で、発想は二次元配列なんだけど、実装は一次元配列で「見立てる」と言う方法を使ってます(ホントの事言うと、そもそもC言語には「多次元配列」なんつー気の利いたモノさえ無い)。
Wikipediaの例の疑似コード

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

と良く見比べてください。

まぁ、このようにCは非力なんで、アルゴリズムは簡単なんだけど、「Cで実装すると」あんま本質に関係ないトコでどんどん複雑になっていく、と言う良い例になったかしらん。
だからこんな言語を初心者にやらせて

「コンピュータの仕組みが分かる」

とかクソみたいな妄言だって良く分かったんじゃないでしょうか(笑)。
言い換えると、コンピュータの仕組みに近ければ近いほど数学的でピュアな「アルゴリズム」から実は乖離していってんだ、って事なのです。

cametan_42 · Answer

あ、それと。一つ忘れてたや。

MicrosoftのVisual Studioの処理系でC言語使ってプログラミングする場合。
次の設定をしておいてください。もはやこれはMUSTです。

Visual Studio に C11 および C17 サポートをインストールする:
https://docs.microsoft.com/ja-jp/cpp/overview/install-c17-support?view=msvc-160

これを設定しておけば、2021年現在、Visual StudioのC処理系はC言語仕様上最強の処理系となります。
この設定ナシでCのプログラムをやろうとすると、Visual Studioではクソメンド臭い事になります。

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

> 画像の意味がよくわかっていないのですが表の数字は何でしょうか？

「ある文字列から別の文字列へ, どのように操作すれば変形できるのか」は, 距離を求めたときの表をじっと見ればわかる.

> ヒントでは直感的に最適と思われる経路と書いてあったのでじゃあこれはヒントじゃなかったのか...

> この問題は最適な経路を通る要するになるべく1をたくさん通るように進むという問題です。

うーん、それでもかなり曖昧なんだよな、このヒント。

画像が小さいは線が薄いわ、で全然読めないんですが。

> やりたいことを画像で書いてみました。

> プログラムを実行した後に正しい文字JAPAN、微妙に違う文字JAPNなどと入力すると挿入誤り Iなどとしたいということです。

Oops!!!

あ、それと。

似たような質問が見つかりました

このQ&Aを見た人はこんなQ&Aも見ています

関連するカテゴリからQ&Aを探す

このQ&Aを見た人がよく見るQ&A

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング