Sumire Japanese Keyboard LOUDS Trie Dictionary Architecture for Candidate Generation

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) 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/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 1s 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/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/master/app/src/main/java/com/kazumaproject/markdownhelperkeyboard/converter/louds/Converter.kt) and [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/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/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:

// 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:

// 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:

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

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