柔軟な入力に対応したローマ字入力のタイピングゲームを考える

はじめまして、darumakahiと申します。

今回は、ローマ字入力のタイピングゲームを作るにあたって、柔軟な入力に対応した方法を考えるのに苦労したため、記事としてまとめました。

# 柔軟な入力とは？

ローマ字入力では、同じ文章を入力するときに、複数の入力パターンが考えられます。例えば、「かっこう」という単語を入力するときには、
* kakkou
* cakkou
* kakkowu
* kaltukou …

というように、様々なパターンが入力として考えられます。そのため、入力キーの正誤判定を行うときには、複数の入力パターンをすべて考慮する必要があります。

# 素朴な方法

柔軟なキー入力を受け付けるために、問題文に対してすべての入力パターンを列挙しておいて、列挙した全パターンについて正誤判定するという方法が考えられます。この場合には、問題文（ひらがな）から、入力パターン（ローマ字）へ変換するプログラムを用意すれば、簡単に実装することができます。

1. 問題文から、すべての入力パターンを列挙する。
    * 「こっき」→ { kokki, cokki, koxtuki, koltuki, coxtuki, coltuki, koxtsuki, koltsuki, coxtsuki, coltsuki }
1. キー入力を受け取り、すべてのパターンに対して正誤判定し、当てはまらなかったパターンを除外する。
    * 入力「k」→ { **k**okki, ~~cokki,~~ **k**oxtuki, **k**oltuki, ~~coxtuki,~~ ~~coltuki,~~ **k**oxtsuki, **k**oltsuki, ~~coxtsuki,~~ ~~coltsuki~~ }

しかし、問題文が長いときには、この方法ではパフォーマンスが落ちてしまう可能性があります。なぜなら、問題文の文字列長に対して、パターンの数が指数的に増加することがあるからです。

例えば、「しゃ」という文字列は、8種類の入力パターンがあります。もし、「しゃしゃしゃしゃしゃ」という問題文があったとしたら、その入力パターンは、$8^5 = 32768$ 個になります。ここでは極端な例を出しましたが、問題文の文字列長が大きくなったときには、この方法を用いることは難しくなります。

# オートマトンを用いた方法

