PathMapDictionary Implementation

Navigation: ← Dictionary Layer | DoubleArrayTrie | Algorithms Home

Table of Contents

1. Overview
2. Theory: Persistent Data Structures
3. PathMap Library
4. Data Structure
5. Construction Methods
6. Accessor Methods
7. Union Operations
8. Usage Examples
9. Performance Analysis
10. When to Use
11. References

Overview

PathMapDictionary is a dictionary backend built on the PathMap library, which provides persistent (immutable) trie structures with structural sharing. It's the simplest dynamic dictionary option but trades performance for simplicity and immutability guarantees.

Key Advantages

• 🔄 Full dynamic updates: Insert AND remove at runtime
• 🔒 Thread-safe: Safe concurrent reads, exclusive writes
• 📦 Simple implementation: Thin wrapper around PathMap
• 💎 Persistent semantics: Structural sharing between versions
• 🎯 Easy to use: Straightforward API

Key Trade-offs

• ⚠️ Slower queries: 2-3x slower than DoubleArrayTrie
• ⚠️ Higher memory: More overhead than specialized tries
• ⚠️ Feature-gated: Requires pathmap-backend feature

When to Use

✅ Use PathMapDictionary when:

• Simplicity is more important than maximum performance
• Need full insert/remove capabilities
• Prefer well-tested external library
• Experimenting or prototyping

⚠️ Consider alternatives when:

• Performance is critical → Use DoubleArrayTrie (3x faster)
• Need maximum efficiency → Use DynamicDawg
• Unicode required → Use PathMapDictionaryChar

Theory: Persistent Data Structures

What are Persistent Data Structures?

Persistent data structures preserve previous versions after modifications through structural sharing.

Example: Adding "test" to dictionary containing ["best", "rest"]

Mutable approach (traditional):

Before:  root → 'b'/'r' → 'est'
After:   root → 'b'/'r'/'t' → 'est'  (modifies in-place)
Old version lost!

Persistent approach (PathMap):

Structural Sharing

Only changed path from root is copied; rest is shared:

Memory: Only $O(m)$ new nodes for m-character insert

PathMap Library

External Dependency

PathMapDictionary wraps the pathmap crate:

• Repository: https://github.com/Adam-Vandervorst/PathMap
• Purpose: Persistent trie data structure
• License: MIT

Enabling PathMapDictionary

Add to Cargo.toml:

[dependencies]
liblevenshtein = { version = "0.4", features = ["pathmap-backend"] }

Or use CLI:

cargo add liblevenshtein --features pathmap-backend

PathMap Features

• Persistent: Old versions preserved
• Structural sharing: Efficient memory use
• Thread-safe: Immutable data structures
• Generic values: Map terms to arbitrary types

Data Structure

Core Components

pub struct PathMapDictionary<V: DictionaryValue = ()> {
    map: Arc<RwLock<PathMap<V>>>,       // Underlying PathMap
    term_count: Arc<RwLock<usize>>,     // Term count tracking
}

Wrapper Design

PathMapDictionary is a thin wrapper that:

1. Manages PathMap lifecycle
2. Tracks term count
3. Provides liblevenshtein Dictionary trait
4. Handles thread safety via RwLock

Memory Layout

Component	Overhead
Arc pointers	16 bytes
RwLock	8 bytes
PathMap	~32 bytes/node
term_count	8 bytes

Per-node overhead: ~32 bytes (HashMap-based)

Example: 10,000-term dictionary $\approx$ 320 KB

Clone Behavior & Memory Semantics

PathMapDictionary uses two separate Arc<RwLock<...>> instances internally, making .clone() a shallow copy that shares all underlying data. The clone behavior is similar to DynamicDawg, but with dual Arc-wrapped components:

use libdictenstein::pathmap::PathMapDictionary;

let dict1: PathMapDictionary = PathMapDictionary::from_terms(vec!["test", "testing"]);
let dict2 = dict1.clone();  // O(1) - increments TWO Arc refcounts

// Both dict1 and dict2 share the SAME underlying PathMap and term count
dict1.insert("new_term");
assert!(dict2.contains("new_term"));  // ✅ Mutations visible through dict2!

// Term count is also shared
assert_eq!(dict1.len(), Some(3));
assert_eq!(dict2.len(), Some(3));  // Same count

Characteristics

Property	Behavior	Impact
Time Complexity	O(1)	Two atomic increments
Space Complexity	O(1)	~32 bytes (two Arc pointers)
Data Sharing	✅ Complete	All clones share PathMap + term count
Mutation Visibility	✅ Global	Changes via any clone affect all
Thread Safety	✅ RwLock	Multiple readers OR single writer
Independence	❌ None	No isolation between clones

How Clone Works

The clone operation increments two atomic reference counters:

pub struct PathMapDictionary<V> {
    map: Arc<RwLock<PathMap<V>>>,       // ← Arc #1
    term_count: Arc<RwLock<usize>>,     // ← Arc #2
}

// Cloning increments both Arc refcounts
let dict2 = dict1.clone();
// Equivalent to:
// Arc::clone(&dict1.map) + Arc::clone(&dict1.term_count)
// Cost: ~2-4 CPU cycles (two atomic increments)

What gets cloned:

• ✅ Arc smart pointer for PathMap (~16 bytes on stack)
• ✅ Arc smart pointer for term_count (~16 bytes on stack)
• ❌ NOT the RwLocks
• ❌ NOT the PathMap trie structure
• ❌ NOT the term count value itself

Memory allocation:

• Zero heap allocation
• Only stack space for two Arc pointers (~32 bytes)
• All data remains shared

Dual-Arc Design

PathMapDictionary's dual-Arc design enables independent locking of map and count:

