trie-kmp
0.5.0indexedLightweight library offering efficient Trie data structures with several optimized implementations. Ideal for autocomplete, spell checkers, and prefix-based applications.
34
Stars
—
Used by
dependents
—
Health
/ 100
Lightweight library offering efficient Trie data structures with several optimized implementations. Ideal for autocomplete, spell checkers, and prefix-based applications.
trie-kmp is a lightweight, efficient, and idiomatic library providing Trie data structures for Kotlin Multiplatform.
The library offers several primary implementations tailored for different needs:
CompactGenericTrie: A memory-efficient Trie that compresses non-branching paths.CompactStringTrie: Similar to CompactGenericTrie but optimized for String keys.StandardGenericTrie: A classic, standard Trie.StandardStringTrie: Similar to StandardGenericTrie but optimized for String keys.This allows developers to choose the optimal data structure for their specific use case, whether it's for autocomplete systems, spell checkers, IP routing tables, or any other prefix-based application.
repositories {
mavenCentral()
}
dependencies {
implementation("com.eygraber:trie-kmp:0.5.0")
}
Snapshots can be found here.
For any String-based use case, use the optimized trieOf / mutableTrieOf builders.
// Create a high-performance, memory-efficient compact Trie for Strings
val trie = mutableTrieOf(
"apple" to "A fruit",
"application" to "A formal request",
"apply" to "To make use of"
)
// The API is clean and direct
trie["banana"] =
value = trie[]
suggestions = trie.getAllWithPrefix()
For non-String keys, use the genericTrieOf / mutableGenericTrieOf builders.
The key type K must have a correct equals/hashCode implementation.
This is useful for cases like IP routing or bioinformatics.
Example 1: IP Routing
// Using a list of integers as a key for IP routing
val ipRouteTrie = genericTrieOf(
listOf(10, 8, 0, 0) to "Local Network A",
listOf(10, 8, 1, 0) to "Local Network B",
)
// Find all routes under the 10.8.0.0/16 prefix
val localRoutes = ipRouteTrie.getAllWithPrefix(listOf(, ))
Example 2: Bioinformatics
// Define a custom data class for DNA segments
data class DnaSegment(val base: )
geneTrie = genericTrieOf(
listOf(DnaSegment(), DnaSegment(), DnaSegment()) to ,
listOf(DnaSegment(), DnaSegment(), DnaSegment()) to ,
)
atPrefixGenes = geneTrie.getAllWithPrefix(
listOf(DnaSegment(), DnaSegment()),
)
Since Trie implements Map (and MutableTrie implements MutableMap), you can use all the standard map functions.
val trie = mutableTrieOf()
// Add a value
trie["hello"] = "A greeting"
trie["world"] = "The earth"
// Get a value
val greeting = trie["hello"] // "A greeting"
println( trie)
trie.remove()
trie.containsValue()
trie.keys
trie.values
This is the core strength of a Trie. The getAllWithPrefix() method is perfect for autocomplete suggestions.
val trie = trieOf(
"team" to 1,
"tea" to 2,
"teammate" to 3,
"ten" to 4,
)
// Get all keys that start with "tea"
val suggestions =
trie
.getAllWithPrefix("tea")
.keys
// suggestions will contain: ["tea", "team", "teammate"]
The library provides multiple implementations with different performance characteristics. The best choice depends on your specific workload.
String KeysList<Int>)| Benchmark | StandardStringTrie (nonOptimizedTrieOf) | CompactStringTrie (trieOf) | Winner |
|---|
| Creation Time (37 items) | ~2.10 µs | ~1.06 µs | CompactStringTrie |
| Prefix Search (Deeply Nested) | ~0.02 µs/op | ~0.03 µs/op | StandardStringTrie |
| Prefix Search (High Branching Factor) | ~0.03 µs/op | ~0.02 µs/op | CompactStringTrie |
| Prefix Search (Long Shared Prefix) | ~0.15 µs/op | ~0.04 µs/op | CompactStringTrie |
| Prefix Search (No Shared Prefix) | ~0.02 µs/op | ~0.01 µs/op | CompactStringTrie |
| Autocomplete | ~0.36 µs/op | ~0.36 µs/op | Tie |
| Spell Check | ~9 µs/op | ~9 µs/op | Tie |
| Removal (Deeply Nested) | ~0.02 µs/op | ~0.03 µs/op | StandardStringTrie |
| Removal (High Branching Factor) | ~0.02 µs/op | ~0.02 µs/op | Tie |
| Removal (Long Shared) | ~0.08 µs/op | ~0.04 µs/op | CompactStringTrie |
| Removal (No Shared) | ~0.02 µs/op | ~0.02 µs/op | Tie |
| Memory Usage (Node Count) | High | Low | CompactStringTrie |
| Benchmark | StandardGenericTrie (genericTrieOf) | CompactGenericTrie (compactGenericTrieOf) | Winner |
|---|
| Creation Time (37 items) | ~0.60 µs | ~0.60 µs | Tie |
| Prefix Search (Deeply Nested) | ~0.02 µs/op | ~0.02 µs/op | Tie |
| Prefix Search (High Branching Factor) | ~0.02 µs/op | ~0.03 µs/op | StandardGenericTrie |
| Prefix Search (Long Shared Prefix) | ~0.03 µs/op | ~0.03 µs/op | Tie |
| Prefix Search (No Shared Prefix) | ~0.01 µs/op | ~0.01 µs/op | Tie |
| Autocomplete | ~0.90 µs/op | ~1.00 µs/op | StandardGenericTrie |
| Spell Check | ~11 µs/op | ~13 µs/op | StandardGenericTrie |
| Removal (Deeply Nested) | ~0.02 µs/op | ~0.03 µs/op | StandardGenericTrie |
| Removal (High Branching Factor) | ~0.02 µs/op | ~0.03 µs/op | StandardGenericTrie |
| Removal (Long Shared) | ~0.02 µs/op | ~0.04 µs/op | StandardGenericTrie |
| Removal (No Shared) | ~0.01 µs/op | ~0.01 µs/op | Tie |
| Memory Usage (Node Count) | High | Low | CompactGenericTrie |
String keys, use CompactStringTrie as your default. It offers superior creation time, memory usage, and
excels at the most common prefix search scenarios (long shared prefixes and high branching).
Only consider StandardStringTrie if your application is dominated by individual lookups (get) and removals,
and you have benchmarked it to be faster for your specific data.List<E>), use StandardGenericTrie as your default. The benchmarks show it has a clear and
consistent performance advantage in nearly every category, including creation, lookups, prefix searches, and removals.
The only reason to choose CompactGenericTrie is if memory efficiency is your absolute highest priority and you
are willing to accept a performance trade-off.Surfaced from shared tags and platforms — no rankings paid for.