ページ 1 / 1
文字列探索プログラムの日本語化について
Posted: 2018年1月10日(水) 17:10
by せうご
コード:
#include <stdio.h>
#include <string.h>
char S1[100], S2[100];
//最少値を求める
int min(int a, int b, int c)
{
return a > b ? (b > c ? c : b) : (a > c ? c : a);
}
int main()
{
scanf("%s", S1);
scanf("%s", S2);
//編集距離計算
int lenstr1 = strlen(S1) + 1;
int lenstr2 = strlen(S2) + 1;
int d[100][100];
int i1 = 0, i2 = 0, cost = 0;
for (; i1 < lenstr1; i1++) d[i1][0] = i1;
for (; i2 < lenstr2; i2++) d[0][i2] = i2;
for (i1 = 1; i1 < lenstr1; i1++) {
for (i2 = 1; i2 < lenstr2; i2++) {
cost = S1[i1 - 1] == S2[i2 - 1] ? 0 : 1;
d[i1][i2] = min(d[i1 - 1][i2] + 1, d[i1][i2 - 1] + 1, d[i1 - 1][i2 - 1] + cost);
}
}
printf("編集距離は%dです\n", d[lenstr1 - 1][lenstr2 - 1]);
}
このプログラムを日本語対応しようとしているのですが、正確な値が出せません。
例えば、あいうえお、いうえお、という文字列を比較した際、編集距離は1になるはずなのですが
2と表示されてしまいます。
ご教授お願い致します。
Re: 文字列探索プログラムの日本語化について
Posted: 2018年1月10日(水) 18:10
by かずま
wchar_t と locale を使えばよいでしょう、
コード:
#include <stdio.h>
#include <wchar.h> // wcslen // 変更
#include <locale.h> // setlocale // 追加
wchar_t S1[100], S2[100]; // 変更
int min(int a, int b, int c)
{
return a > b ? (b > c ? c : b) : (a > c ? c : a);
}
int main()
{
setlocale(LC_CTYPE, ""); // 追加
scanf("%ls", S1); // 変更
scanf("%ls", S2); // 変更
//編集距離計算
int lenstr1 = wcslen(S1) + 1;
int lenstr2 = wcslen(S2) + 1;
int d[100][100];
int i1 = 0, i2 = 0, cost = 0;
for (; i1 < lenstr1; i1++) d[i1][0] = i1;
for (; i2 < lenstr2; i2++) d[0][i2] = i2;
for (i1 = 1; i1 < lenstr1; i1++) {
for (i2 = 1; i2 < lenstr2; i2++) {
cost = S1[i1 - 1] == S2[i2 - 1] ? 0 : 1;
d[i1][i2] = min(d[i1 - 1][i2] + 1, d[i1][i2 - 1] + 1, d[i1 - 1][i2 - 1] + cost);
}
}
printf("編集距離は%dです\n", d[lenstr1 - 1][lenstr2 - 1]);
}
Re: 文字列探索プログラムの日本語化について
Posted: 2018年1月10日(水) 20:43
by せうご
ありがとうございます。
ご指摘のようにwchar_tを使った方法は検討したのですが、エラーこそ起きないものの、正しい結果が表示されませんでした。
例えばきりぎりすときらぎすを比べた際、結果は2となるはずが1となってしまいます。
計算方法そのものに間違いがあるのでしょうか。
ご検討お願いします。
Re: 文字列探索プログラムの日本語化について
Posted: 2018年1月10日(水) 21:42
by かずま
OS とコンパイラは何ですか?
Linux の gcc では、問題なく編集距離は 2 になりました。
Windows の VC++ の scanf の "%ls" には、バグがあるようです。
次のように wscanf を使用すると、このバグを回避できるようです。
コード:
wscanf(L"%ls", S1);
wscanf(L"%ls", S2);
Re: 文字列探索プログラムの日本語化について
Posted: 2018年1月13日(土) 15:44
by かずま
まだ解決にならないのでしょうか?
int d[100][100]; ですが、表を上から順番に作っていくので、
ある行と、その次の行の二つの行だけでできます。
コード:
#include <stdio.h> // printf
#include <wchar.h> // wcslen, wscanf
#include <locale.h> // setlocale
int min(int a, int b, int c)
{
return a < b ? (a < c ? a : c) : (b < c ? b : c);
}
int main(void)
{
setlocale(LC_CTYPE, "");
wchar_t s1[100], s2[100];
wscanf(L"%ls", s1), wscanf(L"%ls", s2);
int n1 = wcslen(s1), n2 = wcslen(s2);
int d[2][100], *a = d[0], *b = d[1], *t;
for (int j = 0; j <= n2; j++) a[j] = j;
for (int i = 0; i < n1; i++) {
b[0] = i + 1;
for (int j = 0; j < n2; j++)
b[j+1] = min(a[j+1] + 1, b[j] + 1, a[j] + (s1[i] != s2[j]));
t = a, a = b, b = t;
}
printf("編集距離は %d です\n", a[n2]);
}