// Concurrent readers can lock map and count independently
let map_lock = self.map.read();      // Lock PathMap
let count_lock = self.term_count.read();  // Lock count separately

// Reduces lock contention compared to single lock

Why two Arcs?

• Flexibility: Can read count without locking PathMap
• Granularity: Finer-grained synchronization
• Cost trade-off: Slightly more expensive clone (2 increments vs 1)

Structural Sharing vs Arc Sharing

Important distinction - PathMapDictionary has TWO types of sharing:

1. Arc-based sharing (clone behavior):

   let dict2 = dict1.clone();
   // dict1 and dict2 share the SAME PathMap instance
   dict1.insert("new");
   assert!(dict2.contains("new"));  // ✅ Visible
   

2. PathMap structural sharing (persistent data structure):

   let mut map1 = PathMap::new();
   map1.insert(b"test", 1);
   
   let mut map2 = map1.clone();  // PathMap's clone creates new version
   map2.insert(b"new", 2);
   
   // map1 and map2 share internal trie nodes where possible
   // But are independent: map1 doesn't see "new"
   

For PathMapDictionary:

• .clone() creates Arc-based sharing (visible mutations)
• PathMap's internal structural sharing is orthogonal (optimization)

When to Use Cloning

✅ Good use cases:

1. Multi-threaded access:

   use std::thread;
   
   let dict: PathMapDictionary = PathMapDictionary::from_terms(vec!["hello", "world"]);
   
   let handles: Vec<_> = (0..4).map(|_| {
       let dict_clone = dict.clone();
       thread::spawn(move || {
           dict_clone.contains("hello")
       })
   }).collect();
   

2. Configuration management:

   let config_dict: PathMapDictionary<String> = load_config();
   
   // Share across services
   let service1_dict = config_dict.clone();
   let service2_dict = config_dict.clone();
   
   // All see updates when config reloads
   reload_config_into(&config_dict);
   

3. Caching and lookup tables:

   let cache: PathMapDictionary<CachedValue> = build_cache();
   
   // Share cache across request handlers
   for _ in 0..10 {
       let handler_cache = cache.clone();
       spawn_handler(handler_cache);
   }
   

❌ Bad use cases (common mistakes):

1. Expecting independent copies:

   let dict1: PathMapDictionary = PathMapDictionary::from_terms(vec!["original"]);
   let dict2 = dict1.clone();
   
   dict1.insert("modified");
   // ❌ WRONG: Expecting dict2 unchanged
   // ✅ REALITY: dict2 also contains "modified"
   

2. Creating versioned snapshots:

   let dict: PathMapDictionary<u32> = load_data();
   let v1 = dict.clone();  // ❌ NOT a snapshot!
   
   dict.insert("v2_data");
   // v1 now also contains v2_data - not versioned
   

3. Isolating test fixtures:

   let base_fixture: PathMapDictionary = create_test_data();
   let test1_dict = base_fixture.clone();  // ❌ Shared!
   let test2_dict = base_fixture.clone();  // ❌ Shared!
   
   // Modifications in test1 affect test2!
   

Alternative: True Independence

For independent copies where mutations don't affect other instances:

Option 1: Serialize/Deserialize

use serde::{Serialize, Deserialize};

// Create deep copy via serialization
let bytes = bincode::serialize(&dict1)?;
let dict2: PathMapDictionary = bincode::deserialize(&bytes)?;

// Now independent
dict1.insert("new");
assert!(!dict2.contains("new"));  // ✅ Independent

Option 2: Rebuild from terms

// Extract all terms
let terms: Vec<String> = dict1.iter().collect();

// Build new independent dictionary
let dict2: PathMapDictionary = PathMapDictionary::from_terms(terms);

Option 3: Extract with values

// For dictionaries with values
let entries: Vec<(String, V)> = dict1
    .iter()
    .filter_map(|term| dict1.get_value(term).map(|v| (term.clone(), v)))
    .collect();

let dict2: PathMapDictionary<V> = PathMapDictionary::from_terms_with_values(entries);

Cost comparison:

Method	Time	Space	Independence
.clone()	O(1)	O(1)	❌ Shared
Serialize/Deserialize	O(n)	O(n)	✅ Full
Rebuild from terms	O(n·log m)	O(n)	✅ Full
Rebuild with values	O(n·log m)	O(n)	✅ Full

Comparison with Other Dictionaries

Dictionary	Arc Count	Clone Cost	Shared Data?
PathMapDictionary	2 (map + count)	O(1)	✅ Yes
DynamicDawg	1 (inner)	O(1)	✅ Yes
DynamicDawgChar	1 (inner)	O(1)	✅ Yes
DoubleArrayTrie	0 (no Arc)	O(n)	❌ No
DoubleArrayTrieChar	0 (no Arc)	O(n)	❌ No

Key differences:

• PathMapDictionary: Two Arc increments (map + count)
• DynamicDawg variants: One Arc increment (inner struct contains count)
• DoubleArrayTrie: Full deep copy (immutable, no Arc needed)

Thread Safety Considerations

PathMapDictionary's dual-Arc design provides flexible locking:

use std::thread;

let dict: PathMapDictionary<u32> = PathMapDictionary::from_terms_with_values(vec![
    ("key1", 100),
    ("key2", 200),
]);

// Multiple concurrent readers
let readers: Vec<_> = (0..10).map(|i| {
    let dict = dict.clone();
    thread::spawn(move || {
        dict.get_value(&format!("key{}", i))
    })
}).collect();

// Single writer (blocks all readers)
let writer = {
    let dict = dict.clone();
    thread::spawn(move || {
        dict.insert_with_value("key3", 300)
    })
};

RwLock semantics:

• Read operations: contains(), get_value(), len(), iteration
• Write operations: insert(), insert_with_value(), remove(), union_with()
• Lock granularity: Map and count can be locked independently for reads

