Minimal Prefix Double-Array Trie with Efficient Deletion
Date: 2025-11-06 Status: Planning Complete - Implementation Pending Type: Research/Evaluation Implementation (Separate from Production) Priority: Medium (Evaluation & Benchmarking)
Implement a separate MpDoubleArrayTrie backend to evaluate the Minimal Prefix Double-Array Trie structure with adaptive deletion algorithm against existing implementations (DoubleArrayTrie and DynamicDawg).
Primary: Determine if MP DAT provides sufficient performance advantage to warrant production integration
Secondary: Validate paper's claims (>97% space efficiency, <1ms deletions)
Tertiary: Educational value and research contribution
Total: 6-8 weeks Breakdown:
Title: "An Efficient Deletion Method for a Minimal Prefix Double Array"
Location: /home/dylon/Papers/Approximate String Matching/An Efficient Deletion Method for a Minimal Prefix Double Array.pdf
Key Contributions:
Algorithm: Adaptive compression loop that relocates rearmost elements to fill empty spaces, using sibling count to determine suitable destinations.
Three Dictionary Backends:
| Backend | Purpose | Mutability | Query Speed | Use Case |
|---|---|---|---|---|
| DoubleArrayTrie | Static/append-only | Build-time only | Fastest (4-13µs) | Read-heavy workloads |
| DynamicDawg | Dynamic | Runtime insert+remove | Slower (98-2384µs) | Mutable dictionaries |
| MP DAT (Planned) | Evaluation | Runtime insert+remove | Unknown | requires benchmark evidence |
Why not refactor existing DAT?
Why not just use DynamicDawg?
Strategy: Implement, benchmark, then decide:
No Breaking Changes
Clean Separation
Interior Mutability
Arc<RwLock<>> like DynamicDawgEvaluation-Focused
src/dictionary/
├── mod.rs # Existing, update with MP DAT guidance
├── double_array_trie.rs # Existing, unchanged
├── dynamic_dawg.rs # Existing, unchanged
└── mp_double_array_trie.rs # NEW: ~1000-1200 lines
tests/
├── mp_dat_correctness.rs # NEW: ~300 lines
└── mp_dat_integration.rs # NEW: ~200 lines
benches/
└── mp_dat_comparison.rs # NEW: ~500 lines
docs/research/
└── mp_dat_evaluation.md # NEW: Results & recommendation
Duration: 2-3 weeks Effort: 60-80 hours Status: 🔴 Not Started
File: src/dictionary/mp_double_array_trie.rs
Public API:
/// Minimal Prefix Double-Array Trie with efficient deletion
///
/// This is an experimental implementation for evaluation purposes.
/// For production use, prefer `DoubleArrayTrie` (static) or
/// `DynamicDawg` (mutable).
pub struct MpDoubleArrayTrie<V: DictionaryValue = ()> {
inner: Arc<RwLock<MpDATInner<V>>>,
}
impl<V: DictionaryValue> MpDoubleArrayTrie<V> {
/// Create empty MP DAT
pub fn new() -> Self;
/// Create from iterator
pub fn from_iter<I>(terms: I) -> Self
where I: IntoIterator<Item = (String, V)>;
/// Insert term with value
pub fn insert(&self, term: &str, value: V) -> bool;
/// Remove term
pub fn remove(&self, term: &str) -> bool;
/// Check if term exists
pub fn contains(&self, term: &str) -> bool;
/// Number of terms
pub fn len(&self) -> usize;
/// Statistics for evaluation
pub fn stats(&self) -> MpDatStats;
}
pub struct MpDatStats {
pub node_count: usize,
pub tail_size: usize,
pub empty_count: usize,
pub space_efficiency: f64, // % of array utilized
}
Internal Structure:
struct MpDATInner<V: DictionaryValue> {
// Standard DAT arrays
base: Vec<i32>, // BASE[i] = base index for state i
check: Vec<i32>, // CHECK[i] = parent of state i
is_final: Vec<bool>, // True if state is final
edges: Vec<Vec<u8>>, // Edge labels (optimization)
values: Vec<Option<V>>, // Associated values
// MP DAT: TAIL array for suffixes
tail: Vec<u8>, // Suffix storage (UTF-8 bytes)
tail_pos: Vec<usize>, // Start position in TAIL for each node
tail_len: Vec<usize>, // Length of suffix in TAIL
tail_free_list: Vec<usize>, // Free blocks in TAIL
// Deletion support
free_list: Vec<usize>, // E-LINK: linked list of empty elements
max: usize, // Rearmost non-empty element
term_count: usize, // Number of terms stored
// Configuration
initial_capacity: usize, // Initial array size
growth_factor: f64, // Array growth rate (e.g., 1.5)
}
Key Differences from Standard DAT:
Operations:
impl<V: DictionaryValue> MpDATInner<V> {
/// Allocate space in TAIL for suffix
fn tail_alloc(&mut self, suffix: &str) -> usize {
let bytes = suffix.as_bytes();
let len = bytes.len();
// Search free list for suitable block
if let Some(pos) = self.find_free_block(len) {
self.tail[pos..pos+len].copy_from_slice(bytes);
return pos;
}
// Append to end
let pos = self.tail.len();
self.tail.extend_from_slice(bytes);
pos
}
/// Free space in TAIL
fn tail_free(&mut self, pos: usize, len: usize) {
// Add to free list
self.tail_free_list.push(pos);
// Improvement candidate: coalesce adjacent free blocks
}
/// Match suffix in TAIL
fn tail_match(&self, pos: usize, len: usize, suffix: &str) -> bool {
if len != suffix.len() {
return false;
}
&self.tail[pos..pos+len] == suffix.as_bytes()
}
/// Find free block of sufficient size
fn find_free_block(&self, required_len: usize) -> Option<usize> {
// First-fit strategy
// Allocation policy candidate: consider best-fit or buddy allocation
for &pos in &self.tail_free_list {
let block_len = self.get_block_length(pos);
if block_len >= required_len {
return Some(pos);
}
}
None
}
}
Memory Management Strategy:
Query Operation:
impl<V: DictionaryValue> MpDATInner<V> {
/// Check if term exists
pub fn contains(&self, term: &str) -> bool {
let bytes = term.as_bytes();
let mut state = 0; // Root
let mut i = 0;
// Navigate trie
while i < bytes.len() {
let c = bytes[i];
// Check if this node has TAIL suffix
if self.tail_len[state] > 0 {
let tail_start = self.tail_pos[state];
let tail_length = self.tail_len[state];
let remaining = &bytes[i..];
return self.tail_match(tail_start, tail_length,
std::str::from_utf8(remaining).unwrap());
}
// Standard DAT transition
let next = self.base[state] + c as i32;
if next < 0 || next >= self.check.len() as i32 {
return false;
}
if self.check[next as usize] != state as i32 {
return false;
}
state = next as usize;
i += 1;
}
self.is_final[state]
}
}
Insertion Operation:
impl<V: DictionaryValue> MpDATInner<V> {
/// Insert term with value
pub fn insert(&mut self, term: &str, value: V) -> bool {
let bytes = term.as_bytes();
let mut state = 0;
let mut i = 0;
// Navigate to insertion point
while i < bytes.len() {
let c = bytes[i];
// Check for TAIL suffix at current node
if self.tail_len[state] > 0 {
// Need to split TAIL
return self.insert_split_tail(state, &bytes[i..], value);
}
// Try transition
let next = self.base[state] + c as i32;
if next < 0 || next >= self.check.len() as i32
|| self.check[next as usize] != state as i32 {
// Create new branch
return self.insert_new_branch(state, &bytes[i..], value);
}
state = next as usize;
i += 1;
}
// Existing node
if self.is_final[state] {
// Update existing
self.values[state] = Some(value);
false
} else {
// Mark as final
self.is_final[state] = true;
self.values[state] = Some(value);
self.term_count += 1;
true
}
}
/// Insert by creating new branch with TAIL
fn insert_new_branch(&mut self, state: usize, suffix: &[u8], value: V)
-> bool
{
let c = suffix[0];
let next = self.allocate_node(state, c);
if suffix.len() > 1 {
// Store remaining as TAIL
let tail_suffix = std::str::from_utf8(&suffix[1..]).unwrap();
let tail_pos = self.tail_alloc(tail_suffix);
self.tail_pos[next] = tail_pos;
self.tail_len[next] = tail_suffix.len();
}
self.is_final[next] = true;
self.values[next] = Some(value);
self.term_count += 1;
true
}
/// Insert by splitting existing TAIL
fn insert_split_tail(&mut self, state: usize, new_suffix: &[u8], value: V)
-> bool
{
// Find common prefix between TAIL and new suffix
let tail_start = self.tail_pos[state];
let tail_len = self.tail_len[state];
let old_tail = &self.tail[tail_start..tail_start+tail_len];
let common_len = old_tail.iter()
.zip(new_suffix.iter())
.take_while(|(a, b)| a == b)
.count();
// Create nodes for common prefix
let mut current = state;
for i in 0..common_len {
let c = old_tail[i];
let next = self.allocate_node(current, c);
current = next;
}
// Branch point
if common_len < old_tail.len() && common_len < new_suffix.len() {
// Both have remaining suffixes - store in TAIL
let old_remaining = &old_tail[common_len..];
let new_remaining = &new_suffix[common_len..];
// Old branch
let old_node = self.allocate_node(current, old_remaining[0]);
if old_remaining.len() > 1 {
let tail_pos = self.tail_alloc(
std::str::from_utf8(&old_remaining[1..]).unwrap()
);
self.tail_pos[old_node] = tail_pos;
self.tail_len[old_node] = old_remaining.len() - 1;
}
self.is_final[old_node] = true;
// New branch
let new_node = self.allocate_node(current, new_remaining[0]);
if new_remaining.len() > 1 {
let tail_pos = self.tail_alloc(
std::str::from_utf8(&new_remaining[1..]).unwrap()
);
self.tail_pos[new_node] = tail_pos;
self.tail_len[new_node] = new_remaining.len() - 1;
}
self.is_final[new_node] = true;
self.values[new_node] = Some(value);
}
// Free old TAIL
self.tail_free(tail_start, tail_len);
self.tail_len[state] = 0;
self.term_count += 1;
true
}
}
Standard DAT Allocation:
impl<V: DictionaryValue> MpDATInner<V> {
/// Allocate node for transition
fn allocate_node(&mut self, parent: usize, c: u8) -> usize {
// Find base value for parent
let base = self.find_base(parent, &[c]);
self.base[parent] = base;
let child = (base + c as i32) as usize;
self.ensure_capacity(child + 1);
self.check[child] = parent as i32;
self.base[child] = 0;
self.is_final[child] = false;
self.tail_pos[child] = 0;
self.tail_len[child] = 0;
self.update_max(child);
child
}
/// Find suitable BASE value
fn find_base(&self, state: usize, edges: &[u8]) -> i32 {
// X-CHECK: Find base where all edges are free
let mut base = 1;
'outer: loop {
for &c in edges {
let candidate = base + c as i32;
if candidate < 0 || candidate >= self.check.len() as i32 {
break 'outer;
}
if self.check[candidate as usize] >= 0 {
base += 1;
continue 'outer;
}
}
return base;
}
// Need to expand arrays
base
}
/// Ensure capacity for index
fn ensure_capacity(&mut self, required: usize) {
if required >= self.base.len() {
let new_size = (required as f64 * self.growth_factor) as usize;
self.base.resize(new_size, 0);
self.check.resize(new_size, -1); // -1 = empty
self.is_final.resize(new_size, false);
self.edges.resize(new_size, Vec::new());
self.values.resize(new_size, None);
self.tail_pos.resize(new_size, 0);
self.tail_len.resize(new_size, 0);
}
}
/// Update maximum non-empty element
fn update_max(&mut self, index: usize) {
if index > self.max {
self.max = index;
}
}
}
impl<V: DictionaryValue> Dictionary for MpDoubleArrayTrie<V> {
type Node = MpDatNode;
fn root(&self) -> Self::Node {
MpDatNode {
inner: Arc::clone(&self.inner),
state: 0,
}
}
fn contains(&self, term: &str) -> bool {
self.inner.read().unwrap().contains(term)
}
fn len(&self) -> Option<usize> {
Some(self.inner.read().unwrap().term_count)
}
fn is_empty(&self) -> bool {
self.len() == Some(0)
}
fn sync_strategy(&self) -> SyncStrategy {
SyncStrategy::ThreadSafe
}
fn is_suffix_based(&self) -> bool {
false // Uses TAIL for suffixes, but not suffix automaton
}
}
pub struct MpDatNode {
inner: Arc<RwLock<MpDATInner<()>>>,
state: usize,
}
impl DictionaryNode for MpDatNode {
fn edges(&self) -> Box<dyn Iterator<Item = u8> + '_> {
let inner = self.inner.read().unwrap();
let edges = inner.edges[self.state].clone();
Box::new(edges.into_iter())
}
fn transition(&self, c: u8) -> Option<Self> {
let inner = self.inner.read().unwrap();
let next = inner.base[self.state] + c as i32;
if next < 0 || next >= inner.check.len() as i32 {
return None;
}
if inner.check[next as usize] != self.state as i32 {
return None;
}
Some(MpDatNode {
inner: Arc::clone(&self.inner),
state: next as usize,
})
}
fn is_final(&self) -> bool {
let inner = self.inner.read().unwrap();
inner.is_final[self.state]
}
}
Progress Tracking for Phase 1:
Duration: 1-2 weeks Effort: 40-60 hours Status: 🔴 Not Started
High-Level Flow:
1. Navigate to node
2. Mark as non-final
3. If node becomes unreachable, mark CHECK as empty
4. Add to free_list (E-LINK)
5. Free TAIL space if present
6. Trigger compression
Implementation:
impl<V: DictionaryValue> MpDATInner<V> {
/// Remove term
pub fn remove(&mut self, term: &str) -> bool {
let bytes = term.as_bytes();
let mut state = 0;
let mut path = vec![0]; // Track path for cleanup
// Navigate to node
for &c in bytes {
// Check TAIL
if self.tail_len[state] > 0 {
// Exact match required
let tail_start = self.tail_pos[state];
let tail_len = self.tail_len[state];
let remaining = &bytes[path.len()..];
if !self.tail_match(tail_start, tail_len,
std::str::from_utf8(remaining).unwrap()) {
return false; // Not found
}
// Match - proceed to deletion
break;
}
let next = self.base[state] + c as i32;
if next < 0 || next >= self.check.len() as i32
|| self.check[next as usize] != state as i32 {
return false; // Not found
}
state = next as usize;
path.push(state);
}
if !self.is_final[state] {
return false; // Not found
}
// Mark as non-final
self.is_final[state] = false;
self.values[state] = None;
self.term_count -= 1;
// Free TAIL if present
if self.tail_len[state] > 0 {
self.tail_free(self.tail_pos[state], self.tail_len[state]);
self.tail_len[state] = 0;
}
// Clean up unreachable nodes (bottom-up)
self.cleanup_path(&path);
// Trigger compression
self.compress();
true
}
/// Remove unreachable nodes along path
fn cleanup_path(&mut self, path: &[usize]) {
for i in (1..path.len()).rev() {
let state = path[i];
// Check if node is still needed
if self.is_final[state] || self.has_children(state) {
break; // Stop at first still-needed node
}
// Mark as empty
let parent = path[i - 1];
self.check[state] = -1; // Empty marker
self.add_to_free_list(state);
// Remove from parent's edge list
self.remove_edge(parent, state);
}
}
/// Check if node has children
fn has_children(&self, state: usize) -> bool {
!self.edges[state].is_empty()
}
/// Add node to E-LINK free list
fn add_to_free_list(&mut self, index: usize) {
self.free_list.push(index);
}
/// Remove edge from parent
fn remove_edge(&mut self, parent: usize, child_state: usize) {
let base = self.base[parent];
for (i, &edge) in self.edges[parent].iter().enumerate() {
if base + edge as i32 == child_state as i32 {
self.edges[parent].remove(i);
break;
}
}
}
}
Adaptive Method from Paper:
impl<V: DictionaryValue> MpDATInner<V> {
/// Compress empty elements (Adaptive Method)
fn compress(&mut self) {
while !self.free_list.is_empty() {
// Find MAX (rearmost non-empty element)
while self.max > 0 && self.check[self.max] < 0 {
self.max -= 1;
}
if self.max == 0 {
break; // Only root remains
}
// Count siblings of MAX
let max_parent = self.check[self.max] as usize;
let max_siblings = self.edges[max_parent].len();
// EX-CHECK: Find suitable destination
if let Some(dest) = self.ex_check(max_siblings) {
// Relocate MAX and siblings
self.relocate(max_parent, dest);
} else {
// No suitable destination, stop compression
break;
}
}
}
/// EX-CHECK: Search free list for suitable destination
fn ex_check(&self, max_siblings: usize) -> Option<i32> {
for &index in &self.free_list {
if self.is_target(index, max_siblings) {
return Some(index as i32);
}
}
None
}
/// IS-TARGET: Adaptive criterion (Paper's key innovation)
fn is_target(&self, dest: usize, max_siblings: usize) -> bool {
// Empty element always accepted
if self.check[dest] < 0 {
return true;
}
// Count siblings at destination
let dest_parent = self.check[dest] as usize;
let dest_siblings = self.edges[dest_parent].len();
// Accept if destination has FEWER siblings than MAX
dest_siblings < max_siblings
}
/// Relocate node and all siblings
fn relocate(&mut self, parent: usize, new_base: i32) {
let old_base = self.base[parent];
let edges = self.edges[parent].clone();
// Update BASE
self.base[parent] = new_base;
// Relocate each child
for &edge in &edges {
let old_child = (old_base + edge as i32) as usize;
let new_child = (new_base + edge as i32) as usize;
// Ensure capacity
self.ensure_capacity(new_child + 1);
// Copy node data
self.base[new_child] = self.base[old_child];
self.check[new_child] = parent as i32;
self.is_final[new_child] = self.is_final[old_child];
self.edges[new_child] = self.edges[old_child].clone();
self.values[new_child] = self.values[old_child].take();
self.tail_pos[new_child] = self.tail_pos[old_child];
self.tail_len[new_child] = self.tail_len[old_child];
// Update children's CHECK pointers
self.update_children_check(old_child, new_child);
// Mark old position as empty
self.check[old_child] = -1;
self.add_to_free_list(old_child);
// Update MAX if necessary
if old_child == self.max {
self.max = new_child;
}
}
}
/// Update CHECK pointers of all children
fn update_children_check(&mut self, old_parent: usize, new_parent: usize) {
for &edge in &self.edges[old_parent] {
let child = (self.base[old_parent] + edge as i32) as usize;
self.check[child] = new_parent as i32;
}
}
}
Free List Management:
impl<V: DictionaryValue> MpDATInner<V> {
/// Initialize free list (called during construction)
fn init_free_list(&mut self) {
self.free_list.clear();
for i in 0..self.check.len() {
if self.check[i] < 0 {
self.free_list.push(i);
}
}
}
/// Remove from free list (when allocating)
fn remove_from_free_list(&mut self, index: usize) {
self.free_list.retain(|&i| i != index);
}
/// Optimize free list (periodic maintenance)
fn optimize_free_list(&mut self) {
// Sort for cache-friendly access
self.free_list.sort_unstable();
// Remove duplicates
self.free_list.dedup();
}
}
Progress Tracking for Phase 2:
Duration: 2 weeks Effort: 60-80 hours Status: 🔴 Not Started
File: tests/mp_dat_correctness.rs
Test Categories:
#[cfg(test)]
mod correctness_tests {
use super::*;
// === Basic Operations ===
#[test]
fn test_insert_single() {
let dat = MpDoubleArrayTrie::new();
assert!(dat.insert("hello", ()));
assert!(dat.contains("hello"));
assert_eq!(dat.len(), 1);
}
#[test]
fn test_insert_multiple() {
let dat = MpDoubleArrayTrie::new();
let words = ["hello", "world", "test", "data"];
for &word in &words {
assert!(dat.insert(word, ()));
}
assert_eq!(dat.len(), 4);
for &word in &words {
assert!(dat.contains(word));
}
}
#[test]
fn test_insert_duplicate() {
let dat = MpDoubleArrayTrie::new();
assert!(dat.insert("hello", ()));
assert!(!dat.insert("hello", ())); // Duplicate
assert_eq!(dat.len(), 1);
}
#[test]
fn test_remove_single() {
let dat = MpDoubleArrayTrie::new();
dat.insert("hello", ());
assert!(dat.remove("hello"));
assert!(!dat.contains("hello"));
assert_eq!(dat.len(), 0);
}
#[test]
fn test_remove_nonexistent() {
let dat = MpDoubleArrayTrie::new();
assert!(!dat.remove("hello"));
}
// === TAIL Array Tests ===
#[test]
fn test_tail_storage() {
let dat = MpDoubleArrayTrie::new();
// Long words should use TAIL
dat.insert("supercalifragilisticexpialidocious", ());
assert!(dat.contains("supercalifragilisticexpialidocious"));
let stats = dat.stats();
assert!(stats.tail_size > 0);
}
#[test]
fn test_tail_split() {
let dat = MpDoubleArrayTrie::new();
// Insert word with long suffix
dat.insert("testing", ());
// Insert word that splits TAIL
dat.insert("test", ());
dat.insert("tester", ());
assert!(dat.contains("test"));
assert!(dat.contains("tester"));
assert!(dat.contains("testing"));
}
#[test]
fn test_tail_no_leaks() {
let dat = MpDoubleArrayTrie::new();
for i in 0..1000 {
dat.insert(&format!("word{}", i), ());
}
for i in 0..500 {
dat.remove(&format!("word{}", i));
}
let stats = dat.stats();
// TAIL free list should have entries
// (implementation-specific check)
}
// === Compression Tests ===
#[test]
fn test_compression_basic() {
let dat = MpDoubleArrayTrie::new();
// Insert many words
for i in 0..100 {
dat.insert(&format!("test{}", i), ());
}
let stats_before = dat.stats();
// Delete half
for i in 0..50 {
dat.remove(&format!("test{}", i));
}
let stats_after = dat.stats();
// Space efficiency should remain high (>90%)
assert!(stats_after.space_efficiency > 0.90,
"Space efficiency: {}", stats_after.space_efficiency);
}
#[test]
fn test_compression_maintains_correctness() {
let dat = MpDoubleArrayTrie::new();
let words: Vec<_> = (0..200).map(|i| format!("word{}", i)).collect();
// Insert all
for word in &words {
dat.insert(word, ());
}
// Delete every other word
for i in (0..words.len()).step_by(2) {
dat.remove(&words[i]);
}
// Verify remaining words
for i in (1..words.len()).step_by(2) {
assert!(dat.contains(&words[i]),
"Lost word after compression: {}", words[i]);
}
// Verify deleted words
for i in (0..words.len()).step_by(2) {
assert!(!dat.contains(&words[i]),
"Word still present: {}", words[i]);
}
}
// === Edge Cases ===
#[test]
fn test_empty_string() {
let dat = MpDoubleArrayTrie::new();
dat.insert("", ());
assert!(dat.contains(""));
}
#[test]
fn test_unicode() {
let dat = MpDoubleArrayTrie::new();
let words = ["café", "naïve", "日本語", "🚀"];
for &word in &words {
dat.insert(word, ());
}
for &word in &words {
assert!(dat.contains(word));
}
}
#[test]
fn test_prefix_words() {
let dat = MpDoubleArrayTrie::new();
dat.insert("test", ());
dat.insert("testing", ());
dat.insert("tested", ());
dat.insert("tester", ());
assert!(dat.contains("test"));
assert!(dat.contains("testing"));
assert!(dat.contains("tested"));
assert!(dat.contains("tester"));
dat.remove("test");
assert!(!dat.contains("test"));
assert!(dat.contains("testing"));
assert!(dat.contains("tested"));
assert!(dat.contains("tester"));
}
// === Property-Based Tests ===
#[cfg(feature = "proptest")]
mod property_tests {
use proptest::prelude::*;
proptest! {
#[test]
fn prop_insert_contains(words in prop::collection::vec("[a-z]{1,20}", 1..100)) {
let dat = MpDoubleArrayTrie::new();
for word in &words {
dat.insert(word, ());
}
for word in &words {
prop_assert!(dat.contains(word));
}
}
#[test]
fn prop_remove_deletes(words in prop::collection::vec("[a-z]{1,20}", 1..100)) {
let dat = MpDoubleArrayTrie::new();
for word in &words {
dat.insert(word, ());
}
for word in &words {
dat.remove(word);
prop_assert!(!dat.contains(word));
}
prop_assert_eq!(dat.len(), 0);
}
#[test]
fn prop_insert_remove_sequences(
ops in prop::collection::vec(
(prop::bool::ANY, "[a-z]{1,10}"),
1..200
)
) {
let dat = MpDoubleArrayTrie::new();
let mut oracle = std::collections::HashSet::new();
for (insert, word) in ops {
if insert {
dat.insert(&word, ());
oracle.insert(word.clone());
} else {
dat.remove(&word);
oracle.remove(&word);
}
}
// Verify consistency
for word in &oracle {
prop_assert!(dat.contains(word),
"Oracle has '{}' but DAT doesn't", word);
}
prop_assert_eq!(dat.len(), oracle.len());
}
}
}
}
File: tests/mp_dat_integration.rs
#[cfg(test)]
mod integration_tests {
use liblevenshtein::prelude::*;
#[test]
fn test_with_transducer() {
let dat = MpDoubleArrayTrie::from_iter(
vec!["test", "testing", "tester", "tested"]
.into_iter()
.map(|s| (s.to_string(), ()))
);
let transducer = Transducer::new(dat, Algorithm::Standard);
let results: Vec<_> = transducer.query("tesy", 1).collect();
assert!(results.contains(&"test".to_string()));
}
#[test]
fn test_dictionary_trait() {
let dat: Box<dyn Dictionary<Node=_>> =
Box::new(MpDoubleArrayTrie::from_iter(
vec!["a", "b", "c"].into_iter().map(|s| (s.to_string(), ()))
));
assert_eq!(dat.len(), Some(3));
assert!(dat.contains("a"));
assert!(!dat.is_empty());
}
#[test]
fn test_thread_safety() {
use std::sync::Arc;
use std::thread;
let dat = Arc::new(MpDoubleArrayTrie::from_iter(
(0..1000).map(|i| (format!("word{}", i), ()))
));
let mut handles = vec![];
// Spawn readers
for _ in 0..10 {
let dat = Arc::clone(&dat);
handles.push(thread::spawn(move || {
for i in 0..1000 {
assert!(dat.contains(&format!("word{}", i)));
}
}));
}
// Spawn writers
for i in 0..5 {
let dat = Arc::clone(&dat);
handles.push(thread::spawn(move || {
dat.insert(&format!("new{}", i), ());
}));
}
for handle in handles {
handle.join().unwrap();
}
}
}
Valgrind / AddressSanitizer:
# Run tests with memory leak detection
RUSTFLAGS="-Z sanitizer=address" cargo test --target x86_64-unknown-linux-gnu
# Run with valgrind
cargo test --release
valgrind --leak-check=full --show-leak-kinds=all \
./target/release/deps/mp_dat_correctness-*
Expected Results:
Progress Tracking for Phase 3:
Duration: 1-2 weeks Effort: 40-60 hours Status: 🔴 Not Started
File: benches/mp_dat_comparison.rs
Structure:
use criterion::{black_box, criterion_group, criterion_main,
BenchmarkId, Criterion, Throughput};
use liblevenshtein::prelude::*;
// === Construction Benchmarks ===
fn bench_construction(c: &mut Criterion) {
let words: Vec<String> = generate_words(10_000);
let mut group = c.benchmark_group("construction");
group.throughput(Throughput::Elements(words.len() as u64));
group.bench_function("DoubleArrayTrie", |b| {
b.iter(|| {
let dat = DoubleArrayTrie::from_iter(
words.iter().map(|s| (s.clone(), ()))
);
black_box(dat)
})
});
group.bench_function("DynamicDawg", |b| {
b.iter(|| {
let dawg = DynamicDawg::from_terms(words.clone());
black_box(dawg)
})
});
group.bench_function("MpDoubleArrayTrie", |b| {
b.iter(|| {
let mp_dat = MpDoubleArrayTrie::from_iter(
words.iter().map(|s| (s.clone(), ()))
);
black_box(mp_dat)
})
});
group.finish();
}
// === Query Benchmarks (CRITICAL) ===
fn bench_query_performance(c: &mut Criterion) {
let words: Vec<String> = generate_words(10_000);
let queries: Vec<String> = sample_words(&words, 1000);
// Build dictionaries
let dat = DoubleArrayTrie::from_iter(
words.iter().map(|s| (s.clone(), ()))
);
let dawg = DynamicDawg::from_terms(words.clone());
let mp_dat = MpDoubleArrayTrie::from_iter(
words.iter().map(|s| (s.clone(), ()))
);
let mut group = c.benchmark_group("query_exact_match");
group.throughput(Throughput::Elements(queries.len() as u64));
group.bench_function("DoubleArrayTrie", |b| {
b.iter(|| {
for query in &queries {
black_box(dat.contains(query));
}
})
});
group.bench_function("DynamicDawg", |b| {
b.iter(|| {
for query in &queries {
black_box(dawg.contains(query));
}
})
});
group.bench_function("MpDoubleArrayTrie", |b| {
b.iter(|| {
for query in &queries {
black_box(mp_dat.contains(query));
}
})
});
group.finish();
}
// === Fuzzy Query Benchmarks ===
fn bench_fuzzy_query(c: &mut Criterion) {
let words: Vec<String> = generate_words(10_000);
let queries: Vec<String> = generate_typos(&words, 100);
for distance in [1, 2, 3] {
let mut group = c.benchmark_group(format!("fuzzy_query_d{}", distance));
// DoubleArrayTrie
let dat = DoubleArrayTrie::from_iter(
words.iter().map(|s| (s.clone(), ()))
);
let transducer_dat = Transducer::new(dat, Algorithm::Standard);
group.bench_function("DoubleArrayTrie", |b| {
b.iter(|| {
for query in &queries {
let results: Vec<_> = transducer_dat
.query(query, distance)
.collect();
black_box(results);
}
})
});
// DynamicDawg
let dawg = DynamicDawg::from_terms(words.clone());
let transducer_dawg = Transducer::new(dawg, Algorithm::Standard);
group.bench_function("DynamicDawg", |b| {
b.iter(|| {
for query in &queries {
let results: Vec<_> = transducer_dawg
.query(query, distance)
.collect();
black_box(results);
}
})
});
// MpDoubleArrayTrie
let mp_dat = MpDoubleArrayTrie::from_iter(
words.iter().map(|s| (s.clone(), ()))
);
let transducer_mp = Transducer::new(mp_dat, Algorithm::Standard);
group.bench_function("MpDoubleArrayTrie", |b| {
b.iter(|| {
for query in &queries {
let results: Vec<_> = transducer_mp
.query(query, distance)
.collect();
black_box(results);
}
})
});
group.finish();
}
}
// === Deletion Benchmarks ===
fn bench_deletion_performance(c: &mut Criterion) {
let words: Vec<String> = generate_words(10_000);
let to_delete: Vec<String> = sample_words(&words, 1000);
let mut group = c.benchmark_group("deletion");
group.throughput(Throughput::Elements(to_delete.len() as u64));
// DynamicDawg
group.bench_function("DynamicDawg", |b| {
b.iter_batched(
|| {
let dawg = DynamicDawg::from_terms(words.clone());
(dawg, to_delete.clone())
},
|(dawg, words_to_delete)| {
for word in words_to_delete {
dawg.remove(&word);
}
},
criterion::BatchSize::SmallInput
)
});
// MpDoubleArrayTrie
group.bench_function("MpDoubleArrayTrie", |b| {
b.iter_batched(
|| {
let mp_dat = MpDoubleArrayTrie::from_iter(
words.iter().map(|s| (s.clone(), ()))
);
(mp_dat, to_delete.clone())
},
|(mp_dat, words_to_delete)| {
for word in words_to_delete {
mp_dat.remove(&word);
}
},
criterion::BatchSize::SmallInput
)
});
group.finish();
}
// === Memory Usage Benchmarks ===
fn bench_memory_usage(c: &mut Criterion) {
let sizes = [1_000, 5_000, 10_000, 50_000];
for size in sizes {
let words = generate_words(size);
println!("\n=== Memory Usage ({} words) ===", size);
// DoubleArrayTrie
let dat = DoubleArrayTrie::from_iter(
words.iter().map(|s| (s.clone(), ()))
);
let dat_size = std::mem::size_of_val(&dat);
println!("DoubleArrayTrie: {} bytes ({} bytes/word)",
dat_size, dat_size / size);
// DynamicDawg
let dawg = DynamicDawg::from_terms(words.clone());
let dawg_size = estimate_dawg_size(&dawg);
println!("DynamicDawg: {} bytes ({} bytes/word)",
dawg_size, dawg_size / size);
// MpDoubleArrayTrie
let mp_dat = MpDoubleArrayTrie::from_iter(
words.iter().map(|s| (s.clone(), ()))
);
let mp_dat_size = estimate_mp_dat_size(&mp_dat);
println!("MpDoubleArrayTrie: {} bytes ({} bytes/word)",
mp_dat_size, mp_dat_size / size);
// TAIL usage
let stats = mp_dat.stats();
println!(" TAIL array: {} bytes", stats.tail_size);
println!(" Node count: {}", stats.node_count);
println!(" Space efficiency: {:.2}%", stats.space_efficiency * 100.0);
}
}
// === Space Efficiency After Deletions ===
fn bench_space_efficiency(c: &mut Criterion) {
let words: Vec<String> = generate_words(10_000);
println!("\n=== Space Efficiency After Deletions ===");
for delete_percent in [10, 25, 50, 75, 90] {
let to_delete_count = words.len() * delete_percent / 100;
let to_delete: Vec<_> = words.iter()
.take(to_delete_count)
.cloned()
.collect();
// MP DAT
let mp_dat = MpDoubleArrayTrie::from_iter(
words.iter().map(|s| (s.clone(), ()))
);
for word in &to_delete {
mp_dat.remove(word);
}
let stats = mp_dat.stats();
println!("{}% deleted: {:.2}% space efficiency ({} empty elements)",
delete_percent,
stats.space_efficiency * 100.0,
stats.empty_count);
}
}
// === Helper Functions ===
fn generate_words(count: usize) -> Vec<String> {
(0..count).map(|i| format!("word{:06}", i)).collect()
}
fn sample_words(words: &[String], count: usize) -> Vec<String> {
use rand::seq::SliceRandom;
use rand::SeedableRng;
let mut rng = rand::rngs::StdRng::seed_from_u64(42);
words.choose_multiple(&mut rng, count).cloned().collect()
}
fn generate_typos(words: &[String], count: usize) -> Vec<String> {
// Simple typo generation for benchmarking
sample_words(words, count).into_iter()
.map(|mut word| {
if !word.is_empty() {
word.pop(); // Simple deletion
}
word
})
.collect()
}
criterion_group!(
benches,
bench_construction,
bench_query_performance,
bench_fuzzy_query,
bench_deletion_performance,
bench_memory_usage,
bench_space_efficiency,
);
criterion_main!(benches);
Goal: Verify paper's claims
Test Sets (if available):
Metrics to Validate:
Must-Have:
Should-Have:
Nice-to-Have:
Progress Tracking for Phase 4:
Duration: 1 week Effort: 20-30 hours Status: 🔴 Not Started
File: docs/research/mp_dat_evaluation.md
Template:
# MP DAT Evaluation Results
**Date**: [Date]
**Implementation**: MpDoubleArrayTrie
**Comparison**: vs DoubleArrayTrie and DynamicDawg
---
## Executive Summary
[Brief summary of findings and recommendation]
---
## Performance Results
### Construction Time
| Backend | 10K words | 50K words | 100K words |
|---------|-----------|-----------|------------|
| DoubleArrayTrie | 3.3ms | [measure] | [measure] |
| DynamicDawg | 4.0ms | [measure] | [measure] |
| **MpDoubleArrayTrie** | **[measure]** | **[measure]** | **[measure]** |
**Finding**: [Analysis]
### Query Performance (CRITICAL)
#### Exact Match (contains)
| Backend | 1K queries | Avg Latency | Throughput |
|---------|-----------|-------------|------------|
| DoubleArrayTrie | [measure] | 4.13µs | 242K q/s |
| DynamicDawg | [measure] | 98µs | 10K q/s |
| **MpDoubleArrayTrie** | **[measure]** | **[measure]** | **[measure] q/s** |
**Finding**: [Analysis - This is the key metric]
#### Fuzzy Query (Levenshtein distance)
| Backend | Distance 1 | Distance 2 | Distance 3 |
|---------|-----------|-----------|-----------|
| DoubleArrayTrie | 8.07µs | 12.68µs | 18.21µs |
| DynamicDawg | 328µs | 2,384µs | [measure] |
| **MpDoubleArrayTrie** | **[measure]** | **[measure]** | **[measure]** |
**Finding**: [Analysis]
### Deletion Performance
| Backend | Single Delete | Batch 100 | Batch 1000 |
|---------|--------------|-----------|------------|
| DynamicDawg | [measure] | [measure] | [measure] |
| **MpDoubleArrayTrie** | **[measure]** | **[measure]** | **[measure]** |
**Paper Claim**: <1ms per deletion
**Our Result**: [measured deletion latency] per deletion
**Finding**: [Analysis]
### Space Efficiency
#### After Deletions
| Delete % | MP DAT Efficiency | Empty Elements |
|----------|------------------|----------------|
| 10% | [measure] | [measure] |
| 25% | [measure] | [measure] |
| 50% | [measure] | [measure] |
| 75% | [measure] | [measure] |
| 90% | [measure] | [measure] |
**Paper Claim**: >97% efficiency
**Our Result**: [measured efficiency] at 50% deletions
**Finding**: [Analysis]
#### Memory Usage
| Backend | 10K words | Bytes/Word | TAIL Size |
|---------|-----------|------------|-----------|
| DoubleArrayTrie | 80KB | 8B | N/A |
| DynamicDawg | 400KB | 40B | N/A |
| **MpDoubleArrayTrie** | **[measure]** | **[measure]** | **[measure]** |
**Finding**: [Analysis]
---
## Paper Validation
| Claim | Paper Result | Our Result | Validated? |
|-------|-------------|------------|------------|
| Space efficiency | >97% | [measure] | pass/fail |
| Deletion time | <1ms | [measure] | pass/fail |
| Node reduction | 30-50% | [measure] | pass/fail |
| Speedup vs Oono | 896× | N/A | N/A |
---
## Decision Matrix
| Criterion | Weight | Result | Score |
|-----------|--------|--------|-------|
| **Query performance** | 0.40 | [measured latency and DAT ratio] | [score] |
| **Deletion performance** | 0.25 | [measured latency vs DynamicDawg] | [score] |
| **Space efficiency** | 0.20 | [measured efficiency after 50% deletes] | [score] |
| **Implementation quality** | 0.10 | [Subjective] | [score] |
| **Maintenance burden** | 0.05 | [Subjective] | [score] |
| **TOTAL SCORE** | | | **[score]/5.0** |
**Threshold for adoption**: ≥4.0/5.0
---
## Use Case Analysis
### Scenario 1: Static Dictionary (No deletions)
**Best choice**: DoubleArrayTrie
**Reason**: [Analysis]
### Scenario 2: Fully Dynamic (Many insert/delete)
**Best choice**: DynamicDawg
**Reason**: [Analysis]
### Scenario 3: Mostly Static (Rare deletions)
**Best choice**: [DoubleArrayTrie / MpDoubleArrayTrie / DynamicDawg]
**Reason**: [Analysis - Key question MP DAT aims to answer]
---
## Recommendation
### Option A: Adopt for Production ✅
**If**:
- Query performance ≥ 50% of DoubleArrayTrie
- Deletion significantly faster than DynamicDawg
- Space efficiency >95%
- Clear use case identified
**Action**:
- Promote to production backend
- Add to user guidance in mod.rs
- Document when to use
- Maintain long-term
---
### Option B: Keep as Research Implementation 📚
**If**:
- Performance marginal (not clearly better)
- Use case unclear
- Maintenance burden concerns
**Action**:
- Keep implementation in codebase
- Mark as experimental
- Document findings
- Reference in papers/talks
---
### Option C: Archive with Findings 📦
**If**:
- Query performance unacceptable (<50% of DoubleArrayTrie)
- No advantage over existing backends
- Implementation issues
**Action**:
- Archive in examples/mp_dat_research/
- Document why not adopted
- Preserve for educational value
- Remove from main codebase
---
## Conclusion
[Final recommendation with clear rationale]
---
**Appendix A: Benchmark Details**
**Appendix B: Test Coverage Report**
**Appendix C: Code Size Analysis**
**Appendix D: Future Work**
Rustdoc for public API:
File: src/dictionary/mod.rs
Add to backend selection guide:
//! ## Backend Selection Guide
//!
//! | Need | Recommendation |
//! |------|---------------|
//! | Fast queries, static dictionary | [`DoubleArrayTrie`] |
//! | Insert + Remove operations | [`DynamicDawg`] |
//! | Mostly static, rare deletions | [`MpDoubleArrayTrie`] (experimental) |
//! | Substring/infix matching | [`SuffixAutomaton`] |
//!
//! ### MpDoubleArrayTrie (Experimental)
//!
//! Minimal Prefix Double-Array Trie with efficient deletion.
//!
//! **Use when**:
//! - Dictionary is mostly static (>90% stable)
//! - Occasional deletions needed (<10% turnover)
//! - Query performance critical
//! - Space efficiency important
//!
//! **Performance** (based on evaluation):
//! - Queries: [measured percentage of DoubleArrayTrie speed]
//! - Deletions: [Faster/slower than DynamicDawg]
//! - Space: [Space efficiency after deletions]
//!
//! **Trade-offs**:
//! - More complex than DoubleArrayTrie
//! - TAIL array management overhead
//! - [Other trade-offs based on evaluation]
//!
//! See [`docs/research/mp_dat_evaluation.md`] for detailed comparison.
Progress Tracking for Phase 5:
Phase Completion:
Overall Progress: 0/5 phases complete (0%)
| Milestone | Target Date | Status | Notes |
|---|---|---|---|
| Phase 1 Complete | Week 3 | 🔴 Not Started | Core implementation |
| Phase 2 Complete | Week 5 | 🔴 Not Started | Deletion algorithm |
| Phase 3 Complete | Week 7 | 🔴 Not Started | Testing & validation |
| Phase 4 Complete | Week 8 | 🔴 Not Started | Benchmarking |
| Decision Point | Week 8 | 🔴 Pending | Adopt / Keep / Archive |
| Phase 5 Complete | Week 9 | 🔴 Not Started | Documentation |
Current Blockers: None (project not started)
Potential Future Blockers:
Mitigation Strategy:
Must Have:
Should Have:
Must Have:
Should Have:
Required for Adoption:
Nice to Have:
Risk 1: Query Performance Unacceptable
Risk 2: TAIL Management Complexity
Risk 3: Compression Correctness
Risk 4: Paper Results Not Reproducible
Risk 5: Implementation Takes Longer
Risk 6: Scope Creep
Risk 7: Maintainer Availability
Risk 8: Lost Interest
Title: "An Efficient Deletion Method for a Minimal Prefix Double Array"
Location: /home/dylon/Papers/Approximate String Matching/An Efficient Deletion Method for a Minimal Prefix Double Array.pdf
Key Contributions:
97% space efficiency vs 40-60%
Oono et al. Method:
Standard DAT:
Minimal Prefix Trie:
Current DoubleArrayTrie: src/dictionary/double_array_trie.rs
DynamicDawg: src/dictionary/dynamic_dawg.rs
Arc<RwLock<>>)Dictionary Trait: src/dictionary/mod.rs
Framework: docs/research/evaluation-methodology/README.md
Norvig Corpus Plan: docs/research/evaluation-methodology/NORVIG_CORPUS_INTEGRATION_PLAN.md
This implementation plan provides a comprehensive roadmap for developing and evaluating the Minimal Prefix Double-Array Trie with efficient deletion. The phased approach enables:
Next Steps:
Decision Point: Week 8
Last Updated: 2025-11-06 Status: Planning Complete - Ready for Implementation Estimated Duration: 6-8 weeks Next Action: Begin Phase 1 - Core MP DAT Structure
Can you improve this documentation?Edit on GitHub
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |