Fuzzy Bridge
Connecting regex engine with fuzzy matching components.
Purpose
The Fuzzy Bridge coordinates between the NFA-based regex engine and specialized fuzzy matchers (Bitap, Damerau-Levenshtein NFA).
Responsibilities
- Literal Extraction: Extract exact-match literals from patterns for pre-filtering
- Search Coordination: Order and combine multiple matchers
- Result Merging: Combine and rank results from different matchers
Architecture
Regex Pattern: hello (?:world){e<=1}
│
▼
┌────────────────┐
│ Fuzzy Bridge │
└───────┬────────┘
│
┌───────────┴───────────┐
▼ ▼
┌──────────────┐ ┌──────────────┐
│ DFA │ │ Fuzzy │
│ (exact) │ │ Matcher │
│ "hello" │ │ (Bitap/NFA) │
└──────────────┘ │ "world"{e<=1}│
└──────────────┘
Literal Extraction
#![allow(unused)]
fn main() {
// Pattern: "prefix (?:target){e<=1} suffix"
// Extracted literals: ["prefix", "suffix"]
}
Extraction Strategy
- Identify fuzzy segments in pattern
- Extract surrounding exact literals
- Use literals for:
- Pre-filtering text positions
- Quick rejection of non-matching areas
Search Flow
Simple Fuzzy Pattern
For (?:hello){e<=1}:
- Use Bitap directly (pattern ≤64 chars)
- Or build Damerau-Levenshtein NFA (longer patterns)
Mixed Pattern
For exact (?:fuzzy){e<=1}:
- Use DFA to find “exact” quickly
- For each “exact” match, check surrounding for fuzzy match
Complex Pattern
For (?:a){e<=1}(?:b){e<=1}:
- Find all fuzzy matches for “a”
- Find all fuzzy matches for “b”
- Check if they can be combined
Optimization Techniques
Prefiltering
Use extracted literals to quickly skip non-matching regions:
#![allow(unused)]
fn main() {
// Text: "blah blah prefix target suffix blah"
// Literal "prefix" found at position X
// Only check fuzzy "target" around position X
}
Early Termination
Stop searching when match found (for find/first):
#![allow(unused)]
fn main() {
// First match found, don't continue
}
Caching
Cache compiled matchers for reuse:
#![allow(unused)]
fn main() {
// Bitap matcher cached for pattern
}
End-Anchor Windowing
When a fuzzy pattern ends in $ (single-line, bounded length), a match must
finish at the end of the input, so only the final bytes can start one. Instead
of building a match cache over the whole text, the bridge searches just the
suffix window and shifts the results back into absolute coordinates:
#![allow(unused)]
fn main() {
// start_byte = earliest position a match could begin
// (text.len() minus the pattern's max length)
// let cached = bridge.search_all(&text[start_byte..], threshold)
// .shifted(start_byte);
}
Because Bitap over the suffix yields the same matches as a full scan for an
end-anchored pattern, the result set is identical — only the work is bounded.
CachedMatches::shifted(offset) re-keys every (pattern, start) entry and
bumps each match’s end by offset, so downstream code is unaware the search
was windowed. Both find and find_iter route through this path, keeping
first-match and all-match results consistent. The window is disabled in
multi-line mode, where $ can match at any line break.