# Sumire Japanese Keyboard LOUDS Trie Dictionary Architecture for Candidate Generation

> Explore Sumire's LOUDS trie dictionary architecture for efficient candidate generation. Discover how it converts readings to kanji, emoji, and symbols with constant-time prefix searches and no network needs.

- Repository: [Kazu/japanesekeyboard](https://github.com/kazumaproject/japanesekeyboard)
- Tags: architecture
- Published: 2026-03-05

---

**The Sumire Japanese keyboard implements a memory-efficient LOUDS (Level-Order Unary Degree Sequence) trie architecture that compresses dictionary data into bit vectors, enabling constant-time prefix searches to convert phonetic readings into kanji, emoji, and symbol candidates without network dependencies.**

The open-source Sumire IME ([kazumaproject/japanesekeyboard](https://github.com/kazumaproject/japanesekeyboard)) relies on a **LOUDS trie dictionary architecture** to deliver fast, offline candidate generation on Android devices. By encoding tree structures as compact bit vectors rather than pointer-heavy object graphs, the system minimizes memory footprint while maintaining the traversal speed necessary for real-time typing. This architecture processes everything from system vocabulary to emoji lookups through a unified succinct data structure pipeline.

## Core Components of the LOUDS Architecture

### LOUDS.kt - The Base Trie Structure

The foundation resides in [[`LOUDS.kt`](https://github.com/kazumaproject/japanesekeyboard/blob/main/LOUDS.kt)](https://github.com/kazumaproject/japanesekeyboard/blob/master/app/src/main/java/com/kazumaproject/markdownhelperkeyboard/converter/louds/LOUDS.kt), which stores the pure LOUDS representation using three parallel arrays:

- **`LBS`** (Level-order Unary Degree Sequence): A bit vector encoding the tree shape where each node is represented by a `0` followed by as many `1`s as it has children.
- **`labels`**: A character array holding the edge label for every node.
- **`isLeaf`**: A bit vector marking terminal nodes.

This class provides the navigation primitives required for traversal, including `firstChild()`, `traverse()`, and `commonPrefixSearch()`. The `getLetter()` method converts node indexes back to character sequences for debugging and verification.

### LOUDSWithTermId.kt - Linking to Dictionary Entries

While the base `LOUDS` class stores only structural data, [[`LOUDSWithTermId.kt`](https://github.com/kazumaproject/japanesekeyboard/blob/main/LOUDSWithTermId.kt)](https://github.com/kazumaproject/japanesekeyboard/blob/master/app/src/main/java/com/kazumaproject/markdownhelperkeyboard/converter/louds/with_term_id/LOUDSWithTermId.kt) extends the architecture by attaching a **term-ID array** (`termIdsSaved`) to each leaf node. 

This indirection layer allows the trie to return lightweight integer IDs during search operations rather than full strings. The term-ID serves as an index into separate dictionary tables (loaded as `String[]` arrays from assets), decoupling the trie's compact structure from the variable-length candidate data.

### Converter Classes - Building the Succinct Tries

The transformation from raw word lists to runtime binaries occurs in [[`Converter.kt`](https://github.com/kazumaproject/japanesekeyboard/blob/main/Converter.kt)](https://github.com/kazumaproject/japanesekeyboard/blob/master/app/src/main/java/com/kazumaproject/markdownhelperkeyboard/converter/louds/Converter.kt) and [[`ConverterWithTermId.kt`](https://github.com/kazumaproject/japanesekeyboard/blob/main/ConverterWithTermId.kt)](https://github.com/kazumaproject/japanesekeyboard/blob/master/app/src/main/java/com/kazumaproject/markdownhelperkeyboard/converter/louds/with_term_id/ConverterWithTermId.kt).

These classes walk a traditional prefix tree built from source dictionaries (system words, single-kanji, emoji, emoticons) and emit serialized `LOUDS` or `LOUDSWithTermId` instances. The conversion happens during the build process, producing `.dat` files that are bundled into the APK's assets directory and loaded at runtime via `readExternalNotCompress()`.

### AppModule - Runtime Integration and Dagger Provision

[[`AppModule.kt`](https://github.com/kazumaproject/japanesekeyboard/blob/main/AppModule.kt)](https://github.com/kazumaproject/japanesekeyboard/blob/master/app/src/main/java/com/kazumaproject/markdownhelperkeyboard/ime_service/di/AppModule.kt) handles the instantiation of trie singletons using Dagger dependency injection. For each dictionary type (`systemTangoTrie`, `systemYomiTrie`, `emojiTangoTrie`), the module:

1. Opens the pre-compiled asset stream.
2. Invokes `readExternalNotCompress()` to hydrate the LOUDS structure.
3. Creates accompanying **SuccinctBitVector** instances that provide fast `rank` and `select` operations required for constant-time child navigation.

This initialization occurs once at application startup, ensuring the IME service has immediate access to all dictionary structures during typing sessions.

## How Candidate Generation Works

The LOUDS trie dictionary architecture powers candidate generation through a seven-stage pipeline implemented primarily in [[`IMEService.kt`](https://github.com/kazumaproject/japanesekeyboard/blob/main/IMEService.kt)](https://github.com/kazumaproject/japanesekeyboard/blob/master/app/src/main/java/com/kazumaproject/markdownhelperkeyboard/ime_service/IMEService.kt):

1. **Dictionary Compilation**: Build-time tools convert raw word lists into LOUDS tries, storing them as `O(N)`-bit binary files where `N` is the number of nodes.

2. **Runtime Loading**: `AppModule` reads the compressed assets into memory, creating singleton `LOUDSWithTermId` instances shared across the application.

3. **Reading Construction**: As the user types, the IME constructs a phonetic reading string (e.g., "konn" for "こん") from key events.

4. **Prefix Search**: The system invokes `systemYomiTrie.commonPrefixSearch(reading)`, which traverses the `LBS` bit vector using `firstChild()` and `traverse()` to locate all leaf nodes that form valid prefixes of the input.

5. **Term-ID Retrieval**: For each matched leaf node, `LOUDSWithTermId` extracts the stored term ID from the `termIdsSaved` array.

6. **Candidate Resolution**: The term ID indexes into a parallel candidate array (loaded from assets like `system_word_table.dat`) to retrieve the full display string.

7. **Ranking**: Optional succinct bit vectors (`SuccinctBitVectorLBS`, `SuccinctBitVectorIsLeaf`) provide frequency-rank data, allowing the engine to prioritize high-probability candidates without linear scanning.

## Implementing LOUDS Trie Operations in Sumire

The following patterns demonstrate how the architecture is accessed within the Sumire codebase:

### Loading a LOUDS Trie from Assets

While Dagger handles this automatically in production, the manual initialization pattern reveals the binary deserialization:

```kotlin
// Load the system Yomi trie (reading → word) from bundled assets
val assetStream = context.assets.open("system_yomi_trie.dat")
val yomiTrie = LOUDSWithTermId().readExternalNotCompress(
    ObjectInputStream(BufferedInputStream(assetStream))
)

```

### Performing Prefix Searches

The `commonPrefixSearch()` method forms the core of candidate discovery, returning all dictionary entries that share the current input prefix:

```kotlin
// User has typed the reading "konn"
val reading = "konn"
val matchedNodes = yomiTrie.commonPrefixSearch(reading)

// Convert node positions to term IDs
val termIds = matchedNodes.mapNotNull { nodeStr ->
    val nodeIndex = yomiTrie.getNodeIndex(nodeStr)
    yomiTrie.getTermId(nodeIndex)  // Returns -1 if not a leaf
}.filter { it >= 0 }

```

### Resolving Candidates from Term IDs

The final step maps compact term IDs to display strings using the parallel dictionary table:

```kotlin
// wordTable loaded from "system_word_table.dat" asset
val wordTable: Array<String> = loadWordTableFromAsset()

val candidates = termIds.map { id ->
    wordTable[id]  // Direct array lookup
}

```

## Summary

- **LOUDS tries** in Sumire encode dictionary trees as compact bit vectors (`LBS`, `isLeaf`) rather than object pointers, minimizing Android memory pressure.
- **Term-ID indirection** via `LOUDSWithTermId` separates the trie structure from candidate storage, allowing the search structure to remain lightweight while supporting large dictionaries.
- **Build-time conversion** using `Converter` classes prepares optimized binary assets that load rapidly at runtime through `readExternalNotCompress()`.
- **Constant-time navigation** via `SuccinctBitVector` rank/select operations enables real-time `commonPrefixSearch()` performance for interactive typing.
- **Offline operation** is preserved because all dictionary data resides in bundled assets, requiring no network connectivity for candidate generation.

## Frequently Asked Questions

### What is a LOUDS trie and why does Sumire use it?

A LOUDS (Level-Order Unary Degree Sequence) trie is a **succinct data structure** that represents a tree using approximately two bits per node. Sumire uses this architecture because it provides the memory efficiency of compressed storage while supporting the fast traversal speeds needed for real-time Japanese input method conversion on resource-constrained mobile devices.

### How does Sumire handle multiple dictionary types within this architecture?

Sumire maintains separate `LOUDSWithTermId` instances for different dictionary categories—system words, single-kanji entities, emoji, emoticons, and symbols—each loaded as independent singletons via Dagger's `AppModule`. This modular approach allows the IME to query specific dictionaries individually or merge results depending on the current input context.

### Why does the architecture use term IDs instead of storing full strings in the trie?

Storing full candidate strings (which vary widely in length) directly within the trie structure would violate the **succinctness** principle and bloat memory usage. By storing only integer term IDs at leaf nodes and maintaining a separate `String[]` lookup table, the LOUDS structure remains uniformly compact while still providing O(1) access to complete candidate data.

### Where does the dictionary compilation happen in Sumire's build process?

The conversion from raw text dictionaries to LOUDS binary format occurs during the Gradle build process through the `Converter` and `ConverterWithTermId` classes. These tools parse the source word lists, construct temporary prefix trees, serialize them into the LOUDS bit-vector format, and output `.dat` files that are packaged into the APK's assets directory for runtime loading.