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

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文字間違った)

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

2017年4月7日

松本 吉生(まつもとよしお)
Microsoft MVP Data Platform

1961年京都に生まれ、神戸で幼少期を過ごす。大学で応用化学を学んだのち、理科教諭として高等学校に勤務する。教育の情報化が進む中で校内ネットワークの構築運用に従事し、兵庫県立明石高等学校で文部科学省の「光ファイバー網による学校ネットワーク活用方法研究開発事業」に携わる。兵庫県立西宮香風高等学校では多部制単位制の複雑な教育システムを管理する学籍管理データベースシステムをSQL ServerとInfoPath、AccessなどのOfficeソフトウエアによるOBA開発で構築・運用する。現在は兵庫県立神戸工業高等学校でC#プログラミング、IoTなどのコンピュータ教育を行う。2004年からマイクロソフトMVP(Microsoft Most Valuable Professional)を受賞し、現在14回目の連続受賞。2016年にマイクロソフト認定教育者(Microsoft Innovative Educator Experts : MIEE)を受賞。

広告

コメントを残す

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

WordPress.com ロゴ

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

Google+ フォト

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

Twitter 画像

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

Facebook の写真

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

w

%s と連携中

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