ローマ字の解析ライブラリ romaji を作った

ローマ字の解析ライブラリ @marmooo/romaji を作りました。主にタイピングの問題文として与えるひらがなをローマ字に変換したり、どこまで入力したかの確認、といった利用を想定しています。タイピングのアプリは割とたくさん作ってきた割に、ローマ字入力のタイピングはクソコードになっていたので、完璧にしました。

実装例

こんな感じで使えます。

import { Romaji } from "@marmooo/romaji";

const problem = "がっこう";
const romaji = new Romaji(problem);
romaji.input("g"); // --> true
romaji.input("j"); // --> false
romaji.input("a"); // --> true
romaji.inputedRomaji;   // --> "ga"
romaji.inputedHiragana; // --> "が"

globalThis.addEventListener("keydown", (event) => {
  if (romaji.input(event.key)) {
    if (romaji.isEnd()) {
      nextProblem();
    } else {
      correctType();
    }
  } else {
    incorrectType();
  }
});

ところで少し前にひらがな→ローマ字の変換のライブラリとして hiraroma を作ったのですが、仕組みは異なります。一般的なひらがな→ローマ字の変換では最もよく使われるヘボン式さえサポートしていれば十分です。しかしローマ字入力のタイピングではすべての変換形式に対応することが求められます。この対応は思っているより面倒で、これまで完璧に対応しているものはなかったと思います。最近ようやくこの手のライブラリが増えてきた気がしますが、実装面で納得のいくライブラリはなかったので、その辺りを軽く説明します。

タイピング用のデータ構造 (基本)

ひらがな→ローマ字の変換では、ひらがな 1-3文字ごとに 1〜30パターンの入力バリエーションがあります。 100 文字にもなると、パターンがとんでもない事になって死ぬ可能性があります。そのためすべてのバリエーションを事前生成するのは無理で、タイピングではひらがな 1-3文字ごとのパターンを保持する必要があります。パターンを生成する方法論としては、 DAG として捉える方法もありますが、形態素解析の延長線でラティスとして考えるとシンプルになります。

ローマ字入力でパターンが複雑になる条件は、実はたった 1つしかありません。前に「っ」、後ろに「ぁぃぅぇぉゃゅょ」が来た時だけです。つまり「が|っこ|う」「や|きゅ|う」「が|っきゅ|う」となるように正規表現でセグメント分割すれば、ただの配列として管理できます。あとはひらがなの部分文字列 (セグメント) からローマ字のパターンを生成するだけです。たとえば「が|っこ|う」は [[ga], [kko, cco, xtuko, ltuko], [u, wu, whu]] となります。

探索時はセグメントの内部チェックをしながら、終端に到達するまで配列を遷移します。セグメントの内部はせいぜい 30 パターン程度と事前にわかっているので、その判定処理は配列の全件探索、Double Array、Trie、その他様々なデータ構造のどれで実装してもたいした速度差は出ません。その中で少しでも速度を出そうとするなら、重要なのは一文字ごとにキャッシュすることです。探索結果をキャッシュさえしていれば一文字ごとの探索における計算量は O(1) に限りなく近づくので、より速度差はなくなります。 Trie なら 40〜50行で書けます。

以上の仕組みなら、ライブラリを拡張しようと思った時にもわかりやすいです。

特殊ルールの考慮

hiraroma のように出力をヘボン式に絞らない場合、いくつか特殊な入力方式が存在します。このへんの対応が一番面倒なところです。それなりに便利なルールとしては、たとえば (1)「にんき→ninki」のような「ん○」で n を 1回省略できるルール、 (2) 「あっっ→axxtu」「あっっぽー→apppo-」のような「っ」の連続ルールがあります。

1 は普段もそれなりに使われそうですし、なにより誤爆しやすいので記憶したいルールです。またおそらくすべての IME が標準サポートしているので考慮しました。 2 はヘボン式に直接定義はされていないと思っています。なのでヘボン式の出力は「axtuxtu」や「axtuxtupo-」が正しいと思います。 MS-IME はこの変換をデフォルトでサポートしていませんが、他のたいていの IME はサポートしている機能です。よく使われる「ｗｗｗｗｗ」だけ変換しない IME もありますが、ほぼデファクトの気はします。