タイパーの白狐さんが、[この記事](https://qiita.com/Arthur_Lugh/items/8c7f32810dd330398b3d)でオートマトンを用いた方法を提案しています。この方法の概要は次の通りです。

1. あらかじめ、文字列と入力パターンの集合を辞書として保持しておく。
    * { あ：{ a } }, { い：{ i, yi } }, … , { しゃ：{ sya, sha, sixya, silya, shixya, shilya, cixya, cilya } }, …
1. 文字列の先頭3文字を切り出し、辞書に含まれているか探索する。
    a. もし含まれていれば、その文字列に対応する入力パターンをオートマトンの状態として保持する。
    b. もし含まれていなければ、先頭2文字を切り出し、辞書に含まれているか探索する。(それでも見つからなければ、先頭1文字で探索する。)

例えば、「きゃっちゃー」という問題文をオートマトンに変換する流れは、次のようになります。

1. 「きゃっ」が辞書に含まれているか探索する。→ No
1. 「きゃ」が辞書に含まれているか探索する。→ Yes
    * オートマトンの状態に、{ kya, kixya, kilya } を追加する。
1. 「っちゃ」が辞書に含まれているか探索する。→ Yes
    * オートマトンの状態に、{ ttya, ccya, ccha, ttilya, ttixya, … } を追加する。
1. 「ー」が辞書に含まれているか探索する。→ Yes
    * オートマトンの状態に、{ - } を追加する。

この方法は非常にスマートで、ほとんどのゲームの実装ではこの方法を参考に実装すると良いと思われます。しかし、この方法では、キーの入力途中において、問題文の何文字目まで入力したかが正確に把握できないという問題があります。例えば、上記の「きゃっちゃー」を例に取ると、「kyatti」と入力したときに、問題文の「きゃっち」まで入力されていますが、オートマトンでは「っちゃ」の入力でひとまとめにしているため、その点を判断することが難しくなっています。

ほとんどのタイピングゲームでは、入力済のテキストに対して色を変更することで、プレイヤーがどこまで打ったかわかるようになっています。有名なタイピングゲームである[寿司打](https://sushida.net/)や[e-typing](https://www.e-typing.ne.jp/)では、入力済のローマ字の色を変更しています。一方、私がよく遊んでいる[歌謡タイピング劇場](https://casual.hange.jp/typing/)では、入力済のローマ字だけではなく、ひらがな文に対しても色を変更しています。そのため、本手法では、歌謡タイピング劇場のようなゲームを作る際に、ひらがなの文の色の変更が難しいということになります。

# 表を用いた方法

前述の通り、同時に判断する入力パターン数を少なくしながら、問題文の何文字目まで入力したかを正確に把握する必要があります。そこで、本記事では、表を用いた方法を紹介したいと思います。

この方法の基本的な考え方は次の通りです。

* あらかじめ、文字列と入力パターンの集合を辞書として保持しておく。しかし、オートマトンの方法と異なり、キーとする文字列に対して、その文字列を**一気に打つことのできる**入力パターンのみ保持する。
    * { あ：{ a } }, { い：{ i, yi } }, … , { しゃ：{ sya, sha ~~, sixya, silya, shixya, shilya, cixya, cilya~~ } }, …
* 問題文に対して、$i$ 文字目から $j$ 文字分切り出した文字列の入力パターンを、表の $i$ 行 $j$ 列に格納する。

例）「きゃっちゃー」を表に変換する。(見やすさのため、行と列を入れ替えています。)

| $j$ ＼ $i$ | き(1) | ゃ(2) | っ(3) | ち(4) | ゃ(5) | ー(6) |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 1 | { ki }  |  { xya, lya } | { xtu, ltu, xtsu, ltsu }  |  { ti, chi } |  { xya, lya } |  { - } |
| 2 | { kya }  |  - |  { tti, cchi } |  { tya, cya, cha } | -  | -  |
| 3 |  - |  - | { ttya, ccya, ccha }  |  - | -  |  - |
| 4 |  - | -  |  - |  - |  - |  - |

* 文字の正誤判定は、次のように行う。
    * $i = 1$ から始めて、$i$ 行に含まれているパターンと一致するか判定する。
    * $i$ 行 $j$ 列に含まれているパターンの入力が終わったら、$i$ に $j$ を加算する。
    * $i$ の値が文字列長を超えたら (厳密には、文字列長+1の値になれば) 、終了する。

この方法では、同時に判断するパターンの種類数は、オートマトンを用いた方法と等しくなります。また、$i$ の値を参照することで、問題文の何文字目まで入力したかを把握することができます。

オートマトンを用いた方法と比較して、本手法の利点は次の通りです。

* 問題文の入力済文字数を知ることができる。
* 辞書に保持しておく入力パターン数を抑えることができる。
* 文末の「ん」の例外処理を行わずに済む。
    * { ん：{ nn, xn } }, …, { んか：{ nka, nca } }, … のように保持することで、同様の処理を行うことができる。

# おわりに

本記事では、柔軟な入力に対応したローマ字入力の方法をいくつか紹介しました。オートマトンを用いた方法は、白狐さんが[ライブラリ](https://github.com/WhiteFox-Lugh/RomanTypeParser)も公開されており、これからタイピングゲームを作る方にはとても有用ですが、私のように問題文の入力文字数を管理したい場合には、本記事で紹介した方法も考えてみてください。

### 参考

* [ローマ字日本語入力タイピングゲーム製作の一番めんどくさい「複数入力判定」を助ける](https://qiita.com/Arthur_Lugh/items/8c7f32810dd330398b3d)
* [タイピングガチ勢が本格的タイピングゲーム（ローマ字入力）を実装してみた](https://qiita.com/Arthur_Lugh/items/43b61877819e402c50d6)
* [歌謡タイピング劇場](https://casual.hange.jp/typing/) : 筆者おすすめのタイピングゲームです。