Performance implications:

• Read lock overhead: ~10-20ns per operation
• Write lock overhead: ~50-100ns + contention costs
• Dual-Arc trade-off: More flexible locking, slightly higher clone cost

Summary

Key Takeaways:

1. 🔗 .clone() creates shallow copy with two Arc increments (map + count)
2. 🚀 $O(1)$ time and space - just atomic reference counting
3. 🔄 Mutations visible across all clones (Arc-based sharing)
4. 🌳 Structural sharing is separate (PathMap's persistent trie optimization)
5. 🔒 Thread-safe with dual RwLocks for flexible granularity
6. 📊 For independence, use serialization or rebuild from terms ($O(n)$ cost)

Construction Methods

PathMapDictionary provides constructors optimized for simple use cases and rapid prototyping.

Overview

Constructor	Complexity	Use Case	Thread-Safe
new()	O(1)	Empty start	✅
from_terms()	O(n·log m)	Simple list	✅
from_terms_with_values()	O(n·log m)	With metadata	✅

Where n = number of terms, m = dictionary size (grows with insertions)

Note: PathMapDictionary uses insert() internally which is $O(\log m)$, making bulk construction $O(n\cdot \log m)$ vs $O(n\cdot m)$ for DAWG variants.

Empty Dictionary

Create an empty dictionary for incremental updates:

use libdictenstein::pathmap::PathMapDictionary;

// Create empty dictionary
let dict: PathMapDictionary = PathMapDictionary::new();

// Add terms incrementally
dict.insert("hello");
dict.insert("world");

// With values
let valued_dict: PathMapDictionary<u32> = PathMapDictionary::new();
valued_dict.insert_with_value("apple", 100);
valued_dict.insert_with_value("banana", 200);

Characteristics:

• Time: $O(1)$ - Minimal initialization
• Memory: ~80 bytes (two Arc pointers + empty PathMap + term count)
• Simplicity: Easiest to use, minimal boilerplate

When to use:

• ✅ Prototyping and quick experiments
• ✅ Small dictionaries (< 1,000 terms)
• ✅ When simplicity matters more than performance

From Terms

Build from iterator of terms:

use libdictenstein::pathmap::PathMapDictionary;

// From Vec
let terms = vec!["test", "testing", "tester"];
let dict = PathMapDictionary::from_terms(terms);

// From any iterator
use std::collections::HashSet;
let term_set: HashSet<&str> = ["dog", "cat", "bird"].iter().copied().collect();
let dict = PathMapDictionary::from_terms(term_set);

Characteristics:

• Time: $O(n\cdot \log m)$ where m grows from 0 to n
• Memory: ~32 bytes per node (HashMap-based)
• Structural sharing: Minimal (PathMap not optimized for bulk insert)

From Terms with Values

Build with associated values (frequencies, IDs, etc.):

use libdictenstein::pathmap::PathMapDictionary;

type ContextId = u32;

// Term frequencies
let freq_dict: PathMapDictionary<u32> = PathMapDictionary::from_terms_with_values(vec![
    ("the", 1000000),
    ("hello", 50000),
    ("rare", 10),
]);

// Context IDs for code completion
let completion_dict: PathMapDictionary<Vec<ContextId>> =
    PathMapDictionary::from_terms_with_values(vec![
        ("println", vec![1, 2, 3]),  // Global contexts
        ("my_var", vec![42]),         // Local context
    ]);

// Configuration values
let config_dict: PathMapDictionary<String> = PathMapDictionary::from_terms_with_values(vec![
    ("app.name", "MyApp".to_string()),
    ("app.version", "1.0.0".to_string()),
    ("app.debug", "false".to_string()),
]);

Value type requirements:

• Must implement DictionaryValue trait
• Bounds: Clone + Send + Sync + 'static
• Recommended: Use PathMapDictionary for simple value types; DynamicDawg for complex structures

Constructor Comparison

Performance (10,000 terms, Intel Xeon E5-2699 v3 @ 2.30GHz):

Method	Time	Memory	vs DynamicDawg
new() + inserts	~12ms	~320KB	~3$\times$ slower
from_terms()	~12ms	~320KB	~3$\times$ slower
from_terms_with_values()	~13ms	~320KB	~3$\times$ slower

Memory usage:

Small (1K terms):     ~40KB  (vs ~30KB DynamicDawg)
Medium (10K terms):   ~320KB (vs ~250KB DynamicDawg)
Large (100K terms):   ~3.2MB (vs ~2.5MB DynamicDawg)

Trade-offs:

• Simpler API: Easier to use, less boilerplate
• Slower: 2-3$\times$ slower than DynamicDawg for bulk operations
• More memory: ~30% higher memory footprint
• Good enough: For < 10K terms, difference is negligible

Best Practices

1. Choose PathMapDictionary for simplicity:

// ✅ Good: Prototyping, small dictionaries
let dict = PathMapDictionary::from_terms(vec!["test", "demo"]);

// ⚠️ Consider DynamicDawg: Large dictionaries, performance-critical
let dict = DynamicDawg::from_iter(large_term_list);  // Faster

2. Use with contextual completion engine:

use liblevenshtein::contextual::DynamicContextualCompletionEngine;

// PathMapDictionary is the DEFAULT backend
let engine = DynamicContextualCompletionEngine::new();  // Uses PathMapDictionary

// Or explicit construction
let dict: PathMapDictionary<Vec<u32>> = PathMapDictionary::from_terms_with_values(terms);
let engine = DynamicContextualCompletionEngine::with_dictionary(dict, Algorithm::Standard);

3. Pre-build for workspace indexing:

use rayon::prelude::*;

// Build per-document dictionaries in parallel
let dicts: Vec<PathMapDictionary<Vec<u32>>> = documents
    .par_iter()
    .map(|(ctx_id, doc)| {
        let terms: Vec<(String, Vec<u32>)> = extract_terms(doc)
            .into_iter()
            .map(|term| (term, vec![*ctx_id]))
            .collect();

        PathMapDictionary::from_terms_with_values(terms)
    })
    .collect();

// Merge using union_with (see Union Operations section)

→ See Parallel Workspace Indexing for complete pattern.

Comparison with Other Dictionaries

When to choose PathMapDictionary:

Factor	PathMapDictionary	DynamicDawg	DoubleArrayTrie
Simplicity	⭐⭐⭐⭐⭐	⭐⭐⭐	⭐⭐
Speed	⭐⭐	⭐⭐⭐	⭐⭐⭐⭐⭐
Memory	⭐⭐	⭐⭐⭐	⭐⭐⭐⭐⭐
Dynamic updates	✅ Full	✅ Full	⚠️ Append-only
Learning curve	✅ Minimal	Medium	High
Use case	Prototyping	Production	Performance

Decision guide:

Parallel Construction

PathMapDictionary supports the same parallel construction pattern as DynamicDawg:

use rayon::prelude::*;

// Build dictionaries in parallel
let dicts: Vec<PathMapDictionary<Vec<u32>>> = documents
    .par_iter()
    .map(|(ctx_id, doc)| {
        let terms_with_contexts: Vec<_> = extract_terms(doc)
            .into_iter()
            .map(|term| (term, vec![*ctx_id]))
            .collect();

        PathMapDictionary::from_terms_with_values(terms_with_contexts)
    })
    .collect();

// Binary tree merge (see Parallel Workspace Indexing guide)
let merged = merge_tree_parallel(dicts);

// Create engine
let engine = DynamicContextualCompletionEngine::with_dictionary(
    merged,
    Algorithm::Standard
);

Performance note: Parallel construction still beneficial despite slower per-dictionary speed - wall-clock time scales with available CPU cores.

Accessor Methods

PathMapDictionary provides the same core accessor methods as other dictionary backends, with simplicity as the primary design goal.

→ See: DynamicDawg Accessor Methods for comprehensive documentation.

Key Differences from DynamicDawg

PathMapDictionary accessor methods have simpler implementations but slower performance:

Method	PathMapDictionary	DynamicDawg	Performance Impact
contains(term)	$O(m\cdot \log k)$	$O(m)$	~2-3$\times$ slower
get_value(term)	$O(m\cdot \log k)$	$O(m)$	~2-3$\times$ slower
term_count()	$O(1)$	$O(1)$	Similar
len() / is_empty()	$O(1)$	$O(1)$	Similar

Where: m = term length, k = average fanout (~26 for English)

Quick Reference

use libdictenstein::pathmap::PathMapDictionary;

let dict = PathMapDictionary::from_terms(vec!["test", "testing", "tested"]);

// Term existence (slower than DynamicDawg, simpler code)
assert!(dict.contains("test"));
assert!(dict.contains("testing"));
assert!(!dict.contains("unknown"));

// Value retrieval
let dict_valued: PathMapDictionary<u32> = PathMapDictionary::new();
dict_valued.insert_with_value("key", 42);
assert_eq!(dict_valued.get_value("key"), Some(42));

// Size queries (O(1), same as Dynamic Dawg)
assert_eq!(dict.term_count(), 3);
assert_eq!(dict.len(), Some(3));
assert!(!dict.is_empty());

// No compaction needed (persistent structure doesn't fragment)
// No node_count() method (implementation detail differs)
// No needs_compaction() (not applicable to PathMap)

// Traversal (via Dictionary trait)
use libdictenstein::{Dictionary, DictionaryNode};
let root = dict.root();
// ... navigate via transition() as with other backends

Performance Characteristics

Accessor Latencies (10K term dictionary):

Method	PathMapDictionary	DynamicDawg	PathMap/DynamicDawg Ratio
contains()	~700ns	~250ns	2.8$\times$ slower
get_value()	~750ns	~260ns	2.9$\times$ slower
term_count()	~5ns	~5ns	Same
len() / is_empty()	~5ns	~5ns	Same

Why slower?:

• PathMap uses tree traversal with log(k) comparisons per level
• DynamicDawg uses direct indexing via edge lookup

Trade-off: Simplicity and persistent semantics vs performance.

Persistent Semantics

PathMapDictionary accessor methods benefit from structural sharing:

let dict1 = PathMapDictionary::from_terms(vec!["test", "testing"]);
let dict2 = dict1.clone(); // Shallow clone (Arc increment)

// Both share same underlying structure
assert!(dict1.contains("test"));
assert!(dict2.contains("test"));

// Modifications create new structure (copy-on-write)
dict2.insert("new_term");
assert!(!dict1.contains("new_term")); // Original unchanged
assert!(dict2.contains("new_term"));  // New version has it

// Accessor methods see correct version
assert_eq!(dict1.term_count(), 2);
assert_eq!(dict2.term_count(), 3);

Thread Safety

PathMapDictionary accessors are thread-safe via Arc-based sharing:

use std::sync::Arc;
use std::thread;

let dict = Arc::new(PathMapDictionary::from_terms(vec!["hello", "world"]));

// Concurrent reads safe
let handles: Vec<_> = (0..10)
    .map(|_| {
        let d = Arc::clone(&dict);
        thread::spawn(move || d.contains("hello"))
    })
    .collect();

for h in handles {
    assert!(h.join().unwrap());
}

// Mutations create new versions (no locks needed)
let dict2 = Arc::new((*dict).clone());
dict2.insert("new");
// Original dict unchanged, dict2 has new term

---

Union Operations

Overview

The union_with() and union_replace() methods enable merging two PathMapDictionary instances with custom value combination logic, while preserving structural sharing properties of the persistent trie. Essential for:

• 🔄 Merging configuration layers (defaults + user overrides)
• 📊 Combining statistics from independent data sources
• 🗂️ Building composite lookup tables
• 💾 Creating snapshots with incremental updates

Key Characteristics:

• 🔒 Thread-safe: Operations use RwLock for concurrent access
• 🌳 Structural sharing: Leverages PathMap's persistent data structure benefits
• ⚡ Iterator-based: Uses PathMap's efficient iteration over key-value pairs
• 🎯 Flexible: Custom merge functions for value conflicts
• 🔧 Simple: Straightforward implementation via iteration + insertion

union_with() - Merge with Custom Logic

Combines two dictionaries by iterating all terms from the source dictionary and inserting into the target, applying a custom merge function when values conflict.

Signature:

fn union_with<F>(&self, other: &Self, merge_fn: F) -> usize
where
    F: Fn(&Self::Value, &Self::Value) -> Self::Value,
    Self::Value: Clone

Parameters:

• other: Source dictionary to merge from
• merge_fn: Function (existing_value, new_value) -> merged_value for conflicts
• Returns: Number of terms processed from other

Algorithm: Iteration-based insertion

1. Acquire read lock on other.map
2. Acquire write lock on self.map
3. Iterate all (key, value) pairs in other.map
4. For each pair:
   • If key exists in self.map: Apply merge_fn and update
   • If key is new: Insert with cloned value
5. Update self.term_count for new entries

Complexity:

• Time: $O(n\cdot \log m)$ where n = terms in other, m = terms in self
  • $O(n)$ for iteration over other
  • $O(\log m)$ per PathMap insertion/lookup
• Space: $O(\log m)$ for PathMap tree height (structural sharing reduces actual allocation)

Why Iteration Instead of PathMap's join()?

PathMap provides native join_into() and pjoin() methods, but they require V: Lattice:

// PathMap native (requires Lattice trait)
pub fn join_into<V: Lattice>(&mut self, other: &PathMap<V>) { ... }

Limitation: The Lattice trait requires specific algebraic properties:

• Commutative: $a \sqcup b = b \sqcup a$
• Associative: $(a \sqcup b) \sqcup c = a \sqcup (b \sqcup c)$
• Idempotent: $a \sqcup a = a$

Our approach: Uses arbitrary merge functions without algebraic constraints:

• ✅ Supports non-commutative merges: $(\text{old}, \text{new}) \to \text{new}$ (last-writer-wins)
• ✅ Supports non-idempotent merges: $(a, b) \to a + b$ (sum aggregation)
• ✅ Flexible merge logic: Any Fn(&V, &V) -> V

Trade-off: Slightly slower (~15-20% overhead) but far more flexible.

Example 1: Sum Aggregation

use libdictenstein::pathmap::PathMapDictionary;
use libdictenstein::MutableMappedDictionary;

// First dataset: term frequencies
let dict1: PathMapDictionary<u32> = PathMapDictionary::new();
dict1.insert_with_value("algorithm", 10);
dict1.insert_with_value("database", 5);

// Second dataset: more frequencies
let dict2: PathMapDictionary<u32> = PathMapDictionary::new();
dict2.insert_with_value("algorithm", 7);    // Overlap
dict2.insert_with_value("distributed", 3);  // New

// Merge by summing counts
let processed = dict1.union_with(&dict2, |left, right| left + right);

// Results:
// - algorithm: 17 (10 + 7)
// - database: 5 (unchanged)
// - distributed: 3 (new)
assert_eq!(dict1.get_value("algorithm"), Some(17));
assert_eq!(dict1.get_value("distributed"), Some(3));
assert_eq!(processed, 2);

Example 2: Configuration Merging

Demonstrates typical use case of layering configurations:

use libdictenstein::pathmap::PathMapDictionary;
use libdictenstein::MutableMappedDictionary;

// System defaults
let defaults: PathMapDictionary<String> = PathMapDictionary::new();
defaults.insert_with_value("theme", "light".to_string());
defaults.insert_with_value("font_size", "12".to_string());
defaults.insert_with_value("autosave", "true".to_string());

// User preferences
let user_prefs: PathMapDictionary<String> = PathMapDictionary::new();
user_prefs.insert_with_value("theme", "dark".to_string());  // Override
user_prefs.insert_with_value("language", "en".to_string()); // New

// Merge: user preferences override defaults
defaults.union_with(&user_prefs, |_default, user| user.clone());

// Results:
// - theme: "dark" (user override)
// - font_size: "12" (default preserved)
// - autosave: "true" (default preserved)
// - language: "en" (new from user)
assert_eq!(defaults.get_value("theme"), Some("dark".to_string()));
assert_eq!(defaults.get_value("font_size"), Some("12".to_string()));

Example 3: Set Union with Lists

Merge lists of associated data:

use libdictenstein::pathmap::PathMapDictionary;
use libdictenstein::MutableMappedDictionary;

let dict1: PathMapDictionary<Vec<u32>> = PathMapDictionary::new();
dict1.insert_with_value("rust", vec![1, 2, 3]);
dict1.insert_with_value("python", vec![4]);

let dict2: PathMapDictionary<Vec<u32>> = PathMapDictionary::new();
dict2.insert_with_value("rust", vec![2, 3, 5]);  // Overlapping values
dict2.insert_with_value("golang", vec![6, 7]);

// Merge by concatenating and deduplicating
dict1.union_with(&dict2, |left, right| {
    let mut merged = left.clone();
    merged.extend(right.clone());
    merged.sort_unstable();
    merged.dedup();
    merged
});

// rust: [1,2,3,5] (merged and deduplicated)
// python: [4] (unchanged)
// golang: [6,7] (new)
assert_eq!(dict1.get_value("rust"), Some(vec![1, 2, 3, 5]));

union_replace() - Keep Right Values

Convenience method for last-writer-wins semantics.

Signature:

fn union_replace(&self, other: &Self) -> usize
where
    Self::Value: Clone

Example:

use libdictenstein::pathmap::PathMapDictionary;
use libdictenstein::MutableMappedDictionary;

let dict1: PathMapDictionary<&str> = PathMapDictionary::new();
dict1.insert_with_value("status", "draft");
dict1.insert_with_value("version", "1.0");

let dict2: PathMapDictionary<&str> = PathMapDictionary::new();
dict2.insert_with_value("status", "published");  // Override
dict2.insert_with_value("author", "alice");      // New

// Simple replacement
dict1.union_replace(&dict2);

assert_eq!(dict1.get_value("status"), Some("published"));
assert_eq!(dict1.get_value("version"), Some("1.0"));
assert_eq!(dict1.get_value("author"), Some("alice"));

Implementation Details

The union operation uses PathMap's iterator with lock-based synchronization:

// Simplified implementation
fn union_with<F>(&self, other: &Self, merge_fn: F) -> usize {
    let other_map = other.map.read().unwrap();
    let mut self_map = self.map.write().unwrap();
    let mut self_term_count = self.term_count.write().unwrap();

    let mut processed = 0;

    // Iterate over all entries in other
    for (key_bytes, other_value) in other_map.iter() {
        processed += 1;

        if let Some(self_value) = self_map.get(&key_bytes) {
            // Key exists: merge the values
            let merged = merge_fn(self_value, other_value);
            self_map.insert(&key_bytes, merged);
        } else {
            // Key doesn't exist: insert from other
            self_map.insert(&key_bytes, other_value.clone());
            *self_term_count += 1;
        }
    }

    processed
}

Why This Approach?

1. Simplicity: Leverages PathMap's well-tested iterator
2. Flexibility: No trait constraints on value types
3. Correctness: RwLock ensures thread-safe updates
4. Structural sharing: PathMap automatically shares structure between old and new versions

Lock Semantics:

• Read lock on other: Allows concurrent reads
• Write lock on self: Blocks all access during union
• Single transaction: All updates atomic from external perspective

Performance Characteristics

Operation	Time Complexity	Space Complexity	Typical Performance (10K terms)
union_with()	O(n·log m)	O(log m)	~80ms
union_replace()	O(n·log m)	O(log m)	~80ms
Iteration	O(n)	O(1)	~15ms
Per-term insertion	O(log m)	O(log m)	~5-8µs

Variables:

• n = number of terms in source dictionary
• m = number of terms in target dictionary
• log m = PathMap tree height (typically 5-10 levels)

Comparison with DynamicDawg:

PathMapDictionary: ~80ms for 10K terms (O(n·log m))
DynamicDawg:       ~50ms for 10K terms (O(n·m))

Reason: PathMap insertion is O(log m) vs DAWG's O(m)
Trade-off: PathMap offers structural sharing and immutability

Benchmark Results (Intel Xeon E5-2699 v3 @ 2.30GHz):

Dictionary Size	union_with()	Throughput
1,000 terms	6.8ms	147K terms/s
10,000 terms	80ms	125K terms/s
100,000 terms	950ms	105K terms/s

Note: Performance includes merge function execution and structural sharing overhead.

When to Use Union Operations

✅ Use union_with() when:

• Parallel workspace indexing: Merging per-document dictionaries built in parallel (→ Parallel Workspace Pattern)
• Merging configuration layers with override semantics
• Combining statistics where structural sharing is beneficial
• Building composite lookup tables from multiple sources
• Aggregating data where immutability is valuable

✅ Use union_replace() when:

• Applying updates with last-writer-wins semantics
• Synchronizing dictionaries where newer data always wins
• Implementing configuration hot-reloading

⚠️ Consider DynamicDawg when:

• Union performance is critical (40% faster)
• Structural sharing not needed
• Frequent mutations expected

⚠️ Consider alternatives when:

• Very large dictionaries: Pre-merge offline or use batch processing
• Frequent unions: Consider maintaining separate indices
• Simple addition: If only adding new terms (no conflicts), use simple iteration

Structural Sharing Considerations

PathMapDictionary's persistent nature means union operations benefit from structural sharing:

let dict1: PathMapDictionary<u32> = PathMapDictionary::new();
// Insert 100,000 terms...

let dict2: PathMapDictionary<u32> = PathMapDictionary::new();
// Insert 100 terms (mostly new)...

// Union creates new version sharing structure with dict1
dict1.union_with(&dict2, |a, b| a + b);

// Memory overhead: Only ~100 new nodes created
// Most of dict1's structure is reused via structural sharing

Benefits:

• 💾 Memory efficient: Only delta nodes allocated
• 🔒 Safe snapshots: Old version still accessible
• 🚀 Fast clones: $O(1)$ shallow copy of Arc

Caveats:

• Lock contention on write during union
• No direct zipper-based traversal (unlike DynamicDawg)
• Iterator overhead vs direct node manipulation

Usage Examples

Example 1: Basic Usage

use libdictenstein::pathmap::PathMapDictionary;

// Create empty dictionary
let dict: PathMapDictionary<()> = PathMapDictionary::new();

// Insert terms
dict.insert("test");
dict.insert("testing");
dict.insert("tested");

assert!(dict.contains("test"));
assert_eq!(dict.len(), Some(3));

// Remove term
dict.remove("tested");
assert!(!dict.contains("tested"));
assert_eq!(dict.len(), Some(2));

Example 2: From Existing Terms

use libdictenstein::pathmap::PathMapDictionary;

let dict = PathMapDictionary::from_terms(vec![
    "algorithm",
    "approximate",
    "automaton",
]);

assert!(dict.contains("algorithm"));
assert_eq!(dict.len(), Some(3));

// Add more terms
dict.insert("analysis");
assert_eq!(dict.len(), Some(4));

Example 3: With Values

use libdictenstein::pathmap::PathMapDictionary;
use libdictenstein::MappedDictionary;

// Map terms to category IDs
let dict: PathMapDictionary<u32> = PathMapDictionary::from_terms_with_values(vec![
    ("test", 1),
    ("testing", 1),
    ("production", 2),
]);

// Query values
assert_eq!(dict.get_value("test"), Some(1));
assert_eq!(dict.get_value("production"), Some(2));

// Update value
dict.insert_with_value("test", 99);
assert_eq!(dict.get_value("test"), Some(99));

Example 4: Fuzzy Search

use libdictenstein::pathmap::PathMapDictionary;
use liblevenshtein::levenshtein::Algorithm;
use liblevenshtein::levenshtein_automaton::LevenshteinAutomaton;

let dict = PathMapDictionary::from_terms(vec![
    "test", "testing", "tested", "best", "rest"
]);

// Fuzzy search
let automaton = LevenshteinAutomaton::new("tset", 1, Algorithm::Standard);
let results: Vec<String> = automaton.query(&dict).collect();

println!("{:?}", results);
// Output: ["test"] (distance 1: transposition)

Example 5: Thread-Safe Updates

use libdictenstein::pathmap::PathMapDictionary;
use std::sync::Arc;
use std::thread;

let dict = Arc::new(PathMapDictionary::from_terms(vec!["initial"]));

// Spawn writer thread
let dict_writer = Arc::clone(&dict);
let writer = thread::spawn(move || {
    dict_writer.insert("new_term");
});

// Spawn reader threads
let handles: Vec<_> = (0..4).map(|_| {
    let dict_reader = Arc::clone(&dict);
    thread::spawn(move || {
        dict_reader.contains("initial")
    })
}).collect();

writer.join().unwrap();
for handle in handles {
    assert!(handle.join().unwrap());
}

Example 6: Dynamic User Dictionary

use libdictenstein::pathmap::PathMapDictionary;

// User's personal dictionary
let user_dict = PathMapDictionary::new();

// User adds custom words
user_dict.insert("refactoring");
user_dict.insert("debugging");
user_dict.insert("profiling");

assert_eq!(user_dict.len(), Some(3));

// User removes a word
user_dict.remove("debugging");
assert_eq!(user_dict.len(), Some(2));

// Check existence
assert!(user_dict.contains("refactoring"));
assert!(!user_dict.contains("debugging"));

Example 7: Metadata Storage

use libdictenstein::pathmap::PathMapDictionary;
use libdictenstein::MappedDictionary;

#[derive(Clone, Debug)]
struct TermMetadata {
    frequency: u32,
    last_used: u64,
}

impl libdictenstein::DictionaryValue for TermMetadata {}

let dict: PathMapDictionary<TermMetadata> = PathMapDictionary::new();

// Add terms with metadata
dict.insert_with_value("test", TermMetadata {
    frequency: 100,
    last_used: 1234567890,
});

dict.insert_with_value("testing", TermMetadata {
    frequency: 50,
    last_used: 1234567891,
});

// Query metadata
if let Some(meta) = dict.get_value("test") {
    println!("Frequency: {}", meta.frequency);
}

Example 8: Prototyping

use libdictenstein::pathmap::PathMapDictionary;
use liblevenshtein::levenshtein::Algorithm;
use liblevenshtein::levenshtein_automaton::LevenshteinAutomaton;

// Quick prototype for fuzzy matching
fn prototype_fuzzy_matcher(words: Vec<&str>, query: &str) {
    let dict = PathMapDictionary::from_terms(words);

    let automaton = LevenshteinAutomaton::new(query, 2, Algorithm::Standard);
    let results: Vec<String> = automaton.query(&dict).collect();

    println!("Matches for '{}': {:?}", query, results);
}

prototype_fuzzy_matcher(
    vec!["hello", "world", "test"],
    "helo"  // Typo
);
// Output: Matches for 'helo': ["hello"]

Performance Analysis

Time Complexity

Operation	Complexity	Notes
Insert	O(m log n)	m = term length, n = dict size
Remove	O(m log n)	HashMap operations
Contains	O(m log n)	Tree traversal + lookups
Fuzzy search	O(m $\times$ d²$\times$b $\times$ log n)	Additional log factor

Benchmark Results

Construction

Build from 10,000 terms:
  PathMapDictionary:  3.5ms
  DoubleArrayTrie:    3.2ms   (8% faster)
  DynamicDawg:        4.1ms   (15% slower)

Runtime Operations

Single insertion:
  PathMapDictionary:  ~2.1µs
  DynamicDawg:        ~800ns  (2.6x faster)
  DoubleArrayTrie:    N/A (append-only)

Single deletion:
  PathMapDictionary:  ~2.5µs
  DynamicDawg:        ~1.2µs  (2x faster)

Contains check:
  PathMapDictionary:  ~350ns
  DoubleArrayTrie:    ~120ns  (2.9x faster)
  DynamicDawg:        ~450ns  (slower)

Fuzzy Search

Query "test" (distance 1) in 10K-term dict:
  PathMapDictionary:  38.7µs
  DoubleArrayTrie:    12.9µs  (3x faster)
  DynamicDawg:        42.3µs  (similar)

Query "test" (distance 2):
  PathMapDictionary:  91.2µs
  DoubleArrayTrie:    16.3µs  (5.6x faster)
  DynamicDawg:        68.9µs  (1.3x faster)

Memory Usage

10,000-term dictionary:
  PathMapDictionary:  ~320 KB
  DoubleArrayTrie:    ~100 KB  (3.2x smaller)
  DynamicDawg:        ~294 KB  (similar)

Memory overhead:
  PathMapDictionary:  ~32 bytes/node (HashMap)
  DoubleArrayTrie:    ~10 bytes/state
  DynamicDawg:        ~25 bytes/node

Comparison Summary

                    Construction  Memory   Contains  Fuzzy(d=2)  Insert  Remove
─────────────────────────────────────────────────────────────────────────────────
PathMapDictionary   3.5ms        320KB    350ns     91.2µs      2.1µs   2.5µs
DoubleArrayTrie     3.2ms        100KB    120ns     16.3µs      N/A     N/A
DynamicDawg         4.1ms        294KB    450ns     68.9µs      800ns   1.2µs

Verdict: PathMapDictionary is 2-3x slower than optimized alternatives, but provides simplicity and full dynamic updates.

When to Use

Decision Matrix

Scenario	Recommended	Reason
Prototyping	✅ PathMapDictionary	Quick to use
Simple applications	✅ PathMapDictionary	Easy API
Maximum performance	⚠️ DoubleArrayTrie	3x faster
Memory-constrained	⚠️ DoubleArrayTrie	3x smaller
Dynamic + fast	⚠️ DynamicDawg	2x faster updates

Ideal Use Cases

1. Prototyping

   • Quick experiments
   • Proof of concept
   • Algorithm validation

2. Small Dictionaries

   • <1000 terms
   • Performance not critical
   • Simplicity valued

3. Educational/Learning

   • Understanding fuzzy matching
   • Teaching examples
   • Simple demonstrations

4. Low-Traffic Applications

   • Infrequent queries
   • Small user base
   • Development/testing

When to Migrate Away

Consider switching to specialized dictionaries when:

✅ DoubleArrayTrie if:

• Query performance becomes bottleneck
• Dictionary becomes mostly static
• Memory usage is concern

✅ DynamicDawg if:

• Frequent updates needed
• Better update performance required
• Still need full dynamic capabilities

Related Documentation

• Dictionary Layer - Overview of all dictionary types
• DoubleArrayTrie - Faster alternative
• DynamicDawg - Faster dynamic alternative
• PathMapDictionaryChar - Unicode variant
• Value Storage - Using values

Read-only views: snapshots and zero-copy borrows

Beyond the mutable PathMapDictionary / PathMapDictionaryChar, the backend exposes four read-only dictionary types (all feature-gated behind pathmap-backend). They exist so a consumer — most importantly MORK, whose Space owns a live PathMap — can query the trie as a Dictionary without cloning it or taking a write path.

Type	Ownership	Alphabet	Obtained by
PathMapSnapshot<V>	owned $O(1)$ snapshot	u8	dict.snapshot()
PathMapSnapshotChar<V>	owned $O(1)$ snapshot	char	dict.snapshot()
PathMapRef<'a, V>	zero-copy borrow ('a)	u8	PathMapRef::from_map(&map) / ::from_trie_ref(map.trie_ref_at_path(prefix))
PathMapRefChar<'a, V>	zero-copy borrow ('a)	char	PathMapRefChar::from_map(&map)