ヘボン式そのものにもツッコミを始めると「まっちゃ→matcha」らしいです。しかし私のキーボードだと入力できないので「maccha」でいいのではと思っています。他にも「てぃ→t'i」もあります。こちらも私のキーボードだと入力できません。このような使えないルールは紛らわしいだけなので、私は無視しています。

タイピング用のデータ構造 (応用)

「にんき→ninki」「あっっぽー→apppo-」はどのように解析すればいいでしょうか。前者はわかりやすくて、「ん」のノードにいる時には一文字目を確定した後、次のノードの最初のアルファベットを確認する実装が必要になります。後者も「っ」ノードにいる時には一文字目を確定した後、最初のノードと同じアルファベットを入力すると次のノードに移動できるルールの実装が必要になります。これらは基礎編の実装を拡張すれば問題なく実装できます。

実際にはもう少し難しくて、「あ|っっぽ|ー」になるように分割した後、「あ|っ|っ|ぽ|ー」へさらに変換して、「ぽ→p」が促音可能であることを連続する前の「っ」に知らせます。 Trie の実装は pp を「っ」としてノードに追加して skip しながら遷移する方法と、p を「っ」としてノードに追加する方法があります。前者はひらがなの文字単位が綺麗になりますが、入力済みのローマ字を復元しようとする時に p の数が問題になります。後者はその逆の問題として最初の p で「っ」がズレる問題があります。ローマ字に寄せたほうがわかりやすいと思ったので後者を採用しています。この 2つの機能についてはオプションで OFF できるようにしておきました。

ASCII 文字列の考慮

タイピングはローマ字だけでなく ASCII 文字列も含まれる可能性があります。たとえば「あっちい!1!!!!1!」や「くぁwせdrftgyふじこlp」などがあり得るので、これもサポートしています。ローマ字の一部と言えば一部ですしね。ただ欠点もあって「aあAあ→aaAa」になるので元の文字列を復元できなくなる可能性があります。記号とひらがなの組み合わせくらいにとどめたほうが良いと思います。

データ構造に関しては、ASCII 文字列を Trie で管理するのは効率が良くないですが、どれだけ出現するかわからない ASCII 文字のために実装を増やすのもなんかなあという感じです。速度を取るなら String と Trie を切り替えながら管理するのでしょうが、そこまで頑張る必要もないと思うので、今のところすべて Trie Array で管理しています。ちなみに全角英語のチェックも面倒くさいのでしていません。ひらがな化や半角化くらいはユーザに任せて良いかなと思っています。

まとめ

あとは真面目にテストを書いてチェックすればライブラリとして完成です。データ構造もそれなりには大切ですが、これが一番大切です。 hiraroma くらいのライブラリでさえ漏れなく作るのに苦労している状態です。タイピング用のライブラリはより複雑なので、テストがいい加減だとさすがに使いづらいです。

速度に関しては、当たり前といえば当たり前なのですが、hiraroma のほうが圧倒的に高速です。 hiraroma だと SudachiDict を使ったフルテストは 1分で終わりますが、 romaji だと 9時間くらい掛かってしまいました。つまり 500倍くらい速度差があります。どちらのライブラリもさらなる高速化はなかなか難しい気がするので、このへんがアルゴリズムの重要性と言えるでしょうか。やはりタイピング以外のユースケースでは、変換をヘボン式に限定するほうが現実的と再認識しました。

jsDelivr から使いたかったので npm へ登録もしました。ただ npm → jsDelivr への反映が 2日経っても行われておらず、何かがバグっているのかと思ってハマりました。と思ったらトップページの検索が更新されていないだけでライブラリ自体は参照できることに気づき、猛烈に時間を無駄にしました。次回から気を付けよう…。

タイピングゲームの実装例が見たい人はこちらもどうぞ。

marmooo's blog

2023年8月25日金曜日