How Karukan Builds Its System Dictionary from SudachiDict Using a Double-Array Trie

Karukan constructs a read-only system dictionary by parsing Sudachi CSV files into a cost-sorted map, converting entries into a byte-sorted vector, and encoding them into a compact double-array trie using the yada crate for fast prefix matching.

The Karukan input method engine (togatoga/karukan) relies on a high-performance system dictionary to map hiragana readings to candidate kanji surface forms. This dictionary is built offline from SudachiDict CSV files and compressed into a double-array trie structure that enables millisecond-level prefix searches at runtime.

Parsing Sudachi CSV Files into a Normalized Map

The build process begins in karukan-cli/src/bin/sudachi_dict.rs, which orchestrates the ingestion of Sudachi dictionary files. The core parsing logic resides in karukan-engine/src/dict.rs within the parse_sudachi_csvs function.

Extracting Readings and Surface Forms

For each CSV line, the parser extracts the reading from column 11 (katakana) and the surface form from column 4. The reading undergoes NFKC Unicode normalization and escape sequence decoding before storage.

// karukan-engine/src/dict.rs
pub fn parse_sudachi_csvs(paths: &[PathBuf]) -> Result<HashMap<String, HashMap<String, i32>>> {
    let mut reading_map: HashMap<String, HashMap<String, i32>> = HashMap::new();
    // Iterates lines, extracts col 11 (reading) and col 4 (surface)
    // Normalizes to NFKC, decodes escapes, accumulates costs
}

Merging Duplicate Entries by Cost

Because SudachiDict may contain multiple entries for the same reading-surface pair with varying costs, the parser uses a nested HashMap<String, HashMap<String, i32>> structure. The merge_reading_maps utility retains only the minimum cost for each duplicate pair, ensuring the dictionary stores the cheapest path for any given conversion.

Converting the Map to Sorted Dictionary Entries

Once the map is consolidated, the builder transforms it into a Vec<DictEntry> where each entry represents a unique reading. This conversion happens in Dictionary::build_from_entries.

1. Entry Construction: Each reading becomes a DictEntry containing the reading string and a vector of Candidate structs (surface form + score).
2. Candidate Sorting: Candidates are sorted by ascending cost (or NLL if --model-scores is enabled).
3. Lexicographic Sorting: The entire vector is sorted by the UTF-8 byte representation of the reading—entries.sort_by(|a, b| a.reading.as_bytes().cmp(&b.reading.as_bytes()))—a prerequisite for the double-array construction algorithm.

let mut entries: Vec<DictEntry> = order
    .into_iter()
    .filter_map(|reading| {
        groups.remove(&reading).map(|surfaces| DictEntry {
            reading,
            candidates: surfaces
                .into_iter()
                .map(|surface| Candidate { surface, score: 0.0 })
                .collect(),
        })
    })
    .collect();
entries.sort_by(|a, b| a.reading.as_bytes().cmp(&b.reading.as_bytes()));

Building the Double-Array Trie Structure

With the sorted entries ready, Karukan constructs the trie using the yada crate's DoubleArrayBuilder. This step occurs in karukan-engine/src/dict.rs.

The builder requires a keyset containing tuples of byte slices and u32 indices:

let keyset: Vec<(&[u8], u32)> = entries
    .iter()
    .enumerate()
    .map(|(i, e)| (e.reading.as_bytes(), i as u32))
    .collect();

The DoubleArrayBuilder::build method consumes this keyset and emits a compact byte array representing the trie structure. This is wrapped in yada::DoubleArray<Vec<u8>> and stored alongside the entries vector in the Dictionary struct:

let trie_bytes = DoubleArrayBuilder::build(&keyset)
    .ok_or_else(|| DictError::Format("failed to build double-array trie".into()))?;
let dict = Dictionary {
    trie: DoubleArray::new(trie_bytes),
    entries,
};

The resulting structure supports exact match and prefix searches with O(m) complexity where m is the key length, while maintaining a smaller memory footprint than a standard hash map.

Serializing to Binary Format

The final stage serializes the dictionary to a .bin file via Dictionary::save. The binary format includes:

• Magic header: "KRKN" (4 bytes)
• Version: Format version number
• Trie length: Size of the double-array structure
• Trie bytes: The raw double-array data
• Entry list: Serialized as (reading_length, reading_utf8, candidate_count, surface_length, surface_utf8, score) tuples

At runtime, Dictionary::load or Dictionary::load_auto reads this header, validates the magic bytes, and reconstructs the DoubleArray and entry vector for the IME engine.

End-to-End Build Example

You can build the dictionary using the CLI tools or directly via the Rust API.

Using the CLI:

# Parse Sudachi CSV and build binary dictionary

karukan-dict build sudachi_lex.csv -o system_dict.bin

# Inspect specific readings

karukan-dict view system_dict.bin --query きょう

Using the Rust Library:

use karukan_engine::dict::Dictionary;
use std::path::Path;

// Build from Sudachi CSV (also accepts Mozc TSV format)
let dict = Dictionary::build_from_mozc_tsv(Path::new("sudachi_lex.csv"))?;

// Perform exact match lookup
if let Some(result) = dict.exact_match_search("きょう") {
    println!("Reading: {}", result.reading);
    for candidate in result.candidates {
        println!("  {} (score: {})", candidate.surface, candidate.score);
    }
}

// Persist for distribution
dict.save("system_dict.bin")?;

Summary

• Karukan parses Sudachi CSV files in karukan-engine/src/dict.rs, extracting readings (column 11) and surfaces (column 4) with NFKC normalization.
• Duplicate entries are merged by keeping the minimum cost, stored temporarily in a HashMap<String, HashMap<String, i32>>.
• Entries are sorted by byte representation before being fed into the yada crate's DoubleArrayBuilder to construct the trie.
• The binary format uses a "KRKN" magic header and stores the double-array structure alongside the candidate vectors for fast deserialization.

Frequently Asked Questions

Why does Karukan use a double-array trie instead of a hash map?

A double-array trie provides prefix search capability in O(m) time complexity (where m is the query length) while using significantly less memory than a hash map for large static key sets. This allows Karukan to efficiently support predictive text and prefix-based candidate lookup required for Japanese IME functionality.

How does Karukan handle duplicate readings with different costs from SudachiDict?

During the parsing phase in parse_sudachi_csvs, Karukan accumulates entries in a nested HashMap structure where the inner map tracks surface forms and their associated costs. The merge_reading_maps function retains only the minimum cost for each reading-surface pair, ensuring the final dictionary contains the optimal conversion path.

What is the difference between the JSON and binary dictionary formats in Karukan?

The JSON format serves as an intermediate representation used during development or when applying model-based scoring (via --model-scores). The binary format (.bin) is the production-ready format containing the compiled double-array trie and serialized entries with the "KRKN" header, optimized for fast loading and minimal memory usage at runtime.

What is the runtime complexity of lookups in the Karukan system dictionary?

Exact match lookups execute in O(m) time where m is the byte length of the reading string, proportional to the number of characters. Prefix searches traverse the trie structure with the same complexity per character, enabling efficient enumeration of all dictionary entries that share a common hiragana prefix without scanning the entire key space.

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