ホチキス先生の「プログラマーと呼ばれたい」

InfoPath & SQL Server !

C# – 文字列を比較するアルゴリズムについて考える(1) – 2つの文字列を前から順に比較し、違いがあった位置を見つけるアルゴリズム

leave a comment »

学校の授業で文字入力のトレーニングをするために、効果的なアプリケーションを作っている。ここで必要な実装として文字列比較がある。

仕様、というか、個人で作るアプリケーションなので厳密な仕様は決めないが、イメージ的にはこうだ。入力トレーニングの元になる文がある。この文は、フォントやポイント、文字飾りなどは無視し、単にテキスト文字列だけのものとする。つまり単なるテキスト文とする。この文と同じ文をキーボードから入力するトレーニングとし、入力にかかった時間と入力できた文字数をカウントしてスコアとする。このとき、入力を間違ったことを評価に加えたい、というものだ。

すぐに思いつくのは、文字列を前から順番に比較し、違いがあったら位置を見つけ出すアルゴリズムだ。2つの文字列が myStr1 と myStr2 に入っており、2つの文字列の長さが同じだとする。

——————————————————————

for (int i = 0; i < myStr1.Length; i++)
{
    if (myStr1[i] != myStr2[i])
    {
        myStrDiff = i;
        break;
    }
}

——————————————————————

前から順に比較し、違いがあった文字でループを抜ける。前から何文字目であったかが myStrDiff に数字として入る。この数字は 0 から始まるので、実際は +1 文字目に違いがあった、となる。これだと、たとえば次のようになるだろう。

myStr1 = "あいうえおかきくけこ";
myStr2 = "あいうえおまきくけこ";

このとき、myStrDiff の値は 5となる。前から 6文字目に違いがあるからだ。しかし、「か」を「ま」と間違えてはいるが、そのあとはちゃんと入力できている。つまり「5文字目までしか間違いなく入力できなかった」のではなく「6文字目だけ間違えたが、それ以外はちゃんと入力できた」はずだ。つまり、このように評価すべきだろう。

入力すべき文字列 ・・・ あいうえおかきくけこ
実際の入力1 ・・・・・ あいうえおかきくけこ (評価10点:満点)
実際の入力2 ・・・・・ あいうえおまきくけこ (評価9点:1文字だけ間違った)
実際の入力3 ・・・・・ あいうえおまみむめも (評価5点:5文字間違った)

つまり、間違った文字以降をどう再判定するか、を考えなければならない。このアルゴリズムについて引き続き考えていきたい。

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。