WallBreaker Algorithm - Implementation Complete

Overview

WallBreaker is a similarity search algorithm that overcomes the "wall effect" in traditional left-to-right Levenshtein automata traversal. This algorithm has been fully implemented in liblevenshtein-rust using the Full SCDAWG approach.

The Wall Effect Problem

Traditional approximate string matching starts from the left edge of the pattern and must explore all prefixes up to error bound b before any filtering occurs. For example, with max_distance = 16, the algorithm must visit all dictionary prefixes of length 0-16, even though most lead to dead ends.

WallBreaker Solution

Instead of left-to-right traversal:

1. Split pattern P into b+1 pieces (pigeonhole principle)
2. Find exact matches for pattern pieces using SCDAWG substring search
3. Extend bidirectionally from exact matches using Levenshtein filters
4. Verify total distance meets bound

This avoids the wasteful initial exploration, dramatically improving performance for large error bounds.

Implementation Status: ✅ Complete

Status: Implemented and Tested Approach: Option A - Full SCDAWG Implementation Date: 2025-12-26 Tests: 35 new tests, all passing (982 total library tests)

Quick Start

use liblevenshtein::dictionary::scdawg::Scdawg;
use liblevenshtein::wallbreaker::WallBreaker;

// Build SCDAWG dictionary
let dict = Scdawg::<()>::from_terms(vec!["cathedral", "category", "catering"]);

// Create WallBreaker with max distance 2
let wb = WallBreaker::new(&dict, 2);

// Find approximate matches
for result in wb.query("cathedrel") {
    println!("{} (distance {})", result.term, result.distance);
}
// Output: cathedral (distance 1)

New Types and Modules

Dictionary Types

• Scdawg<V> - Byte-level (ASCII) SCDAWG dictionary
• ScdawgChar<V> - Character-level (Unicode/UTF-8) SCDAWG dictionary

Traits

• SubstringDictionary - Trait for dictionaries supporting exact substring search
• BidirectionalDictionaryNode - Trait for nodes supporting backward traversal

WallBreaker Module

• WallBreaker<D> - Main WallBreaker query builder
• WallBreakerQuery<D> - Iterator over approximate matches
• WallBreakerResult - Result containing matched term and distance
• PatternSplitter - Splits queries using pigeonhole principle
• PatternPiece - A piece of the split pattern

Original Paper

Title: "WallBreaker - overcoming the wall effect in similarity search" Authors: Stefan Gerdjikov, Stoyan Mihov, Petar Mitankin, Klaus U. Schulz Published: EDBT/ICDT 2013

Key Result: 0.088ms average query time for 100-character patterns with 16 errors in 750K word lexicon.

Documentation Index

Analysis Documents

• technical-analysis.md - Original analysis of codebase architecture
• decision-matrix.md - Comparison of implementation approaches

Planning Documents

• implementation-plan.md - Original phase-by-phase plan
• architectural-sketches.md - Code designs and integration points
• benchmarking-plan.md - Performance validation strategy

Tracking Documents

• progress-tracker.md - Completed task breakdown and implementation summary

Implementation Summary

Files Created

File	Lines	Description
src/dictionary/substring.rs	~120	SubstringMatch, SubstringDictionary, BidirectionalDictionaryNode traits
src/dictionary/scdawg.rs	~1300	Byte-level SCDAWG implementation (ASCII)
src/dictionary/scdawg_char.rs	~800	Character-level SCDAWG (Unicode/UTF-8)
src/wallbreaker/mod.rs	~200	WallBreaker struct and module exports
src/wallbreaker/pattern_splitter.rs	~275	PatternSplitter using pigeonhole principle
src/wallbreaker/extension.rs	~460	BidirectionalExtension for left/right traversal
src/wallbreaker/query_iterator.rs	~230	WallBreakerQuery iterator with deduplication

Key Features

• SCDAWG Backend: Full Symmetric Compact DAWG with bidirectional traversal
• Pattern Splitting: Pigeonhole principle (b+1 pieces for max_distance b)
• Bidirectional Extension: Left and right traversal with Levenshtein filters
• Deduplication: HashSet-based result deduplication
• Unicode Support: Both ASCII (Scdawg) and UTF-8 (ScdawgChar) variants

Performance Expectations

When WallBreaker Helps Most

• Large error bounds: b ≥ 4
• Long patterns: ≥ 50 characters
• Large dictionaries: ≥ 100K terms
• Cases where wall effect dominates runtime

When Traditional May Be Better

• Small error bounds: b ≤ 2
• Short patterns: < 20 characters
• Small dictionaries: < 10K terms
• Memory-constrained environments

Future Enhancements

1. Substring Search Optimization: Replace naive O(n*m) substring search with proper SCDAWG suffix link traversal for O(|pattern| + occurrences) complexity
2. Benchmarks: Add comprehensive benchmarks comparing WallBreaker vs traditional Levenshtein automata
3. Frequency-based Splitting: Optimize pattern splitting based on character frequency
4. SIMD Optimization: Apply SIMD acceleration to extension operations

Related Documentation

Library Documentation

• Levenshtein Automata - Current automata implementation
• Dictionary Layer - Available dictionary backends

Code Locations

• /src/wallbreaker/ - WallBreaker implementation
• /src/dictionary/scdawg.rs - SCDAWG dictionary backend
• /src/dictionary/scdawg_char.rs - Unicode SCDAWG variant
• /src/dictionary/substring.rs - Substring search traits

License

Documentation follows the same Apache-2.0 license as the main library.

---

Last Updated: 2025-12-26 Status: ✅ Implemented and Tested Approach: Full SCDAWG (Option A)