変換エンジンの仕組み

このページでは、Akaza のかな漢字変換エンジンがひらがな入力から漢字かな混じり文を生成するまでの流れを説明する。

全体の流れ

入力（ひらがな列）
  ↓
1. セグメンテーション — 共通接頭辞検索で分割候補を列挙
  ↓
2. ラティス構築 — 各分割候補に漢字候補ノードを生成
  ↓
3. ビタビアルゴリズム — 前向き DP で上位 k 個の経路を計算
  ↓
4. パス抽出 — 後ろ向きトレースで k 本のパスを取り出す
  ↓
5. リランキング — 特徴量ベースの重み付きスコアで再順位付け
  ↓
出力（漢字かな混じり文の候補リスト）

1. セグメンテーション

入力ひらがな列を辞書に存在する単語単位に分割する。内部では KanaTrie（かな → 漢字候補のマッピング）を使い、各位置から始まる共通接頭辞をすべて列挙する。

例: わたしはがっこう の場合

• 位置 0 から: わ, わた, わたし, …
• 位置 9 から: は, …
• 位置 12 から: が, がっ, がっこ, がっこう, …

辞書にマッチしない位置では、1 文字ずつのフォールバック候補が自動生成される。 また、ユーザーが Shift+矢印で文節境界を指定した場合は force_ranges として渡され、その境界が強制される。

数字+かな複合セグメント

ASCII 数字がマッチした場合、数字の後に続くかなについてもトライ検索を試行し、複合セグメントを追加する。例えば入力 90ぎょう に対して:

• 個別セグメント: 90 + ぎょう
• 複合セグメント: 90ぎょう

両方を候補として保持し、Viterbi が LM スコアに基づいて最適なパスを選択する。

実装: libakaza/src/graph/segmenter.rs — Segmenter::build()

2. ラティス構築

セグメンテーション結果をもとに、ラティスグラフ（有向非巡回グラフ）を構築する。

各分割候補（読み）に対して、以下の候補ノードが生成される:

• システム辞書の漢字候補 — SKK-JISYO 等から取得（例: わたし → 私, 渡し, わたし）
• ユーザー辞書の候補 — ユーザーが登録した変換候補
• 自動生成候補 — ひらがなそのまま、カタカナ変換
• 数値変換候補 — 数字パターンの自動変換（漢数字等）
• 数字+かな複合候補 — 複合セグメント（例: 90ぎょう）に対して、かな部分を辞書検索し 90行, 90業 等の候補を生成。漢数字候補（九十行 等）も追加。LM lookup は <NUM>行/<NUM>ぎょう のように正規化してフォールバック

グラフの先頭には BOS（文頭）ノード、末尾には EOS（文末）ノードが配置される。

BOS → [わたし: 私, 渡し, ...] → [は: は, 葉, ...] → [がっこう: 学校, ...] → EOS
       [わた: 綿, ...]  →  [しは: ...] → ...

各ノードは以下の情報を持つ:

実装: libakaza/src/graph/graph_builder.rs — GraphBuilder::construct()

3. ビタビアルゴリズム（前向き DP）

ラティスグラフ上で前向き動的計画法を実行し、BOS から EOS までの最小コスト経路を求める。

コストの種類

ユニグラムコスト

単語の出現しやすさを表すコスト。加法スムージングを適用した対数確率:

unigram_cost(word) = -log₁₀((count(word) + α) / (N + α × V))

• count(word): コーパスでの出現回数
• N: 全単語の出現回数合計
• V: 語彙数
• α = 0.00001: スムージング定数

値が小さいほど（0 に近いほど）出現しやすい単語を意味する。

バイグラムコスト

直前の単語 w_{n-1} から現在の単語 w_n への遷移コスト:

bigram_cost(w_{n-1}, w_n) = -log₁₀(P(w_n | w_{n-1}))

MARISA Trie に格納されたバイグラム言語モデルから取得する。該当ペアが存在しない場合はデフォルトのフォールバックコストが使用される（未知バイグラム）。

スキップバイグラムコスト

1 語飛ばしの遷移コスト。直前ではなく 2 語前の単語 w_{n-2} と現在の単語 w_n の関係を捉える:

skip_bigram_cost(w_{n-2}, w_n)

バイグラムだけでは捉えられない、やや離れた文脈の整合性を補完する。

K-Best ビタビ

標準のビタビでは各ノードに最小コストの前ノードを 1 つだけ記録するが、K-Best ビタビでは上位 k 個のエントリを保持する。各エントリは以下を記録する:

前向き DP では、各ノードについてすべての前ノード × 前ノードの k エントリの組み合わせからコストを計算し、上位 k 個を残す。

実装: libakaza/src/graph/graph_resolver.rs — GraphResolver::resolve_k_best()

4. パス抽出

EOS ノードの k エントリから、(prev_node, prev_rank) チェーンを逆向きにたどって k 本のパスを取り出す。

重複排除

同じ分節パターン（各文節の読みの長さの列）を持つパスは、コストが低い方のみを残す。これにより、漢字候補だけが異なるパスが重複して表示されることを防ぐ。

分節パターンが異なるパスは Tab キーで切り替え、同じ分節内の漢字候補は ↑/↓ キーで切り替える。この 2 つは直交する概念である。

候補の補完

各ノード位置で同じ読みを持つ代替候補（漢字表記の異なるもの）を収集し、候補リストに含める。候補が 5 個未満の場合は、長い読みを再帰的に分割したブレークダウン候補も生成される。

5. リランキング

ビタビで得られた k 本のパスを、重み付きスコアで再順位付けする。

スコア計算式

rerank_cost = 1.0 × Σ unigram_cost
            + bigram_weight × Σ bigram_cost
            + unknown_bigram_weight × Σ unknown_bigram_cost
            + length_weight × token_count
            + skip_bigram_weight × Σ skip_bigram_cost

デフォルト重み

unigram_weight は基準スケールとして 1.0 に固定し、他の重みを相対的に探索する設計になっている。これにより探索空間を 1 次元減らし、グリッドサーチが安定する。

設計意図

ビタビは等重み（unigram + bigram の単純加算）で多様な候補を生成し、リランキングで最終選択に最適化された重みを適用する。候補生成と最終選択で最適な重みが異なるのは自然であり、この 2 段階構成により柔軟なチューニングが可能になる。

length_weight = 2.0 により、トークン数が少ない（= 長い単位でまとめた）分割が優先される。Σcost はトークン数に比例して増えるため、分節パターンが異なる候補が混ざると短い分割が不当に有利になる副作用があり、length_weight でこれを補正する。例えば「とうきょうと」→「東京都」（1トークン）が「東京と」（2トークン）より選ばれやすくなる。

各重みの詳細な評価結果はリランキング評価レポートを参照。リランキング機構全体の設計方針はリランキング設計メモを参照。

実装: libakaza/src/graph/reranking.rs — ReRankingWeights::rerank()

言語モデル

変換エンジンが使用する言語モデルは MARISA Trie 形式で格納される。

ユーザー言語モデルはプレインテキスト形式で保存され、システム言語モデルより優先して参照される。詳細はユーザーデータを参照。

言語モデルの構築パイプラインについてはデータフローを参照。

エンジンの呼び出し

変換エンジンの主要なエントリポイントは BigramWordViterbiEngine が提供する:

convert_k_best() の内部では、ラティス構築 → ビタビ → リランキングの全パイプラインが実行される。

実装: libakaza/src/engine/bigram_word_viterbi_engine.rs