Token Trie

A high-performance Radix Trie implementation in Rust with sorted children for efficient binary search operations.

Features

Radix Compression: Efficient space usage through path compression
Sorted Children: All child nodes are kept sorted for O(log k) lookups where k is the branching factor
Binary Search: Fast child node lookup using binary search
Generic Keys: Works with any key type that implements Clone + Ord + PartialEq
Prefix Operations: Efficient prefix search and common prefix length calculation
Memory Safe: Written in safe Rust with comprehensive test coverage

Installation

Add this to your Cargo.toml:

[dependencies]
token_trie = "0.1.0"

Quick Start

use token_trie::Trie;

// Create a new trie
let mut trie = Trie::new();

// Insert key-value pairs
trie.insert(&['h', 'e', 'l', 'l', 'o'], "greeting");
trie.insert(&['h', 'e', 'l', 'p'], "assistance");
trie.insert(&['w', 'o', 'r', 'l', 'd'], "earth");

// Look up values
assert_eq!(trie.get(&['h', 'e', 'l', 'l', 'o']), Some(&"greeting"));
assert_eq!(trie.get(&['f', 'o', 'o']), None);

// Prefix search
let he_words = trie.keys_with_prefix(&['h', 'e']);
println!("Words starting with 'he': {:?}", he_words);

// Common prefix length
let prefix_len = trie.common_prefix_length(&['h', 'e', 'l', 'p', 'e', 'r']);
assert_eq!(prefix_len, 4); // Matches "help"

Usage with Integer Keys (Token IDs)

The trie works excellently with integer sequences, making it perfect for token-based applications:

use token_trie::Trie;

let mut token_trie = Trie::new();

// Insert token sequences
token_trie.insert(&[1, 2, 3], "sequence_a");
token_trie.insert(&[1, 2, 4], "sequence_b");
token_trie.insert(&[1, 5], "sequence_c");

// Find all sequences starting with [1, 2]
let sequences = token_trie.keys_with_prefix(&[1, 2]);
// Returns: [[1, 2, 3], [1, 2, 4]]

API Reference

Core Operations

new() - Create a new empty trie
insert(&[Key], Value) - Insert a key-value pair
get(&[Key]) -> Option<&Value> - Get value for a key
remove(&[Key]) -> Option<Value> - Remove and return value for a key
contains_key(&[Key]) -> bool - Check if key exists

Advanced Operations

keys_with_prefix(&[Key]) -> Vec<Vec<Key>> - Get all keys with given prefix
common_prefix_length(&[Key]) -> usize - Find longest common prefix length
iter() -> Vec<(Vec<Key>, &Value)> - Get all key-value pairs
keys() -> Vec<Vec<Key>> - Get all keys
len() -> usize - Number of key-value pairs
is_empty() -> bool - Check if trie is empty

Performance Characteristics

Insert: O(m) where m is the key length
Lookup: O(m + log k) where k is the average branching factor
Delete: O(m + log k)
Prefix Search: O(p + n) where p is prefix length and n is number of matching keys
Space: O(total_characters) with radix compression

Algorithm Details

This implementation uses a Radix Trie (compressed trie) with the following optimizations:

Path Compression: Nodes with single children are compressed into their parent
Sorted Children: Child nodes are maintained in sorted order
Binary Search: Child lookup uses binary search for O(log k) performance
Root Constraint: The root node always has an empty key

Examples

Run the comprehensive demo:

cargo run --example demo

Testing

The implementation includes extensive test coverage:

cargo test

Test categories:

Basic operations (insert, get, remove)
Radix compression behavior
Children ordering after all operations
Binary search efficiency
Edge cases with various key types
Random operations stress testing
Common prefix length accuracy

License

MIT License - see LICENSE file for details.

Contributing

Contributions are welcome! Please ensure all tests pass and add tests for new features.

token_trie 0.1.0