How Karukan Implements Romaji-to-Hiragana Conversion Using a Trie and FSM

Karukan implements romaji-to-hiragana conversion through a two-stage pipeline that combines a static trie storing conversion rules with a mutable finite-state machine converter that buffers input, resolves ambiguities via longest-prefix matching, and handles Japanese-specific edge cases like sokuon and the "n" rule.

Karukan’s input method engine relies on a sophisticated romaji-to-hiragana conversion system implemented in the karukan-engine crate. This architecture uses a prefix tree (trie) to store approximately 200 romanization rules, paired with a finite-state machine (FSM) converter that processes keystrokes incrementally while managing complex linguistic edge cases.

The Trie Data Structure for Conversion Rules

The conversion dictionary lives in karukan-engine/src/romaji/trie.rs, which defines the TrieNode structure:

pub struct TrieNode {
    pub output: Option<String>,                // hiragana when this node is terminal
    pub children: HashMap<char, TrieNode>,    // next character branches
}

The TrieNode provides two critical operations. First, insert builds the tree from the static rule list defined in rules.rs. Second, search_longest walks the tree character-by-character, remembering the last terminal node to achieve longest-prefix matching. This method returns a SearchResult containing:

• matched_len — the number of input characters matched
• output — the corresponding hiragana string
• has_continuation — a boolean indicating whether a longer match could still exist

The trie guarantees O(∣input∣) lookup complexity, enabling the converter to efficiently determine when a romaji segment is complete or when it must wait for additional input.

The FSM Converter Implementation

The stateful conversion logic resides in karukan-engine/src/romaji/converter.rs within the RomajiConverter struct:

pub struct RomajiConverter {
    trie:   TrieNode,   // the immutable rule trie
    buffer: String,     // un-converted characters awaiting disambiguation
    output: String,     // already-converted hiragana
}

The converter operates as a finite-state machine with four primary behaviors:

Buffering state — When push(ch) receives a character, it adds the lower-cased value to buffer and invokes try_convert.

Conversion state — The try_convert method queries trie.search_longest for the longest match. When found, it emits a ConversionEvent::Converted(hiragana) and removes the matched prefix from buffer.

Waiting state — If a match exists but has_continuation is true and the buffer equals the match length, the FSM emits ConversionEvent::Buffered. This prevents premature conversion of "ka" when "kya" or "kana" might still be incoming.

Special case handling — Before generic trie lookup, the converter handles edge cases (lines 70–115):

• "nn" → ん — Recognized immediately (lines 70–84)
• 'n' before a consonant — Converts to ん while leaving the following consonant in the buffer (lines 86–104)
• Double consonant — Produces a sokuon (っ) and keeps the trailing consonant for the next syllable (lines 106–112)

The continuation flag logic (lines 120–130) ensures that sequences like "ka" do not convert until a non-Japanese character follows, unless the pattern is definitive (such as "n'" or "nn"). When the first character cannot start any rule, the converter passes it through unchanged (lines 165–190).

Utility methods include flush() to empty the buffer and convert remaining characters, backspace() to remove the last character from either buffer or output, and output_katakana() to transform accumulated hiragana to katakana via hiragana_to_katakana.

Rule Generation

The static mapping of romaji to hiragana is defined in karukan-engine/src/romaji/rules.rs. The build_rules() function populates approximately 200 entries (e.g., "kya" → "きゃ") and inserts each into the trie during converter initialization. This file serves as the single source of truth for all romanization patterns, including yōon, sokuon, and special "n" handling.

Practical Usage Example

The following demonstrates the typical lifecycle: creation, incremental feeding, result extraction, and backspace handling:

use karukan_engine::romaji::converter::RomajiConverter;

// Create a fresh converter (loads the full rule set)
let mut conv = RomajiConverter::new();

// Simulate a user typing "konnnichiha"
for ch in "konnnichiha".chars() {
    conv.push(ch);          // each character is processed by the FSM
}

// The converter has already emitted the full Hiragana sentence:
assert_eq!(conv.output(), "こんにちは");

// Katakana version is available without extra work:
assert_eq!(conv.output_katakana(), "コンニチハ");

// If the user deletes the last keystroke:
let _ = conv.backspace();   // removes the trailing 'は' from output

Each call to push(ch) drives the FSM through its state transitions, buffering ambiguous input and emitting conversion events as soon as the trie determines a definitive match exists.

Summary

• Karukan implements romaji-to-hiragana conversion in the karukan-engine crate using a trie-based FSM architecture.
• The TrieNode in karukan-engine/src/romaji/trie.rs stores conversion rules and provides O(∣input∣) longest-prefix lookup via search_longest.
• The RomajiConverter in karukan-engine/src/romaji/converter.rs buffers input, uses the trie to resolve matches, and handles special cases like "nn", 'n' before consonants, and double consonants.
• The has_continuation flag prevents premature conversion of ambiguous prefixes.
• Rules are generated from karukan-engine/src/romaji/rules.rs and loaded during initialization.
• The converter supports katakana output and backspace operations without requiring external state management.

Frequently Asked Questions

How does the trie handle ambiguous romaji sequences like "ka" versus "kya"?

The search_longest method returns a has_continuation flag indicating whether the current match could extend into a longer valid sequence. When this flag is true and the buffer equals the current match length, the FSM enters a waiting state and emits ConversionEvent::Buffered, delaying conversion until the user either completes the longer sequence (e.g., "kya") or types a character that breaks the continuation.

What happens when a user types "nn" or a single "n" before a consonant?

According to lines 70–104 in converter.rs, the FSM checks for these patterns before consulting the trie. The sequence "nn" converts immediately to ん. When a single "n" appears before a consonant (excluding 'y' for yōon), the converter emits ん and leaves the following consonant in the buffer for the next syllable's conversion.

How does the converter manage double consonants for sokuon (っ)?

Lines 106–112 implement specific logic to detect double consonants (e.g., "kk", "ss"). When detected, the converter emits a sokuon (っ) and retains the second consonant in the buffer to begin the next syllable, ensuring correct segmentation of words like "katta" (かった).

Can the converter output katakana instead of hiragana?

Yes. The RomajiConverter provides the output_katakana() method, which transforms the accumulated hiragana string to katakana using the internal hiragana_to_katakana function. This conversion happens on-demand without requiring separate input processing, allowing the same keystroke stream to generate either script.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}