論文

HITs における Typing 練習用採点プログラムの改良
松井吉光 （愛知大学法学部）

要旨：
近年，情報機器の普及が進む反面，PC の扱い，特にキーボード入力に不慣れな学生が再び増加しつつある。今後しばらくは PC における入力の主体はキーボード入力であり続ける可能性が高く，タッチタイピングによるキーボード入力スキルを身につけることは，学生にとって大学での勉学を修める上でも，卒業後社会に出てからも必須であると言えよう。このような状況にあるため，情報リテラシー・入門では e-Learning システムである HITs において，Typing 練習の問題を多数用意し，自習できる環境を整備している。その HITs における Typing 採点プログラムについて，2019 年度の講義に向けて，差分検出アルゴリズムを用いてエラーメッセージ表示機能の改良を行った。それにより，学生の Typing 学習の効率化を図った。本稿では改良に用いた差分検出アルゴリズムについて述べる。

キーワード：e-Learning，Typing，情報リテラシー教育，差分検出アルゴリズム

1．はじめにでも，キーボードによる文字入力についても不慣れで入力速度がほとんど上がら近年，スマートフォンの普及によりイない学生が多いようである。

ンターネットを使ったコミュニケーショ

PC に お け る 入 力 の 主 体 が 将 来 音 声 入ン，情報収集に一定のスキルを持って大力等の他の方法に移行していくことは考学に入学してくる学生が増えてはいる

えられるが，今後何年かはキーボード入が，逆に PC の利用に関して言えば，そ力がその地位を譲ることは想定できる現の機会が減ってきていて扱いに不慣れな状 で は な い た め， キ ー ボ ー ド 入 力 の 技学生が増えているように感じられる。そ術，特にタッチタイピングのスキルは学れを反映してか，キーボードの入力に関生にとって必須のものであり続けるであして，アルファベットの大文字の入力のろう。そのため，情報リテラシー・入門仕方といったごく基本的な操作方法につで は e-Learning シ ス テ ム で あ る HITs

いての質問がなされるようになってきてに お い て，Typing 練 習 問 題 を 多 数 用 意いる。スマートフォンのフリック入力・し，練習できる環境を提供してきた。

予測変換による入力には長けている学生
愛知大学情報メディアセンター

そ の Typing 練 習 を 支 え て い る の が，－ 15 －Vol.30, No.1, 2020

自動採点プログラムである。採点においムをコーディングすることを試みた。て， 入 力 の 各 行 の 文 字 列 を 模 範 と 比 較

二つの文字列の差分を求めることとし，一致しているかどうかで正解・不正は，変更によって一方の文字列からもう解を判定するという方法をとっており，一方の文字列を生成するときに，どの文その点において全く支障は発生していな字が追加されたか，どの文字が削除されい。ただ，不正解と判定した場合に，不たか，どの文字列がそのままなのかを調

正解個所の学生への提示において，最初べることに尽きる。その際，コンピューの間違い箇所を表示するのみで，全体でタで求めるべきは何カ所間違っているか，2 つ目以降の間◦ SES（Shortest Edit Script）

違っている箇所がどこかを表示するよ◦編集距離（Edit Distance）

う に は な っ て い な い と い う， 学 習 者 に◦最長共通部分列とって不親切な仕様になっていた。今回（Longest Common Subsequence）

は，不正解個所のメッセージをより具体の三つに還元される。その三つの量につ的に，文書全体でどの部分に，誤字があいて以下に述べる。

るか，書込不足か，書込過剰かといった間違いを一目で分かるように改良を行っSESた。このメッセージを作成するのにあた二つの文字列 A，B があったとき，文り用いたのが，本稿で紹介する差分検出

字列 A から文字列 B へ変更するときの手アルゴリズムである。

順は，様々なものが考えられる。そのう
ち，SES を考えるときは，文字列に対す

2．差分検出アルゴリズムの基本

る編集操作として◦任意の位置への一文字の挿入

このプログラム改良に用いた差分検出◦任意の一文字の削除

アルゴリズムとは，入力された文字列との二つのみが許されるものとする。手順

解答の文字列との差分を検出するためののうち最大の手数は，文字列 A の全てのものである。UNIX 等ではファイル等の文字を削除し，文字列 B のすべての文字差分を検出する diff というプログラムがを 挿 入 す る 手 順 で あ ろ う。 文 字 列 A とあり，PHP にも差分を検出する TextDiff