Both families implement Dictionary and MappedDictionary but not the mutation traits — they are strictly for reading. The distinction between them is lifetime and ownership:

• A snapshot takes PathMap's persistent-structure $O(1)$ snapshot: it owns an immutable view of the trie as of the call, and outlives the source dictionary. Later writes to the source do not affect it — proper snapshot isolation. Use it when the reader must persist independently of the writer.
• A ref borrows a live PathMap (or a sub-trie reached by a path) for the borrow's lifetime 'a with no allocation at all. Use it for a transient query against a map you already hold — e.g. a fuzzy transducer walking MORK's Space in place. Because it borrows, it cannot outlive the map, and the borrow checker forbids mutating the map while the ref is alive.

use libdictenstein::pathmap::PathMapDictionary;

let dict: PathMapDictionary<u64> = PathMapDictionary::from_terms_with_values(
    vec![("cat", 1u64), ("car", 2)],
);

// Owned snapshot: outlives `dict`, unaffected by later writes to `dict`.
let snap = dict.snapshot();
assert!(snap.contains("cat"));

from_trie_ref is the sub-trie entry point: it builds a PathMapRef rooted at an arbitrary path inside the source map, so a caller can hand a transducer a dictionary that is really a prefix slice of a larger structure — descent is $O(1)$ from that focus, with no root replay. See docs/integration/pathmap/ for the MORK integration.

References

PathMap Library

1. PathMap Repository
   • 📦 https://github.com/Adam-Vandervorst/PathMap
   • Underlying persistent trie implementation

Persistent Data Structures

2. Okasaki, C. (1999). Purely Functional Data Structures

   • Cambridge University Press
   • ISBN: 978-0521663502
   • 📚 Comprehensive coverage of persistent structures

3. Driscoll, J. R., Sarnak, N., Sleator, D. D., & Tarjan, R. E. (1989). "Making data structures persistent"

   • Journal of Computer and System Sciences, 38(1), 86-124
   • DOI: 10.1016/0022-0000(89)90034-2
   • 📄 Foundational paper on persistence

Trie Structures

4. Fredkin, E. (1960). "Trie memory"
   • Communications of the ACM, 3(9), 490-499
   • DOI: 10.1145/367390.367400
   • 📄 Original trie paper

Next Steps

• Performance: Compare with DoubleArrayTrie
• Dynamic: Explore DynamicDawg
• Unicode: Check PathMapDictionaryChar
• Values: Learn about Value Storage

---

Navigation: ← Dictionary Layer | DoubleArrayTrie | Algorithms Home