日本語かな漢字変換を実装してみた

Last updated at 2024-12-19Posted at 2024-12-19

この記事は、UniMagic Advent Calendar 2024 20日目の記事です。

日本語のかな→漢字変換を実装したよという記事です。
具体的には、VRChat(Unity)で動く、以下のような変換機能付きキーボードを作成しました。
（VRChatから離れるのでメンテできない＆コードが汚いため、公開予定はありません）

かな漢字変換

日本語は、ひらがな・カタカナ・漢字・その他記号などで構成されており、その文字数は膨大です。
それら全てをキーボード上に配置するのは現実的でありません。

そこで出てくるのが、かな漢字変換の技術です。
その名の通り、ひらがなを漢字に変換する技術ですね。

実際に使われているIME（日本語入力システム）では、先を予測する機能や、入力履歴を参照する機能などが含まれていますが、今回は最小限の機能を実装しました。

かな漢字変換は、ぱっと見簡単そうですが、実はかなり複雑な技術です。

例えば、「かそうのせかい」というひらがなの変換を考えてみましょう。

どれも「かそうのせかい」とは読めます。
しかし、多くの人が1番目の「仮想の世界」が一番自然だと感じるはずです。

では、どうやってプログラムで自然である変換結果を出力するのでしょうか？

まずは、元となるひらがなから、単語の一覧を抽出します。

例えば、「かそう」というひらがなの変換候補を全て探すには、

の合計6通りの部分文字列に対応する単語が必要です。

これを高速に行えるのが、Trie木による共通接頭辞検索です。

今回はtrie木の中でもダブル配列というデータ構造を利用します。
既に素晴らしい実装があるので、今回はそれを使わせてもらいました。
（ダブル配列を読みこんで検索する部分を、U#に移植しました）

また、単語のデータについては、mozcのものを使用しました。

共通接頭辞検索で引っ張ってきた単語を並べ、ラティスというものを構築します。

冒頭の「かそうのせかい」の例だと、こんな感じになります。
（本当はもっと単語がありますが、ここでは省略します）

左端から右端まで矢印をたどっていくと、最終的な変換候補となります。
今回は、全部で15パターンありますね。

ここに「単語の出現しやすさ」と「単語の繋がりやすさ」を表す「コスト」の情報を追加します。
（図内のコストは適当な値です）

そして、先頭から末尾までのコスト合計を求めます。
例えば、「仮想の世界」だと、「仮想(100)」「→(10)」「の(100)」「→(10)」「世界(150)」で、合計370です。
このコスト合計の小さい候補が「自然な変換候補」となります。

しかし、全通りのコストを計算していては時間が足りません。
そこで出てくるのが最短経路検索の技術です。

動的計画法の一種です。

「この単語までの最小コスト」と「コストが最小になる時の1つ前の単語への参照」を、ラティスの先頭から計算・保存していきます。

ラティスの最後までたどり着いた後、参照を前向きにたどっていけば、最小コストの変換候補が分かります。

しかし、Veterbiアルゴリズムだと、最小コストの場合しか分かりません。
かな漢字変換の場合は、2番目や3番目以降にコストが小さい変換候補も欲しくなります。
（「かそう」で変換した時、「仮想」だけ出てきても「仮装」「下層」と変換したい人は困ってしまいますよね）

N番目にコストが小さい結果まで出すことができるのがこのアルゴリズムです。
前半はVeterbiアルゴリズムと似たような感じですが、後半で優先度付きキューを使ってラティスの一番後ろから前へと探索していくのが特徴です。

ここまでのアルゴリズムを、全てU#で実装します。
なお、優先度付きキューはUdonに公開されてないので、自前で実装する必要があります。

また、Udonはとても遅いので、処理をタイムスライスするようにしています。
入力したひらがなが長くなければ、おおむね0.5秒以内に結果が返ってきます。

残念ながら、この変換ギミックを組み込めそうなキーボードが無かったため、キーボード部分も実装しました。
ローマ字からひらがなへの変換ですが、「ん」の処理と「っ」の処理を先に行い、後はローマ字の文字数順に処理していきました。

どうでもいい事ですが、「ヵ」は「lka」「xka」、「ヶ」は「lke」「xke」で入力できるということを、この処理の実装で初めて知りました。

かな漢字変換の処理は、自然言語処理でよく使われる「Mecab」の形態素解析と良く似ています。
詳しく知りたい人は、Mecabを解説しているブログ等を参照すると良いかもしれません。