はじめに

タイピングソフトを作りたい人向けの記事です
丁寧な導入は省略して、理論の話をします。
プログラムが見たい人は以下のリンクから見てください。

作成するタイピングゲームの要件

半角文字とひらがなを受け付ける
ひらがなはローマ字入力のみとする
ひらがなの変換は概ねすべてを対応する(例えば「っ」を入力する方法4通り全て可能）

本題

日本語入力の嫌なところ

日本語入力は面倒くさく、面倒くさい原因は特に以下二点が挙げられます。

1つのかな文字に対して複数のローマ字が対応している
規則性が薄い

例えば、「し」というかな文字を入力するためには、"si"と"shi"の2種類があります。
「っ」(小さいつ)を入力する方法は"ltu", "xtu", "ltsu", "xtsu"の4種類があります。
このような1文字に対して複数の入力方法があれば、複数文字を同時に入力する方法もあります。
特に、「っし」という文字列は"ssi"や"sshi"と入力すれば一度に入できます。もちろん、「っ」と「し」に分けて入力することもできます。

「ざっしゅ」という文字列を入力する方法がいくつあるかご存知ですか？

一覧

zassyu
zasshu
zassixyu
zassilyu
zasshixyu
zasshilyu
zaltusyu
zaltushu
zaltusilyu
zaltusixyu
zaltushilyu
zaltushixyu
zaxtusyu
zaxtushu
zaxtusilyu
zaxtusixyu
zaxtushilyu
zaxtushixyu
zaltsusyu
zaltsushu
zaltsusilyu
zaltsusixyu
zaltsushilyu
zaltsushixyu
zaxtsusyu
zaxtsushu
zaxtsusilyu
zaxtsusixyu
zaxtsushilyu
zaxtsushixyu

なんと怒涛の20通りです。

タイピングゲームを作成するにあたって、この複数入力への対応は必須になるでしょう。

これらがなんらかの規則に則っていれば簡単に対応できたかもしれませんが、アルファベットとローマ字入力に規則はほぼないと言ってよく、残念ながら愚直に変換テーブルを作成せざるをえません。

用語設定

センテンス
タイピングゲームで入力するお題の文章を指します。
ワード
1度にローマ字からひらがなに変換できる文字列を指します。
例:「し」、「っし」、「っくぁ」など
「おかき」というひらがなを1度に変換する方法はないので、これは1ワードではない

アルゴリズム

まず、お題をタイピングゲームで使いやすくするための前処理に、
「センテンスとしてひらがなの文字列を入力すると1ワードを1つのノードとした、文字列入力の有向グラフを出力する」ようなアルゴリズムを考えます。

ワードを判定するテーブルを作成する
センテンスを頭から走査し、ワードをみつける
隣接するワード同士にエッジをはり、つなげる

以上

変換テーブルの作成

変換テーブルとは、「し」が入力されたら"si", "shi"という入力が可能、というワードとローマ字の辞書です。
このテーブルを作成すれば、ワードごとの入力方法がわかると同時に、この文字列はワードであるか？という問に答えることができます。

このテーブルの作成は、手作業で頑張りました。どの入力方法を採用するかは、wikipediaを参考にしています。
実際の変換テーブルは上GitHubリンクからソースコードを確認してください。

ワードの検索

該当部分のソースコードを引用します
余計な部分もありますが、雰囲気で読んでください。

for (int l=0, r=1; l < Sentence.Length; l++, r=l + 1) {
    edge[l]=new List<TypeWord>(); // l文字目からはじまるワードのリストを初期化
    while (r <=Sentence.Length) { // センテンス長をこえない間
        string kana_substr=Sentence[l..r]; // [l, r)の連続部分文字列を取得
        // テーブル上に存在しなければbreak
        if (TypeUtils.kana2romaList.TryGetValue(kana_substr, out string[]? val)==false) break;
        foreach (var romaji in val) {
            edge[l].Add(new TypeWord(kana_substr, romaji)); // 可能な入力方法の分だけ追加
        }
        r++;
    }
}

解説

edge[l]は、文字列の$l$番目から始まるワードのリストです。
例えば、”っし”という文字列のとき、$edge[0]$は{"っ", "っし"}という集合を持ちます(コードではリストですが)
forで各文字から始まるワードを、ワード長を1文字、2文字と増やしながら検索していきます。
文字列長を伸ばして、ワードが見つからなかったら、$l$文字目から始まるワードの検索を終えます。
これは、センテンスを$S$とすると、$S_{l..l+i}$という$i$文字の部分
文字列がワードでないならば、部分文字列$S_{l..l+i+1}$がワードであることはない、という理屈に基づいています。

$edge[l]$には、ワードの集合を持ちますので、もちろんそれぞれのワード長がわかります。
$l$文字目から始まる$n$文字のワードが入力されたら、次に入力すべきは$l+n$文字目のワードである、ということなので、これを有向グラフと見立てることで、以下のような有向グラフが完成します。

最後に

とりあえずここまでで解説を終了します。
以上の前処理を実際にどう利用しているか気になる人はページトップのリンクからソースコードを読んで見てください。
いつか続きを書きます。

タイピングのロジックを考えよう