文字列 B に共通の文字がなければもちろ等のライブラリーが存在するが，メンテん，この手順しかないが，そうでなけれナンスが終了していたり，ライセンスがば，もっと少ない手数で変更が可能にな明記されてなかったり等の問題があったるはずである。そういった様々な手順のため，今回は，自前で差分検出プログラ

うち，最も手数が少ない手順を SES と呼愛知大学情報メディアセンター

－ 16 －

Vol.30, No.1, 2020

ぶ。

する際の編集操作の最小回数を指す。文

例えば，二つ「abcde」と「abief」であれば，字列の編集操作は SES と同様，◦任意の位置への一文字の挿入

1．「a」をそのまま◦任意の一文字の削除

2．「b」をそのままの二つのみが許されるものとし，それぞ3．「c」を削除れを「1」と する。 編 集距 離 は SES が分4．「i」を「b」の後に挿入かれば求めることができて，SES におけ5．「d」を削除る削除・挿入の回数に相当する。先の例

6．「e」をそのまま「abcde」と「abief」の場合であれば，編集7．「f」を「e」の後に挿入

距離は「4」となり，「abcde」と「abdce」が SES となる。ただし，SES は二つの文の 場 合 で あ れ ば， 編 集 距 離 は「2」 と な字列が与えられとしても，一意に決まらる。編集距離は二つの文字列が与えられない場合がある。例えば，れば，一意に決まると考えて良い。

「abcde」と「abdce」の場合だと，
1．「a」をそのまま最長共通部分列（LCS）

2．「b」をそのまま

最長共通部分列とは，二つの文字列に3．「c」を削除

共通して含まれる最も長い部分列のこと

4．「d」をそのままである。この時，部分列は部分文字列で5．「c」を「d」の後に挿入はなく，連続した文字列である必要はな

6．「e」をそのままい。ただし，出現する順序は元の文字列との順序通りである必要がある。
1．「a」をそのまま先の例「abcde」と「abief」の場合であ2．「b」をそのままれば，最長共通部分列は「abe」となる。

3．「c」をそのまま

最長共通部分列は SES と同様，一意に決

4．「d」を削除

ま ら な い 場 合 が あ る。 先 の 例「abcde」

5．「d」を「b」の後に挿入と「abdce」 だ と， 最 長 共 通 部 分 列 は6．「e」をそのまま「abce」と「abde」のどちらとしても良はともに SES となる。

い。最長共通部分列と SES は一対一の関係になっており，SES が決まれば最長共編集距離通部分列が決まり，最長共通部分列が決二つの文字列 A，B の違いを数値化しまれば SES が決まるという関係にある。

たもので，文字列 A から文字列 B へ変更
愛知大学情報メディアセンター

－ 17 －

Vol.30, No.1, 2020

差分検出アルゴリズムでは，上記三つでの移動を距離「0」とする。この時の最の量，SES，編集距離，最長共通部分列短距離が，編集距離に相当する。また，を求めることになるが，この問題を編集編集グラフを SES に解釈するときは，斜グラフ（Edit Graph）上の最短距離取得

め線での移動を「そのまま」とし，下方問題に還元し，解を求めるのが一般的で向への移動を「文字の削除」，右方向へのある。編集グラフとは，文字列 A と文字移動を「文字の挿入」とすれば良い。

列 B の各要素を x 軸 y 軸上に 並べ，それの交点を縦横の辺で結合し，文字列 A の

上記の例で SES は例えば，以下のような太線の経路である。

i 番目の文字と文字列 B の j 番目の文字が等しい場合のみ，（i － 1，j － 1）から（i，（0，0）

abiefaj）へ斜め線で結んだものである。

yb

例 え ば，「abcde」 と「abief」 の 場 合cであれば，編集グラフは以下のようになdる。

e（0，0）

abiefaxy（図 2bc（5，5）
編集グラフ上での SES の例）

太線において，縦の線が二つ，横の線dが二つあるので，距離は「4」となり，編ex

集距離が「4」と合致しているのが分か（5，5）（図 1る。
編集グラフ上の最短距離取得問題を解編集グラフの例）

