fuzzy-regex 0.1.0

High-performance fuzzy regular expression engine combining regex with Damerau-Levenshtein distance
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

# Architecture Overview

How fuzzy-regex works internally.

## High-Level Architecture

```
┌─────────────────────────────────────────────┐
│              FuzzyRegex                      │
│         (Public API Layer)                   │
└──────────────────┬──────────────────────────┘
                   │
        ┌──────────┴──────────┐
        ▼                     ▼
┌───────────────┐   ┌─────────────────┐
│     DFA       │   │   NFA Engine   │
│  (Fast Path)  │   │  (Full Engine) │
└───────┬───────┘   └────────┬────────┘
        │                    │
        └────────┬───────────┘
                 ▼
        ┌─────────────────┐
        │  Fuzzy Bridge  │
        └────────┬────────┘
                 │
     ┌───────────┴───────────┐
     ▼                       ▼
┌──────────┐         ┌──────────┐
│  Bitap   │         │  Lev.    │
│ Matcher  │         │   NFA    │
└──────────┘         └──────────┘
```

## Components

### 1. Parser
- Tokenizes regex patterns
- Builds Abstract Syntax Tree (AST)
- Handles fuzzy syntax extensions

### 2. Compiler
- Converts AST to Intermediate Representation (IR)
- Optimizes patterns
- Handles fuzzy matching compilation

### 3. Matching Engines

#### DFA (Deterministic Finite Automaton)
- Fast path for exact/non-fuzzy patterns
- No backtracking
- Limited feature support

#### NFA (Non-deterministic Finite Automaton)
- Full regex feature support
- Backtracking engine
- Supports fuzzy matching

#### Bitap Algorithm
- Optimized for short patterns (≤64 chars)
- O(n×k) time complexity
- SIMD-accelerated

#### Levenshtein NFA
- Fuzzy matching via automata
- Supports all edit types
- Used for longer patterns

### 4. Fuzzy Bridge
- Connects NFA to fuzzy matchers
- Extracts literals for pre-filtering
- Coordinates multiple matchers