かな漢字変換の仕組みを理解したい

高校2年生の夏頃から、azooKeyというプロジェクトに少しだけ関わらせてもらっています。

そのころから、僕はazooKey-WindowsというWindows向けのIMEを作っているのですが、肝心な日本語入力のコアな部分はまったく実装したことがなかったので、 勉強という意味も込めて、かな漢字変換の仕組みを解説していきたいと思います。

Note (対象読者)

• かな漢字変換について知りたい人
• 簡単なデータ構造（リスト、辞書など）を理解している人

また、Rustを使って実装していくので、Rustをある程度理解できているとより良いです。

「読み」を扱う方法

私たち人間が「きょうはいいてんきだ」というひらがなを見たとき、脳内では瞬時に「今日はいい天気だ」という漢字交じりの文章が浮かびます。文脈や経験から、無意識に正解を選んでいるんですね。

しかし、コンピュータにとって入力された「読み」は、ただの記号の羅列です。

ここから正しい文章を作るために、コンピュータはまず 「この読みで考えられるすべての可能性」 を洗い出す必要があります。

たとえば、「きょう」と入力されただけでも、これだけの候補（異形同音語）があります。

• 今日（日付）
• 京（数詞、地名）
• 強（強弱）
• 教（宗教）
• 凶（おみくじ）
• …

これが文章全体となると、その組み合わせは天文学的な数字になってしまいます。

この膨大な候補を整理し、効率よく扱うための地図が 「ラティス（Lattice）」 です。

「ラティス」を知る

ラティス（Lattice）とは「格子」という意味です。 入力された読みに対して、 辞書にある単語をパズルのように当てはめ、それらを線でつないだグラフ構造 のことを指します。

言葉で説明するより、実際に見たほうが早いでしょう。

「きょうはいいてんきだ」という読みから、ラティスが構築される様子を見てみます。

見ての通り、左（文頭）から右（文末）へ向かって、単語のノード（点）と、それをつなぐエッジ（線）で構成された網目状のグラフができあがりました。

これがかな漢字変換の基盤となるラティスです。

最適な候補を探す

ラティスが完成しましたが、これはまだありうる候補をすべて並べたものにすぎません。

日本語入力のゴールは、このラティスのスタートからゴールまでを結ぶ無数のルートの中から、 「最も自然な一本の道」 を見つけ出すことです。
では、どうやって「自然さ」を数値化するのでしょうか？

ここで登場するのが 「スコア」 という概念です。 主に使われる指標は2つあります。

1. 単語そのもののスコア（1-gram / Unigram）

「その単語はどれくらい頻繁に使われるか？」という指標です。

たとえば、「今日」はよく使われるのでスコアが高く、「恭」は日常会話であまり使われないのでスコアが低く設定されます。

2. つながりのスコア（2-gram / Bigram）

「ある単語の次に、どの単語が来やすいか？」という指標です。

たとえば、

• 「今日」→「は」：非常によくあるつながり（スコア大）
• 「強（きょう）」→「派（は）」：あまりないつながり（スコア小）

では、具体的に図に示してみます。

このように、ノードとエッジそれぞれに点数をつけていきます。
そして、 スタートからゴールまでの合計スコアが最も高くなるルート こそが、コンピュータが導き出す「正解の変換結果」になるわけです。

全探索の壁

さて、ラティスもできたし、点数のつけ方もわかりました。あとは計算するだけです！
……と言いたいところですが、ここで現実に直面します。

単純に「すべてのルート」を計算して比較しようとすると（全探索）、どうなるでしょうか？

文章が長くなればなるほど、ラティスの分岐はネズミ算式に増え、組み合わせは爆発します。

スマホで文字を打つたびに何分も待たされたら、使い物になりませんよね。

この「計算量の爆発」を抑え、一瞬で「正解のルート」だけを見つけ出す魔法のようなアルゴリズムが必要です。

それが、次回解説する 「ビタビアルゴリズム（Viterbi Algorithm）」 です。
さらに、そもそもこのラティスを作るために「辞書から高速に単語を探す」ための仕組み、 「トライ木（Trie）」 についても触れていきます。