くアルゴリズムとしては，単純な「動的このような編集グラフを考えるとき，計画法」を用いる方法や，それを文字列SES を求める問題は，原点（0，0）からの差分を求めるために効率を良くした，座標（M，N）まで向かう場合の，最短距O（ND）アルゴリズム［8］や O（NP））

離を求める問題に還元される（ここで，アルゴリズム［9］がある。今回の改良でM,N はそれぞれ文字列 A，文字列 B の文は最も単純な「動的計画法」を用いるア字数である）。このとき考える距離は単ルゴリズムを採用した。

純な距離ではなく，編集グラフにおいて縦横へ一つ分の移動を距離「1」，斜め線
愛知大学情報メディアセンター

－ 18 －

Vol.30, No.1, 2020

3．「動的計画法」アルゴリズム◦文字列 A の i 番目の文字と文字列 Bの j 番 目 の 文 字 が 等 し い 場 合 は， 最単純な「動的計画法」を用いるアルゴ

長共通部分列の長さが一つ伸びるのリズムでは，まず編集グラフの各頂点にで「1」を加算する。

辿り着くまでの最長共通部分列の長さを

この規則を用いると先の例の場合は，計算する。文字列 A（文字数 M）と文字各格子点における最長共通部分列の長さ

列 B（文字数 N）を考えるときは，（M ＋は以下のようになる。

1）×（N ＋ 1）の表を作成し，先頭の行，

abief000000a011111b012222

列を以下のように「0」で初期化する（ここでは，文字列 A を「abcde」と文字列B を「abief」を例にとる）。

0a0b0c0d0e0abiefc01222200000d012222e012233（表 2）
次に，この表を用いて SES と最長共通部分列を求めることになるが，このとき（表 1）

座 標（M，N） か ら 原 点（0，0） に 戻 ることを考え，その時最短となる経路を以この表の算出する規則は以下の通りとする。

下の手順で決定していく。
◦文字列 A の i 番目の文字と文字列 B◦文字列 A の i 番目の文字と文字列 Bの j 番 目 の 文 字 が 等 し い 場 合 は， 編の j 番 目 の 文 字 の， そ れ ぞ れ 一 つ 前

集グラフで（i，j）から（i － 1，j －の文字（一つ左，または一つ上）の1）に進む。（編集グラフ上では左斜最長共通部分列の長さを基準としてめ上に進む）

考える。

◦文字列 A の i 番目の文字と文字列 B◦一つ左と一つ上の二つの最長共通部の j 番目の文字が等しくない場合は，分列の長さのうちどちらか一方が長格子 点（i － 1，j） と（i，j － 1）にい場合は，長い方がその格子点にお最長共通部分列の長さを比較し，長ける最長共通部分列の長さとなる。

い方に進む（編集グラフ上では左ま愛知大学情報メディアセンター

－ 19 －

Vol.30, No.1, 2020たは，上に進む）。なお，同じ場合は

1．「a」をそのままどちらに進んでも良いので，実装上2．「b」をそのままは上に進むことにした。

3．「i」を「b」の後に挿入

今回の例でこの手順を実行すると，以4．「c」を削除

下のような図になる。
a5．「d」を削除

bie

6．「e」をそのまま

f

7．「f」を「e」の後に挿入と な り，SES に な っ て い る こ と が 分 かる。また，この SES から編集距離は「4」←a←←bc↑d↑であることも導き出すことができる。
以上が，単純な「動的計画法」を用いた，差分検出用の最短経路探索アルゴリ←←eズムであり，このアルゴリズムを，PHP（図 3）言語を使って実装を行った。

この経路の中で斜め上に進んだ箇所の4．まとめ文字列を左上から経路を順に辿って集めると「abe」となり，最長共通部分列に今 回 は HITs の Typing 採 点 プ ロ グ ラなっていることが分かる。この場合の経ムの改良を行い，不正解個所のメッセー

路 は， 編 集 グ ラ フ で は 以 下 の よ う に なジをより具体的に，文書全体でどの部分る。に，誤字があるか，書込不足か，書込過（0，0）

abiefab

剰かといった間違いを一目で分かるようyにした。その際，文字列の差分を検出するアルゴリズムとして，前節で紹介した単純な「動的計画法」を用いるアルゴリcズムを採用した。

d

単純な「動的計画法」を用いるアルゴ

ex（5，5）（図 4）

