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

> Discover how Karukan builds its system dictionary from SudachiDict with a double-array trie. Learn about efficient dictionary construction for fast prefix matching.

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

---

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

```rust
// 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.

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

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

```rust
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:

```rust
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:**

```bash

# 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:**

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