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

> Learn how Karukan implements romaji-to-hiragana conversion using a trie and FSM. Discover its two-stage pipeline for efficient and accurate Japanese text input.

- Repository: [Hitoshi Togasaki/karukan](https://github.com/togatoga/karukan)
- Tags: internals
- Published: 2026-07-03

---

**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`](https://github.com/togatoga/karukan/blob/main/karukan-engine/src/romaji/trie.rs), which defines the **TrieNode** structure:

```rust
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`](https://github.com/togatoga/karukan/blob/main/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`](https://github.com/togatoga/karukan/blob/main/karukan-engine/src/romaji/converter.rs) within the **RomajiConverter** struct:

```rust
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`](https://github.com/togatoga/karukan/blob/main/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:

```rust
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`](https://github.com/togatoga/karukan/blob/main/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`](https://github.com/togatoga/karukan/blob/main/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`](https://github.com/togatoga/karukan/blob/main/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`](https://github.com/togatoga/karukan/blob/main/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.