リズムは実行時間が最長・平均ともに O（MN）となり，文字列が長くなると計算量，メモリの使用量とも膨大になってしまうという欠陥が存在する。それは，最これを解釈すると，愛知大学情報メディアセンター

短経路の探索で，編集グラフ上の全ての－ 20 －Vol.30, No.1, 2020

格子点をいったん全て辿って最長共通部

愛知大学一般教育論集，（40），25–40（2011）

分列の長さを計算し，それから経路を見［4］長谷部勝也，松井吉光，谷口正明，「HITsつけ出すという手順になっているためでにおける Word 文書の採点プログラム 2013 年ある。それは共通部分の多い文字列同士度版の開発」，愛知大学一般教育論集，（45），での比較ではとても冗長な作業となって41–53（2013）しまうからである。それを改善する方法［5］松井吉光，長谷部勝也，谷口正明，「HITsとしては，最短経路の探索範囲を絞ってにおける Word 文書の採点プログラム 2016 年

計算量とメモリの使用量を減らす方法が度版の開発」，愛知大学一般教育論集，（52），あり，それが O（ND）アルゴリズム［8］27–36（2017）

や O（NP）アルゴリズム［9］等である。

［6］松井吉光，谷口正明，「HITs における Word

ただ，HITs の Typing の問題では各行文書の採点プログラム2018年度版の開発」，愛が高々30 文字であるため，その欠陥が大知大学一般教育論集，（54），43–49（2018）

きな問題になることはほぼ想定する必要［7］長谷部勝也，松井吉光，谷口正明，「HITsはないと判断している。しかし，今後とにおける Word 文書の採点プログラム 2019 年

しては，他のより効率の良いアルゴリズ度版の開発」，愛知大学一般教育論集，（56），ムを採用することも視野にいれて，改良

31–39（2019）をして行いたいと考えている。

［8］E.W.Myers, “An O (ND) Difference
Algorithm and Its Variations”

参考文献

Algorithmica 1, 251 (1986)［1］岩田員典，功刀由紀子，齋藤毅，谷口正明，［9］Sun Wu, Udi Manber, G.Myers, W.Miller,長谷部勝也，松井吉光，古川邦之，「Excel，“An O (NP) Sequence Comparison

Word 自 動 採 点 シ ス テ ム HITs の 構 築 と 運

Algorithm”

用」，愛知大学情報メディアセンター紀要

Information Processing Letters

COM vol. 20，No. 1，2010

35, 317 (1990)［2］岩田員典，松井吉光，長谷部勝也，谷口正［10］『アルゴリズムイントロダクション「第 2明，池森均，梅垣敦紀，齋藤毅，澤田貴行，巻」アルゴリズムの設計と解析手法

土橋喜，中尾浩，西本寛，古川邦之，毛利元T．コルメン，C．ライザーソン，R．リベス昭，「情報リテラシーのための Word，Excel 自ト，C．シュタイン（浅野哲夫，岩野和生，梅動採点システムの構築と運用」，教育改革 ICT尾博司，山下雅史，和田幸一共訳）近代科学戦略大会

社

pp. 294–295（2013）［3］松井吉光，谷口正明，長谷部勝也，「HITs における Word 文書の採点プログラムの開発」，

愛知大学情報メディアセンター

第 3 版』［11］久保達彦，「diff の動作原理を知る～どのようにして差分を導き出すのか」－ 21 －

Vol.30, No.1, 2020

https://gihyo.jp/dev/column/01/prog/2011/
diff_sd200906（2019/8/23 参照）［12］「差分検出アルゴリズム三種盛りプログラ
ミング」
https://susisu.hatenablog.com/entry/2017/10/09/134032（2019/8/23 参照）［13］N. Tsuda，「diff ってなんだ」
https://gist.github.com/gurimusan/
7e554eb12f9f59880053（2019/8/23 参照）［14］文書比較（diff）アルゴリズム
http://hp.vector.co.jp/authors/VA007799/
viviProg/doc5.htm（2019/8/23 参照）［15］典型的な DP（動的計画法）のパターンを
整理 Part 1～ナップサック DP 編～

https://qiita.com/drken/items/
a5e6fe22863b7992efdb（2019/8/26 参照）

愛知大学情報メディアセンター

－ 22 －

Vol.30, No.1, 2020