このページは 2001 年四月に書いたものに少々加筆したものです。 初めはこれが「その１」の後半になる予定でした。 厳密に書こうとしすぎていると気づいたので、 いまの「その１」の形に書き直したのですが、 そこで使われなかった部分を一応まとめたのがこの「その２」です。
零個の文字からなる文字列を「空文字列」と呼ぶ。
txt と usr を同数の文字列に分割する。 ただし、それらを τ1τ2...τn および υ1υ2...υn とするとき、各 i について τi と υi の組は
与えられた txt と usr に対し少なくとも一つの採点が存在する。 与えられた txt と usr に対し採点は一通りとは限らない。
エラー数が最も少ない採点を「エラー数最小の採点」と呼ぶ。 これも一通りとは限らない。 エラー数最小の採点のエラー数も「エラー数」という。 呼び名は同じであるが紛れはあまりないと思う。
注） txt も usr も空文字列の場合は、必然的に零個の文字列に分割することになり、 「エラー数 0」である。
付） txt と usr を上下に並べて書き、文字列の組 τi と υi を線分で結んでみれば、 この定義が妥当なものであることがわかるだろう。 前の例では
| a | b | c | d | e | f | g | h | i | jk | l | |
| | | | | | | | | | | | | | | | | | | | | | | | |
| a | z | c | d | y | e | f | h | i | kj | l |
付） 「採点」の定義には次のようなものも考えられよう。 文字列 txt と比較して 「エラー 1」と判定される文字列は最初に例であげたようなもの、と定義する。 その文字列と比較して「エラー 1」と判定される文字列は 「エラー 2 以下」とする。 その文字列と比較して「エラー 1」と判定される文字列は 「エラー 3 以下」とする。 こうやって帰納的に「エラー n 以下」を定義したうえで 「エラー n 以下」であるが「エラー (n-1) 以下」でない文字列を 「エラー n」と定義する。 上で述べた「採点」でエラー数 n の場合、 この定義でエラー n 以下になることは明らかであろう。 しかし、両者は一致はしない。 「txt が abcd, usr が bdac」の場合、 転置をくり返すと abcd → bacd → badc → bdac だからこの意味ではエラー 3 以下となるが、 上で述べた定義に従えばエラー数最小の採点でのエラー数は 4 になる。
txt と usr が与えられたとする。
txt または usr が空文字列の場合、
次に、txt も usr も空文字列でない場合を考える。 それらが次のような文字列であったとしよう。 ここで ti や uj は一文字を表わしている。
| t1 | t2 | t3 | ... |
| u1 | u2 | u3 | ... |
「エラー数最小の採点」（の一つ）で最初の部分がどう判定されたかを考えると、 それは次のいずれかである。
全体のエラー数は
よって、 txt の文字数と usr の文字数の積がより小さい場合に問題は帰着した。 その積が 0 の場合は最初に考察を済ませてある。
上のアイディアを、再帰を用いたプログラムにしてみた。 ただし、簡単のため、「転置」はエラーの種類に含めないことにした。
#include <stdio.h>
#include <string.h> /* strlen() */
#define MIN3(X,Y,Z) ((X)<(Y)?(X)<(Z)?(X):(Z):(Y)<(Z)?(Y):(Z))
int compare(char* p, char* q);
unsigned long count = 0; /* compare() の呼ばれた回数 */
int errors; /* エラーの数 */
int main(int argc, char* argv[]) {
char *p, *q;
p = argc > 1 ? argv[1] : "";
q = argc > 2 ? argv[2] : "";
errors = compare(p, q);
putchar('\n');
printf("\"%s\" and \"%s\", ", p, q);
printf("%lu times, %d error(s).", count, errors);
return 0;
}
/* 文字列 p と q を比較してエラーの数を返す（再帰バージョン）*/
int compare(char* p, char* q) {
int n, n1, n2; /* エラーの数を一時的にいれる変数 */
if (count++ % 100000 == 0) {
putchar('.'); /* 止まっていないことをアピールするための出力 */
fflush(stdout);
}
if (*p == '\0') { /* p が空文字列の場合 */
return strlen(q); /* 「エラー数は q の長さ」が答え（挿入）*/
}
if (*q == '\0') { /* q が空文字列の場合 */
return strlen(p); /* 「エラー数は p の長さ」が答え（脱落）*/
}
/* p も q も空文字列でない場合 */
/* 正常または誤打と仮定してみる */
n = compare(p+1, q+1); /* p+1 と q+1 を比較（ここで自分自身を呼ぶ） */
if (*p != *q) { /* *p と *q が一致しない場合は */
n++; /* 誤打の分として 1 だけ増やす */
}
n1 = compare(p+1, q) + 1; /* 脱落と仮定してみる（ここで自分自身を呼ぶ）*/
n2 = compare(p, q+1) + 1; /* 挿入と仮定してみる（ここで自分自身を呼ぶ）*/
return MIN3(n, n1, n2); /* 三つを比較して最小のものを返す */
}
「わかるのがエラー数だけ」という欠陥もあるが、 それ以前に計算量が多すぎる。 txt と usr の文字数を縦横にとって関数の呼ばれた回数を表にすると次のようになる。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 4 | 7 | 10 | 13 | 16 | 19 | 22 | 25 | 28 | 31 |
| 2 | 1 | 7 | 19 | 37 | 61 | 91 | 127 | 169 | 217 | 271 | 331 |
| 3 | 1 | 10 | 37 | 94 | 193 | 346 | 565 | 862 | 1249 | 1738 | 2341 |
| 4 | 1 | 13 | 61 | 193 | 481 | 1021 | 1933 | 3361 | 5473 | 8461 | 12541 |
| 5 | 1 | 16 | 91 | 346 | 1021 | 2524 | 5479 | 10774 | 19609 | 33544 | 54547 |
| 6 | 1 | 19 | 127 | 565 | 1933 | 5479 | 13483 | 29737 | 60121 | 113275 | 201367 |
| 7 | 1 | 22 | 169 | 862 | 3361 | 10774 | 29737 | 72958 | 162817 | 336214 | 650857 |
| 8 | 1 | 25 | 217 | 1249 | 5473 | 19609 | 60121 | 162817 | 398593 | 897625 | 1884697 |
| 9 | 1 | 28 | 271 | 1738 | 8461 | 33544 | 113275 | 336214 | 897625 | 2193844 | 4976167 |
| 10 | 1 | 31 | 331 | 2341 | 12541 | 54547 | 201367 | 650857 | 1884697 | 4976167 | 12146179 |
（この表はプログラムのデバッグも兼ねて実験により数値を求めたが、 各マスの数は 「左上のマスの数」＋「上のマスの数」＋「左のマスの数」＋１としても計算できる。）
上の表の範囲で、すでに実用的でなくなっている。 実際の練習文は 60 文字ぐらいあるので、これではとても使えない。
付） 再帰を用いる方法は、割と最近まで思いつかなかった。 このプログラムの本質的部分を書いたのは 2001-04-12 (4) である。