このページでは、 私たちの作ったタイピング練習プログラム tx で使用した採点アルゴリズムについて説明する。
このアルゴリズムはタイピング練習の結果の採点には十分な力を発揮する。 すなわち、一行分のテキストとそれをユーザが打った文字列とを比較し、 誤打のみならず挿入や脱落も込めて、 ほぼ瞬時に、練習者に不満を与えないような判定結果を出すことができる。 しかし、 計算量および必要なメモリが 「打つべきテキストの長さ」と 「練習者が実際に打った文字列の長さ」の積に比例するので、 アルゴリズムとしては平凡なものである。
以下、 打つべき文字列を txt で、 練習者が実際に打った文字列を usr で表わす。 txt は text に、usr は user に由来する記号である。 txt の下に usr を書き、さらにその下に採点結果を書くが、 採点結果は usr の地の色などでも示してある。
エラーには、次のようなものが考えられる。
| a | b | c |
| a | z | c |
| * |
| a | b | |
| a | z | b |
| + |
| a | b | c |
| a | > | c |
| - |
| a | b | c | d |
| a | c | b | d |
| ) | ( |
注） 「転置」をエラーの種類に含めない方法もある。 その場合は、上の転置の例は複数のエラーになる。 しかし、転置は比較的よく起こるミスなので一つと数えたい。 そのためにこれもエラーの種類に含めてあるのである。
注） 「脱落」の例の usr は「ac」であって「a>c」ではない。 にもかかわらず間に「>」を入れて表示するのは、 そうでないと脱落したことを示しにくいのと、 こうすることでこの脱落以降の文字がそろうからである。
次は、上にあげた「誤打」「挿入」「脱落」「転置」を “きれいに”四つ含む例である。
| a | b | c | d | e | f | g | h | i | j | k | l | |
| a | z | c | d | y | e | f | > | h | i | k | j | l |
| * | + | - | ) | ( |
これは「エラー数 4」と採点するのが自然であろう。
注）この例では脱落部分に「>」 を入れないで表示したほうがそれ以降の文字がそろうが、 上のように決めたのでそうしてある。
上の例では、四つの誤りの間に正しく打てている部分があった。 しかし、必ずそうであるとは限らない。
| a | b | c | d | |
| a | x | y | z | d |
| * | * | + |
この例では誤打の直後に挿入が起こっている。
注） これを
| a | b | c | d | |
| a | x | y | z | d |
| * | + | * |
| a | b | c | d | |
| a | x | y | z | d |
| + | * | * |
付） この例は常識的には「bc を xyz と打ち誤った」 と採点するところだが、 単純化のためエラーの種類は前に挙げた四つに限っている。 「エラー数 3」とすることに疑問の余地もありえようが、 タイピング練習の採点に用いるという当初の目的を思い出してみると、 このような“まとまった”打ち間違いをしている間はまだまだ練習が不足であり、 次の課に進ませるべきではない、ということだけは確かである。 よってこの程度の採点法で十分なのである。
ここまでに出てきた例ではエラー数が最小となる採点のしかたはほぼ自明であった。 しかし、エラーが近接して起こった場合にはそれは自明とは限らない。 そこで、アルゴリズムを考えることが必要になるのである。
ここでは、 表を見やすくするため、転置をエラーの種類に含めないとして説明する。
txt が abcdef, usr が axycfe の場合を考えよう。 前者を表の下の端に書き、後者を表の左の端に、下から上へ向かって書く。 「$」は文字列の終わりを表わす記号である。
表本体には、 そこ以降の文字列をエラー数最小となるように比較した場合のエラー数を記入する。 たとえば、下辺の d と左辺の y の交点には、 その文字以降の文字のなす部分文字列 def と ycfe をエラー数最小となるよう採点した場合のエラー数である 3 が記入してある。
|
表本体の埋め方は以下の通りである。 表本体の一番上の一列、一番右の一列の数が上のようになることは明らかであろう。
次に、まだ数を埋めていないマスで、 その「上」「右上」「右」がすべて埋まっているマスを一つ選ぶ。 そのマスの左には文字 x が、下には文字 y が書かれているとする。 このとき、そのマスには次の数のうち最小のものを記入する。
このとき、単に数を記入するだけでなく、 どのように計算して埋めたのかも記録しておく。
これで正しく表が埋められることは、少し考えればわかるであろう。
なお、最初に書き込んだ上辺の数は「-」で、 右辺の数は「|」で結ぶのが適当であることがわかるだろう。
こうやってできたのが上の表である。
この表では、左下のマスにエラー数最小の採点によるエラー数が表示されている。 この例ではそれは 4 である。 また、どう採点されたかを読み取るには、 左下のマスから線をたどって「上」「右上」「右」へと進んでゆけばよい。 その結果は
| a | b | c | d | e | f | |
| a | x | y | c | f | e | > |
| * | + | * | - |
| a | b | c | d | e | f | |
| a | x | y | c | f | e | > |
| + | * | * | - |
上のアルゴリズムをＴコードの練習プログラムに使う場合、 実際にユーザが打った（いわゆる）日本語の文字列をテキストと比較するのでなく、 どちらもキーストロークの列とみなして比較すればよいのではあるまいか。 「はるになると」の最初の「は」の第二ストロークが脱落すると 「映基言渋輸」という全く異なる文字群が現れる。 このまま比較すると全てエラーだが、 キーストロークとして比較すれば
| は | る | に | な | る | と | ||||||
| j | > | る | に | な | る | と | |||||
| - | |||||||||||
Ｔコードは常に１文字につき２ストロークだが、 文字によって長さが異なるコードもあるそうである。 その場合も、この方法はそのまま使えるものと思われる。
付） ただし、これでは
| は | る | に | な | る | と | ||
| る | は | に | な | る | と | ||
| ) | ( | ||||||