第 33 章
柔性匹配与正则引擎
第三十三章：柔性匹配与正则引擎 — 当"精确匹配"不够用时
前面的章节（KMP、Rabin-Karp、后缀数组）解决的都是精确匹配问题：给你一个模式串 P，在文本 T 中找到 P 出现的所有位置。但现实世界的搜索远比这复杂：
- 用户输入 "algoritm"（拼错了），你需要找到 "algorithm"
- Git 需要比较两个版本的文件差异，找出最短的编辑序列
- 你写
grep "log.*Error"在日志中搜索，这不是一个固定字符串
这一章讨论三个核心问题：模糊搜索（容许拼写错误的匹配）、差异比较（Myers diff 算法）、正则表达式引擎（如何把 a*b|c 变成能运行的程序）。
它们的共同点是：匹配不再是"相等或不相等"的二元判断，而是一个需要探索的搜索空间。
Level 1 · 你需要知道的
1.1 编辑距离回顾
在第 28 章中我们详细讨论了编辑距离（Levenshtein distance）：把字符串 A 变成字符串 B 所需的最少操作次数（插入、删除、替换）。
快速回顾核心公式：
dp[i][j] = min(
dp[i-1][j] + 1, # 删除 A[i]
dp[i][j-1] + 1, # 插入 B[j]
dp[i-1][j-1] + cost # 替换（cost=0 如果 A[i]==B[j]，否则=1）
)
时间复杂度 O(nm)，空间可以优化到 O(min(n,m))。
1.2 模糊搜索的实现
问题：在一个词典中找到与查询词编辑距离不超过 k 的所有词。
朴素方法：对词典中每个词计算编辑距离。如果词典有 N 个词，每个长度 m，查询长度 n，则总时间 O(N * n * m)。对于一个 10 万词的词典，这太慢了。
方法 1：BK 树（Burkhard-Keller Tree, 1973）
BK 树利用编辑距离的三角不等式来剪枝：如果 d(q, root) = d，那么与 q 距离不超过 k 的词，与 root 的距离在 [d-k, d+k] 范围内。
class BKTree:
"""
BK 树：利用三角不等式加速模糊搜索
三角不等式：d(a, c) >= |d(a, b) - d(b, c)|
即：如果 d(query, root) = d，那么答案词 w 满足：
d(root, w) 在 [d-k, d+k] 范围内
Burkhard & Keller, "Some Approaches to Best-Match File Searching", 1973
"""
def __init__(self):
self.root = None
class Node:
def __init__(self, word: str):
self.word = word
self.children = {} # distance -> child node
def add(self, word: str):
if self.root is None:
self.root = self.Node(word)
return
node = self.root
while True:
d = self._edit_distance(word, node.word)
if d == 0:
return # 重复词
if d in node.children:
node = node.children[d]
else:
node.children[d] = self.Node(word)
return
def search(self, query: str, max_dist: int) -> list[tuple[str, int]]:
"""
找所有与 query 编辑距离 <= max_dist 的词
平均时间复杂度远好于 O(N)
"""
if self.root is None:
return []
results = []
stack = [self.root]
while stack:
node = stack.pop()
d = self._edit_distance(query, node.word)
if d <= max_dist:
results.append((node.word, d))
# 利用三角不等式剪枝
# 只需要检查距离在 [d - max_dist, d + max_dist] 的子节点
for dist, child in node.children.items():
if d - max_dist <= dist <= d + max_dist:
stack.append(child)
return results
@staticmethod
def _edit_distance(a: str, b: str) -> int:
"""标准编辑距离 O(nm)"""
n, m = len(a), len(b)
dp = list(range(m + 1))
for i in range(1, n + 1):
prev = dp[0]
dp[0] = i
for j in range(1, m + 1):
temp = dp[j]
if a[i-1] == b[j-1]:
dp[j] = prev
else:
dp[j] = 1 + min(prev, dp[j], dp[j-1])
prev = temp
return dp[m]
# 演示
tree = BKTree()
dictionary = ["algorithm", "altruistic", "algebra", "logarithm",
"align", "alien", "all", "allocate"]
for word in dictionary:
tree.add(word)
results = tree.search("algoritm", max_dist=2)
print(f"与 'algoritm' 距离 ≤ 2 的词:")
for word, dist in sorted(results, key=lambda x: x[1]):
print(f" {word} (距离={dist})")
方法 2：Trie + 编辑距离自动机
对于更大的词典，可以把所有词插入 Trie 树，然后用编辑距离的 DP 行逐层与 Trie 同步计算。
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
self.word = ""
class FuzzySearchTrie:
"""
Trie + 编辑距离：一次 DFS 找到所有模糊匹配
思路：在 Trie 上做 DFS，同时维护编辑距离 DP 的当前行。
当 DP 行的最小值超过 max_dist 时，剪枝。
"""
def __init__(self):
self.root = TrieNode()
def insert(self, word: str):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_word = True
node.word = word
def search(self, query: str, max_dist: int) -> list[tuple[str, int]]:
"""
找所有与 query 编辑距离 <= max_dist 的词
核心：DFS Trie 的同时，维护 DP 行
- 当前 Trie 路径对应 "词典中的前缀"
- DP 行的第 j 列 = edit_distance(query[:j], current_prefix)
"""
results = []
n = len(query)
# 初始 DP 行：edit_distance("", query[:j]) = j
initial_row = list(range(n + 1))
# DFS
for c, child in self.root.children.items():
self._dfs(child, c, query, initial_row, max_dist, results)
return results
def _dfs(self, node: TrieNode, char: str, query: str,
prev_row: list[int], max_dist: int, results: list):
n = len(query)
# 计算当前行
curr_row = [prev_row[0] + 1] # 删除当前字符
for j in range(1, n + 1):
# 插入、删除、替换
insert_cost = curr_row[j - 1] + 1
delete_cost = prev_row[j] + 1
replace_cost = prev_row[j - 1] + (0 if query[j-1] == char else 1)
curr_row.append(min(insert_cost, delete_cost, replace_cost))
# 如果到达词尾且距离 <= max_dist
if node.is_word and curr_row[n] <= max_dist:
results.append((node.word, curr_row[n]))
# 剪枝：如果当前行的最小值 > max_dist，无需继续
if min(curr_row) <= max_dist:
for c, child in node.children.items():
self._dfs(child, c, query, curr_row, max_dist, results)
# 演示
trie = FuzzySearchTrie()
for word in ["algorithm", "altruistic", "algebra", "logarithm",
"align", "alien", "all", "allocate"]:
trie.insert(word)
results = trie.search("algoritm", max_dist=2)
print(f"\nTrie 模糊搜索 'algoritm' (距离≤2):")
for word, dist in sorted(results, key=lambda x: x[1]):
print(f" {word} (距离={dist})")
1.3 Myers Diff 算法 — Git Diff 的核心
当你运行 git diff 时，Git 需要找出两个文件版本之间的最短编辑脚本（shortest edit script, SES）。这本质上是一个编辑距离问题，但输入单位是"行"而非"字符"。
Eugene Myers 在 1986 年的论文 "An O(ND) Difference Algorithm and Its Variations" 中给出了一个优雅的算法，它的时间复杂度是 O(ND)，其中 N = n + m（两个序列的总长度），D = 编辑距离。
关键洞察：大多数文件差异很小（D << N），所以 O(ND) 通常远好于 O(NM)。
def myers_diff(a: list[str], b: list[str]) -> list[tuple[str, str]]:
"""
Myers diff 算法：找两个序列的最短编辑脚本
输入：a = 原始序列, b = 目标序列
输出：[(操作, 内容), ...] 其中操作为 ' '(不变)、'-'(删除)、'+'(插入)
时间复杂度：O((n+m) * D)，D = 编辑距离
空间复杂度：O((n+m) * D)（可优化为 O(D²) 用线性空间分治）
Myers, "An O(ND) Difference Algorithm", Algorithmica, 1986
"""
n, m = len(a), len(b)
# 在编辑图中，x 轴是 a，y 轴是 b
# 对角线 k = x - y
# 目标：从 (0,0) 到 (n,m)
# 移动规则：
# 向右 = 删除 a[x]（x++）
# 向下 = 插入 b[y]（y++）
# 对角线 = a[x] == b[y] 时匹配（x++, y++，免费）
max_d = n + m # 最大可能的编辑距离
# v[k] = 在对角线 k 上能到达的最远 x 坐标
# 使用偏移使 k 可以为负
offset = max_d
v_size = 2 * max_d + 1
# 保存每一轮的 v 以便回溯
history = []
v = [-1] * v_size
v[offset + 1] = 0 # 初始化：从对角线 1 开始（虚拟起点）
for d in range(max_d + 1):
history.append(v[:])
for k in range(-d, d + 1, 2):
# 决定从上方（删除）还是左方（插入）到达对角线 k
if k == -d or (k != d and v[offset + k - 1] < v[offset + k + 1]):
x = v[offset + k + 1] # 从对角线 k+1 向下移动（插入）
else:
x = v[offset + k - 1] + 1 # 从对角线 k-1 向右移动（删除）
y = x - k
# 沿对角线走（匹配）
while x < n and y < m and a[x] == b[y]:
x += 1
y += 1
v[offset + k] = x
# 到达终点？
if x >= n and y >= m:
# 回溯找路径
return _backtrack(a, b, history, d, offset)
return [] # 不应该到达这里
def _backtrack(a: list[str], b: list[str], history: list,
d: int, offset: int) -> list[tuple[str, str]]:
"""从 Myers 算法的历史中回溯出具体的编辑操作"""
n, m = len(a), len(b)
x, y = n, m
edits = []
for step in range(d, 0, -1):
v = history[step]
v_prev = history[step - 1]
k = x - y
# 判断是从哪个方向来的
if k == -step or (k != step and v_prev[offset + k - 1] < v_prev[offset + k + 1]):
prev_k = k + 1 # 来自上方（插入）
prev_x = v_prev[offset + prev_k]
else:
prev_k = k - 1 # 来自左方（删除）
prev_x = v_prev[offset + prev_k] + 1
prev_y = prev_x - prev_k
# 对角线移动（匹配）
while x > prev_x and y > prev_y:
x -= 1
y -= 1
edits.append((' ', a[x]))
# 非对角线移动
if step > 0:
if prev_k == k + 1:
# 插入
y -= 1
edits.append(('+', b[y]))
else:
# 删除
x -= 1
edits.append(('-', a[x]))
# 处理 d=0 时的对角线
while x > 0 and y > 0:
x -= 1
y -= 1
edits.append((' ', a[x]))
edits.reverse()
return edits
# 演示
a = ["A", "B", "C", "A", "B", "B", "A"]
b = ["C", "B", "A", "B", "A", "C"]
diff = myers_diff(a, b)
print("Myers diff 结果:")
for op, line in diff:
print(f" {op} {line}")
1.4 正则表达式基础
正则表达式是一种描述字符串模式的语言。核心操作只有三种：
| 操作 | 记号 | 含义 |
|---|---|---|
| 连接 | ab | 先匹配 a，再匹配 b |
| 选择 | a|b | 匹配 a 或 b |
| 重复 | a* | 匹配 a 零次或多次 |
加上括号用于分组，这三种操作可以描述所有正则语言（Kleene, 1956）。
现代正则表达式引擎还支持 +（一次或多次）、?（零次或一次）、.（任意字符）、[abc]（字符类）等，但这些都是语法糖——它们可以用三种基本操作表达。
# 语法糖的等价转换
# a+ 等价于 aa*
# a? 等价于 (a|ε) ε = 空串
# a{3} 等价于 aaa
# [abc] 等价于 (a|b|c)
# . 等价于 (a|b|c|...|z|0|...|9|...) 所有字符的选择
1.5 正则引擎的两种实现
方法 1：回溯法（Backtracking）
大多数编程语言（Python、Java、JavaScript、Ruby）的正则引擎使用回溯法。它本质上是一个带回溯的 DFS：
def regex_match_backtrack(text: str, pattern: str) -> bool:
"""
回溯法正则匹配（简化版，只支持 . 和 *）
对应 LeetCode #10: Regular Expression Matching
时间复杂度：最坏 O(2^n)（指数级！）
"""
def match(t: int, p: int) -> bool:
# 基本情况
if p == len(pattern):
return t == len(text)
# 当前字符是否匹配
first_match = (t < len(text) and
(pattern[p] == '.' or pattern[p] == text[t]))
# 如果下一个是 *
if p + 1 < len(pattern) and pattern[p + 1] == '*':
# 选择 1：* 匹配零次（跳过当前 pattern 的两个字符）
# 选择 2：* 匹配一次或多次（当前字符匹配，继续在同一个 * 上）
return (match(t, p + 2) or # * 匹配零次
(first_match and match(t + 1, p))) # * 匹配一次
# 普通字符匹配
return first_match and match(t + 1, p + 1)
return match(0, 0)
# 演示
print(regex_match_backtrack("aab", "c*a*b")) # True
print(regex_match_backtrack("mississippi", "mis*is*p*.")) # False
方法 2：Thompson NFA
Ken Thompson 在 1968 年提出了一个完全不同的方法：把正则表达式编译成 NFA（非确定性有限自动机），然后同时模拟 NFA 的所有可能状态。
class ThompsonNFA:
"""
Thompson NFA 正则引擎
核心思想：
1. 把正则表达式转换为 NFA（每个操作有固定的构造规则）
2. 匹配时同时追踪 NFA 的所有当前可能状态
3. 时间保证 O(nm)：n = text 长度, m = pattern 中的状态数
Thompson, "Programming Techniques: Regular Expression Search Algorithm",
Communications of the ACM, 1968
"""
class State:
def __init__(self, char=None):
self.char = char # None = epsilon 转移, '.' = 任意字符
self.out1 = None # 转移目标 1
self.out2 = None # 转移目标 2 (用于分支)
self.is_match = False
class Fragment:
"""NFA 片段：有一个起始状态和若干悬空箭头"""
def __init__(self, start, dangling):
self.start = start
self.dangling = dangling # 待连接的状态列表
def __init__(self, pattern: str):
self.start = self._compile(pattern)
def _compile(self, pattern: str):
"""
将正则表达式编译为 NFA
使用经典的"后缀表达式 + 栈"方法
"""
# 先转换为后缀表达式（加显式连接符）
postfix = self._to_postfix(pattern)
# 用栈构建 NFA
stack = []
for c in postfix:
if c == '.': # 连接
f2 = stack.pop()
f1 = stack.pop()
# f1 的所有悬空箭头指向 f2 的起始
for s in f1.dangling:
s.out1 = f2.start
stack.append(self.Fragment(f1.start, f2.dangling))
elif c == '|': # 选择
f2 = stack.pop()
f1 = stack.pop()
s = self.State() # 新的分支状态
s.out1 = f1.start
s.out2 = f2.start
stack.append(self.Fragment(s, f1.dangling + f2.dangling))
elif c == '*': # 重复
f = stack.pop()
s = self.State()
s.out1 = f.start # 进入循环
s.out2 = None # 或跳过（悬空）
for ds in f.dangling:
ds.out1 = s # 回到分支点
stack.append(self.Fragment(s, [s]))
elif c == '?': # 零次或一次
f = stack.pop()
s = self.State()
s.out1 = f.start
s.out2 = None # 悬空
stack.append(self.Fragment(s, f.dangling + [s]))
elif c == '+': # 一次或多次
f = stack.pop()
s = self.State()
s.out1 = f.start
s.out2 = None # 悬空
for ds in f.dangling:
ds.out1 = s
stack.append(self.Fragment(f.start, [s]))
else: # 普通字符
s = self.State(c)
stack.append(self.Fragment(s, [s]))
# 最终：连接匹配状态
if stack:
f = stack.pop()
match_state = self.State()
match_state.is_match = True
for s in f.dangling:
s.out1 = match_state
return f.start
return None
def _to_postfix(self, pattern: str) -> str:
"""
正则表达式转后缀表达式
添加显式连接符 '.'，然后用调度场算法
"""
# 添加显式连接符
output = []
for i, c in enumerate(pattern):
output.append(c)
if c not in ('(', '|') and i + 1 < len(pattern):
next_c = pattern[i + 1]
if next_c not in (')', '|', '*', '+', '?'):
output.append('.')
# 简化处理：这里只演示思路
# 实际实现需要完整的运算符优先级和括号处理
return ''.join(output)
def match(self, text: str) -> bool:
"""
NFA 模拟匹配
同时追踪所有可能状态
时间复杂度：O(n * m)，n = len(text), m = NFA 状态数
"""
if self.start is None:
return False
# 计算 epsilon 闭包
current_states = self._epsilon_closure({self.start})
for c in text:
next_states = set()
for state in current_states:
if state.char == c or state.char == 'ANY':
if state.out1:
next_states.add(state.out1)
current_states = self._epsilon_closure(next_states)
# 检查是否有匹配状态
return any(s.is_match for s in current_states)
def _epsilon_closure(self, states: set) -> set:
"""计算状态集合的 epsilon 闭包"""
closure = set()
stack = list(states)
while stack:
s = stack.pop()
if s in closure:
continue
closure.add(s)
if s.char is None: # epsilon 转移
if s.out1 and s.out1 not in closure:
stack.append(s.out1)
if s.out2 and s.out2 not in closure:
stack.append(s.out2)
return closure
1.6 两种引擎的根本区别
| 特性 | 回溯法 | Thompson NFA |
|---|---|---|
| 时间复杂度 | 最坏 O(2^n) | 保证 O(nm) |
| 支持反向引用 | 是 | 否 |
| 支持贪婪/懒惰 | 是 | 需要额外处理 |
| 实际性能（简单模式） | 快 | 快 |
| 实际性能（恶意模式） | 灾难性慢 | 仍然快 |
| 使用者 | Python, Java, JS, Ruby | RE2, Rust regex, Go |
Level 2 · 它是怎么运行的
2.1 Myers Diff 算法的编辑图模型
Myers diff 的核心是把 diff 问题转化为图上的最短路径问题。
编辑图（Edit Graph）：
- 一个 (n+1) x (m+1) 的网格图
- 水平边 (x,y) -> (x+1,y)：删除 a[x]，代价 1
- 垂直边 (x,y) -> (x,y+1)：插入 b[y]，代价 1
- 对角线边 (x,y) -> (x+1,y+1)：仅当 a[x] == b[y]，代价 0
- 目标：找从 (0,0) 到 (n,m) 的最小代价路径
对角线表示：
- k = x - y 表示当前在哪条对角线上
- 初始状态在对角线 k=0
- 终点 (n,m) 在对角线 k = n-m
- 每次水平移动：k 增加 1
- 每次垂直移动：k 减少 1
BFS 按层展开：
- 第 d 层 = 恰好做了 d 次非对角线移动（编辑距离 = d）
- 从 d=0 开始，每层尝试所有能到达的对角线
- 在每条对角线上尽可能沿对角线走（免费匹配）
- 直到某条对角线到达 (n,m)
这就是为什么算法是 O(ND) 的——外层循环 D 次（最短编辑距离），内层循环处理 2d+1 条对角线。
2.2 NFA 到 DFA 的转换（子集构造法）
Thompson NFA 匹配的每一步需要维护一个状态集合。如果我们预先把所有可能的状态集合枚举出来，就得到了 DFA（确定性有限自动机）：
def nfa_to_dfa(nfa_start, alphabet: set[str]):
"""
子集构造法（Subset Construction / Powerset Construction）
将 NFA 转换为等价的 DFA
Rabin & Scott, "Finite Automata and Their Decision Problems", 1959
每个 DFA 状态 = NFA 状态的一个子集
最坏情况：DFA 状态数 = 2^(NFA状态数)（指数爆炸）
"""
def epsilon_closure(states):
"""计算 epsilon 闭包"""
closure = set()
stack = list(states)
while stack:
s = stack.pop()
if id(s) in closure:
continue
closure.add(id(s))
if s.char is None: # epsilon
if s.out1:
stack.append(s.out1)
if s.out2:
stack.append(s.out2)
return frozenset(closure)
def move(state_set, char):
"""从状态集合经过字符 char 能到达的状态"""
result = set()
# 需要从 id 映射回实际状态对象
# 此处省略具体实现
return result
# DFA 的起始状态 = NFA 起始状态的 epsilon 闭包
start_closure = epsilon_closure({nfa_start})
# BFS 构建 DFA
dfa_states = {start_closure: 0} # 状态集合 -> DFA 编号
dfa_transitions = {} # (DFA状态, 字符) -> DFA状态
queue = [start_closure]
while queue:
current = queue.pop(0)
current_id = dfa_states[current]
for c in alphabet:
# 经过字符 c 能到达的 NFA 状态集合
next_states = move(current, c)
next_closure = epsilon_closure(next_states) if next_states else frozenset()
if not next_closure:
continue
if next_closure not in dfa_states:
dfa_states[next_closure] = len(dfa_states)
queue.append(next_closure)
dfa_transitions[(current_id, c)] = dfa_states[next_closure]
return dfa_states, dfa_transitions
DFA 的优势和劣势：
- 优势：匹配时每步只查一次表，O(n) 匹配
- 劣势：构建可能指数爆炸（2^m 个状态）
- 实际做法：懒惰 DFA 构建——只在需要时构建新的 DFA 状态
2.3 RE2 的混合策略
Google 的 RE2 正则引擎（Russ Cox 设计）使用混合策略：
- 小正则：直接 NFA 模拟（状态集合通常很小）
- 频繁使用的正则：逐步构建 DFA（缓存已见过的状态集合）
- DFA 太大时：回退到 NFA 模拟，并设置 DFA 缓存上限
class HybridRegexEngine:
"""
混合正则引擎（RE2 风格）
思路：
1. 从 NFA 模拟开始
2. 缓存已见过的 (当前状态集, 输入字符) -> 下一状态集
3. 当缓存足够大时，相当于自动构建了部分 DFA
4. 设置缓存上限，防止内存爆炸
"""
def __init__(self, max_cache_size: int = 10000):
self.max_cache_size = max_cache_size
self.cache = {} # (frozenset(states), char) -> frozenset(next_states)
self.cache_hits = 0
self.cache_misses = 0
def step(self, current_states: frozenset, char: str,
nfa_transitions) -> frozenset:
"""
一步转移：查缓存或计算
"""
key = (current_states, char)
if key in self.cache:
self.cache_hits += 1
return self.cache[key]
self.cache_misses += 1
# 计算下一状态集
next_states = set()
for state in current_states:
if state in nfa_transitions and char in nfa_transitions[state]:
next_states.update(nfa_transitions[state][char])
result = frozenset(next_states)
# 缓存（带上限）
if len(self.cache) < self.max_cache_size:
self.cache[key] = result
return result
2.4 Git Diff 的优化细节
实际的 Git diff 不是纯粹的 Myers 算法。它做了几个优化：
1. 先找公共前缀和后缀
def optimized_diff(a: list[str], b: list[str]) -> list[tuple[str, str]]:
"""Git 风格优化：先去掉公共前缀和后缀"""
# 找公共前缀
prefix_len = 0
while prefix_len < len(a) and prefix_len < len(b) and a[prefix_len] == b[prefix_len]:
prefix_len += 1
# 找公共后缀
suffix_len = 0
while (suffix_len < len(a) - prefix_len and
suffix_len < len(b) - prefix_len and
a[-(suffix_len+1)] == b[-(suffix_len+1)]):
suffix_len += 1
# 只对中间不同的部分运行 Myers
a_mid = a[prefix_len:len(a)-suffix_len if suffix_len else len(a)]
b_mid = b[prefix_len:len(b)-suffix_len if suffix_len else len(b)]
result = []
# 公共前缀
for line in a[:prefix_len]:
result.append((' ', line))
# 中间差异部分
if a_mid or b_mid:
diff_result = myers_diff(a_mid, b_mid)
result.extend(diff_result)
# 公共后缀
for line in a[len(a)-suffix_len:] if suffix_len else []:
result.append((' ', line))
return result
2. 线性空间优化（Hirschberg 风格）
Myers 原始算法需要 O(ND) 空间保存历史。Git 使用分治法将空间降到 O(D^2)：
- 从两端同时运行 Myers 的前向和后向搜索
- 找到中间的"蛇"（最长对角线段）
- 递归处理两半
3. Patience Diff
Git 还提供了 --patience 选项，使用 Patience Diff 算法：
- 先找两个文件的"唯一公共行"（只在 A 和 B 中各出现一次的行）
- 对这些行求 LCS（最长公共子序列）
- 用这些"锚点"分割问题，递归处理
Patience Diff 在实际中往往产生更直观的差异（不会把两个函数的大括号"对齐"）。
2.5 编辑距离自动机
Levenshtein 自动机是一个 DFA，它接受所有与给定词 w 编辑距离不超过 k 的字符串。
关键性质（Schulz & Mihov, 2002）：
对于固定的 k 和字母表大小 σ，Levenshtein 自动机的状态数是 O(n)（n = |w|）。这意味着我们可以在 O(n) 时间构建自动机，然后用它在 O(m) 时间匹配任何长度为 m 的候选字符串。
def build_levenshtein_nfa(word: str, max_dist: int):
"""
构建 Levenshtein NFA 的概念演示
状态：(i, e) 表示"已处理 word 的前 i 个字符，累计 e 次编辑"
转移：
- 匹配：(i, e) --c--> (i+1, e) 如果 word[i] == c
- 替换：(i, e) --c--> (i+1, e+1) 如果 word[i] != c 且 e < k
- 删除：(i, e) --ε--> (i+1, e+1) 跳过 word[i]，e < k
- 插入：(i, e) --c--> (i, e+1) 不消耗 word，e < k
接受状态：所有 (n, e)，e <= k
"""
n = len(word)
# 状态 = (position_in_word, edit_count)
# 转移 = character -> set of next states
states = {}
for i in range(n + 1):
for e in range(max_dist + 1):
states[(i, e)] = {}
# 构建转移（此处省略完整实现）
# 实际中会转为 DFA 以获得 O(m) 匹配
return states
Level 3 · 规范怎么定义的
3.1 Thompson (1968)：正则引擎的起源
Ken Thompson 在论文 "Programming Techniques: Regular Expression Search Algorithm"（发表于 CACM 1968 年 6 月）中，描述了如何将正则表达式编译为 IBM 7094 的机器码。这是历史上第一个实用的正则引擎。
Thompson 的核心贡献：
-
NFA 构造规则：每种正则操作（连接、选择、闭包）都有固定的 NFA 构造模板，每个模板最多增加 2 个状态。因此 NFA 状态数 = O(m)（m = 模式长度）。
-
并行模拟：不是一次追踪一条路径（那会导致回溯），而是同时追踪所有可能的状态。每读一个输入字符，更新所有当前状态的集合。
-
时间保证：每步最多处理 m 个状态，每个状态最多 2 条出边，所以每步 O(m)。总时间 O(nm)。
Thompson 构造规则的精确定义：
1. 单字符 'a':
s --a--> e
(一个起始状态 s，一条标记为 a 的边，一个结束状态 e)
2. 连接 AB:
A.end --ε--> B.start
(A 的结束状态通过 ε 边连接 B 的起始状态)
3. 选择 A|B:
ε --> A.start
s -<
ε --> B.start
A.end --ε--> e
B.end --ε--> e
(新起始状态 s 通过 ε 边分别连接 A 和 B，
A 和 B 的结束状态通过 ε 边连接新结束状态 e)
4. 闭包 A*:
ε --> A.start
s -< A.end --ε--> e
ε --> e --ε--> A.start (回环)
(起始状态可以跳过 A 直接到结束状态，
A 的结束状态可以回到 A 的开始重新匹配)
3.2 Russ Cox (2007)："Regular Expression Matching Can Be Simple and Fast"
Russ Cox 在 2007 年发表了这篇极具影响力的文章（不是正式论文，是 blog post，但被广泛引用），展示了一个惊人的对比：
匹配正则 a?^n a^n 对文本 a^n（即 n 个可选的 a 后跟 n 个必须的 a，匹配 n 个 a）：
| n | Perl/Python (回溯) | Thompson NFA |
|---|---|---|
| 10 | 0.0001s | 0.0001s |
| 20 | 0.01s | 0.0001s |
| 25 | 1s | 0.0001s |
| 30 | 60s | 0.0001s |
| 100 | 永远跑不完 | 0.0001s |
为什么回溯法在这里是指数级的？
正则 a?a?a?aaa 匹配 "aaa"：
- 每个
a?有两种选择：匹配或不匹配 - 回溯法尝试所有 2^n 种组合
- 实际只在最后才能确认最佳匹配方案
Thompson NFA 则同时维护所有可能的状态，每步 O(n) 即可。
Cox 的关键论点：
"Perl, PCRE, Python, Ruby, Java, and many other languages have regular expression implementations based on recursive backtracking that are simple but can be exponentially slow. In contrast, Thompson's algorithm, which the author learned from reading the Plan 9 grep source, guarantees linear time."
这篇文章直接催生了 Google 的 RE2 引擎。
3.3 Myers (1986)：差异算法的数学基础
Eugene Myers 在 "An O(ND) Difference Algorithm and Its Variations"（Algorithmica, 1986）中严格证明了：
定理 1：算法在 O(ND) 时间和 O(D^2) 空间内找到最短编辑脚本，其中 N = n + m，D = 编辑距离。
定理 2：使用分治技巧（类似 Hirschberg 1975），空间可以降到 O(D^2) 同时保持 O(ND) 时间。
关键引理：在编辑图的第 d 步中，每条对角线 k 上的最远可达点 V[d][k] 满足：
V[d][k] = max( V[d-1][k-1] + 1, (从上方到达) V[d-1][k+1] (从左方到达) ) + (沿对角线能走多远)
这个递推关系使得算法只需要 O(D) 空间存储当前层的 V 值。
3.4 Kleene (1956) 和正则语言的等价性
Stephen Kleene 在 1956 年的论文 "Representation of Events in Nerve Nets and Finite Automata" 中证明了正则表达式和有限自动机的等价性（Kleene 定理）：
定理：一个语言是正则的，当且仅当它可以被以下之一描述：
- 一个正则表达式
- 一个 DFA
- 一个 NFA
这三种表示之间可以相互转换：
- 正则 -> NFA：Thompson 构造（1968），O(m) 状态
- NFA -> DFA：子集构造（Rabin & Scott, 1959），最坏 O(2^m) 状态
- DFA -> 正则：状态消除法，O(2^n) 长度
为什么反向引用让正则超出了正则语言？
现代"正则表达式"支持反向引用 \1、\2 等，这些实际上超出了正则语言的表达能力。例如 (a+)\1 匹配 "aa", "aaaa", "aaaaaa" 等（长度为偶数的 a 串），这不是正则语言（可以用泵引理证明）。
支持反向引用的匹配问题是 NP-Complete 的（Aho, 1990），这就是为什么回溯法在这类模式上不可避免地慢。
3.5 Ukkonen (1985)：编辑距离的对角线技巧
Esko Ukkonen 在 "Algorithms for Approximate String Matching"（Information and Control, 1985）中给出了另一个 O(kn) 的编辑距离算法（k = 编辑距离，n = 文本长度），它和 Myers 1986 的算法思路相似但角度不同：
- Myers：按编辑距离 d 逐层展开，在编辑图上前进
- Ukkonen：计算 DP 表时只计算带宽为 2k+1 的对角线带
两者都利用了"当编辑距离小时，只需探索一小部分搜索空间"的思想。
Level 4 · 边界与陷阱
4.1 正则表达式灾难性回溯（ReDoS）
灾难性回溯（Catastrophic Backtracking）或 ReDoS（Regular Expression Denial of Service）是一类安全漏洞：精心构造的输入可以让正则引擎运行指数级时间。
典型的有问题模式：
import re
import time
# 危险模式 1：嵌套量词
# (a+)+ 匹配 "aaaaX" 时会灾难性回溯
# 因为有无数种方式把 a 分成若干组
# 危险模式 2：重叠选择
# (a|a)* 匹配 "aaaaX" 同样灾难性
# 危险模式 3：实际中的例子
# ^(([a-z])+.)+[A-Z]([a-z])+$ # email 验证
def demonstrate_redos():
"""演示 ReDoS 攻击"""
# 安全：使用 re2 或设置超时
pattern = re.compile(r'(a+)+b')
for n in [10, 15, 20, 22, 24]:
text = 'a' * n + 'X' # 永远不会匹配
start = time.time()
try:
result = pattern.match(text)
except Exception:
pass
elapsed = time.time() - start
print(f"n={n:2d}: {elapsed:.4f}s (result={result})")
if elapsed > 5:
print(" 太慢了，停止测试")
break
# demonstrate_redos() # 取消注释运行（注意可能很慢！）
ReDoS 的根本原因：
回溯引擎在匹配失败时需要回溯所有已做的选择。如果模式中有嵌套的量词或重叠的选择，选择数量是指数级的。
防御策略：
- 使用 Thompson NFA 引擎：RE2, Rust regex, Go regex — 保证线性时间
- 静态分析工具：检测有问题的正则模式
- 设置超时：限制正则匹配的最大时间
- 原子组和占有量词：防止回溯（但需要引擎支持）
# Python 中的防御
import signal
class RegexTimeout(Exception):
pass
def timeout_handler(signum, frame):
raise RegexTimeout("正则匹配超时!")
def safe_regex_match(pattern: str, text: str, timeout_sec: float = 1.0):
"""带超时的安全正则匹配"""
signal.signal(signal.SIGALRM, timeout_handler)
signal.setitimer(signal.ITIMER_REAL, timeout_sec)
try:
result = re.match(pattern, text)
signal.setitimer(signal.ITIMER_REAL, 0)
return result
except RegexTimeout:
return None # 超时，视为不匹配
4.2 面试题：正则表达式匹配（LeetCode #10）
def is_match(s: str, p: str) -> bool:
"""
LeetCode #10: Regular Expression Matching
实现支持 '.' 和 '*' 的正则表达式匹配
'.' 匹配任意单字符
'*' 匹配零个或多个前面的元素
方法：动态规划
dp[i][j] = s[:i] 是否匹配 p[:j]
时间复杂度：O(nm)
空间复杂度：O(nm)，可优化到 O(m)
"""
n, m = len(s), len(p)
# dp[i][j] = s 的前 i 个字符是否匹配 p 的前 j 个字符
dp = [[False] * (m + 1) for _ in range(n + 1)]
dp[0][0] = True
# 初始化：空字符串 s 匹配 "a*b*c*..." 的情况
for j in range(2, m + 1):
if p[j-1] == '*':
dp[0][j] = dp[0][j-2]
for i in range(1, n + 1):
for j in range(1, m + 1):
if p[j-1] == '*':
# * 的两种选择：
# 1. 匹配零次：忽略 pattern 的最后两个字符
dp[i][j] = dp[i][j-2]
# 2. 匹配一次或多次：当前字符匹配 * 前面的字符
if p[j-2] == '.' or p[j-2] == s[i-1]:
dp[i][j] = dp[i][j] or dp[i-1][j]
elif p[j-1] == '.' or p[j-1] == s[i-1]:
# 普通字符或 . 匹配
dp[i][j] = dp[i-1][j-1]
return dp[n][m]
# 测试
test_cases = [
("aa", "a", False),
("aa", "a*", True),
("ab", ".*", True),
("aab", "c*a*b", True),
("mississippi", "mis*is*p*.", False),
]
for s, p, expected in test_cases:
result = is_match(s, p)
status = "PASS" if result == expected else "FAIL"
print(f"[{status}] is_match('{s}', '{p}') = {result}")
4.3 面试题：通配符匹配（LeetCode #44）
def is_match_wildcard(s: str, p: str) -> bool:
"""
LeetCode #44: Wildcard Matching
'?' 匹配任意单字符
'*' 匹配任意字符串（包括空串）
注意：这里的 '*' 和正则的 '*' 不同！
正则的 '*' 修饰前一个字符，通配符的 '*' 独立匹配任意序列。
方法 1：动态规划 O(nm)
"""
n, m = len(s), len(p)
dp = [[False] * (m + 1) for _ in range(n + 1)]
dp[0][0] = True
# 初始化：p 的前缀全是 * 时可以匹配空串
for j in range(1, m + 1):
if p[j-1] == '*':
dp[0][j] = dp[0][j-1]
for i in range(1, n + 1):
for j in range(1, m + 1):
if p[j-1] == '*':
# * 匹配空（dp[i][j-1]）或匹配当前字符（dp[i-1][j]）
dp[i][j] = dp[i][j-1] or dp[i-1][j]
elif p[j-1] == '?' or p[j-1] == s[i-1]:
dp[i][j] = dp[i-1][j-1]
return dp[n][m]
def is_match_wildcard_greedy(s: str, p: str) -> bool:
"""
方法 2：贪心双指针 O(nm) 最坏，但平均 O(n+m)
思路：
- 遇到 '*' 时记录位置，先假设它匹配空串
- 如果后面匹配失败，回退到上一个 '*'，让它多匹配一个字符
"""
n, m = len(s), len(p)
si, pi = 0, 0
star_pi, star_si = -1, -1
while si < n:
if pi < m and (p[pi] == '?' or p[pi] == s[si]):
si += 1
pi += 1
elif pi < m and p[pi] == '*':
star_pi = pi
star_si = si
pi += 1 # 先假设 * 匹配空串
elif star_pi != -1:
# 回退到上一个 *，让它多匹配一个字符
star_si += 1
si = star_si
pi = star_pi + 1
else:
return False
# 检查 pattern 剩余部分是否全是 *
while pi < m and p[pi] == '*':
pi += 1
return pi == m
# 测试
test_cases = [
("aa", "a", False),
("aa", "*", True),
("cb", "?a", False),
("adceb", "*a*b", True),
("acdcb", "a*c?b", False),
]
for s, p, expected in test_cases:
result1 = is_match_wildcard(s, p)
result2 = is_match_wildcard_greedy(s, p)
status = "PASS" if result1 == expected else "FAIL"
print(f"[{status}] wildcard('{s}', '{p}') = {result1} (greedy={result2})")
4.4 编辑距离变体在面试中的应用
变体 1：只允许删除操作（LCS 问题）
如果编辑操作只有"删除"，那么把 A 变成 B 的最少删除次数 = |A| + |B| - 2*LCS(A, B)。
变体 2：通配符删除（One Edit Distance, LeetCode #161）
def is_one_edit_distance(s: str, t: str) -> bool:
"""
判断两个字符串是否恰好编辑距离为 1
O(n) 时间，O(1) 空间
"""
n, m = len(s), len(t)
if abs(n - m) > 1:
return False
if n > m:
return is_one_edit_distance(t, s)
# 现在 n <= m
for i in range(n):
if s[i] != t[i]:
if n == m:
# 替换：剩余部分必须相同
return s[i+1:] == t[i+1:]
else:
# 插入/删除：s[i:] 必须等于 t[i+1:]
return s[i:] == t[i+1:]
# 所有对应字符都相同，只有长度差 1 时才是 distance 1
return n + 1 == m
变体 3：编辑距离 + 路径还原
def edit_distance_with_operations(a: str, b: str) -> tuple[int, list[str]]:
"""
计算编辑距离并返回具体操作序列
用于实现 diff 工具的"最小修改建议"
"""
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = i
for j in range(m + 1):
dp[0][j] = j
for i in range(1, n + 1):
for j in range(1, m + 1):
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
# 回溯操作
ops = []
i, j = n, m
while i > 0 or j > 0:
if i > 0 and j > 0 and a[i-1] == b[j-1]:
ops.append(f"keep '{a[i-1]}'")
i -= 1
j -= 1
elif i > 0 and j > 0 and dp[i][j] == dp[i-1][j-1] + 1:
ops.append(f"replace '{a[i-1]}' with '{b[j-1]}'")
i -= 1
j -= 1
elif j > 0 and dp[i][j] == dp[i][j-1] + 1:
ops.append(f"insert '{b[j-1]}'")
j -= 1
else:
ops.append(f"delete '{a[i-1]}'")
i -= 1
ops.reverse()
return dp[n][m], ops
# 演示
dist, ops = edit_distance_with_operations("kitten", "sitting")
print(f"编辑距离: {dist}")
print("操作序列:")
for op in ops:
print(f" {op}")
4.5 实际工程中的正则引擎选择
| 引擎 | 语言/工具 | 类型 | 反向引用 | 时间保证 |
|---|---|---|---|---|
| PCRE | PHP, Nginx | 回溯 | 支持 | 无（可能指数） |
| Python re | Python | 回溯 | 支持 | 无 |
| RE2 | C++/Go | NFA/DFA | 不支持 | O(nm) |
| Rust regex | Rust | NFA/DFA | 不支持 | O(nm) |
| Hyperscan | Intel | DFA + 硬件加速 | 不支持 | O(n) |
选择指南：
- 如果输入可能来自用户/外部：必须用 RE2/Rust regex（防 ReDoS）
- 如果需要反向引用且输入可控：Python re 够用
- 如果需要极高吞吐量：Hyperscan（网络入侵检测等）
4.6 综合对比：匹配算法全景
| 算法 | 问题 | 时间 | 适用场景 |
|---|---|---|---|
| KMP/BM | 精确单模式匹配 | O(n+m) | 简单搜索 |
| Aho-Corasick | 精确多模式匹配 | O(n+m+z) | 敏感词过滤 |
| Rabin-Karp | 精确匹配（多模式） | O(n+m) 期望 | 剽窃检测 |
| 后缀数组 | 文本索引 | O(m log n) 查询 | 全文搜索 |
| 编辑距离 | 模糊匹配 | O(nm) | 拼写检查 |
| Myers diff | 最短编辑脚本 | O(ND) | 版本比较 |
| Thompson NFA | 正则匹配 | O(nm) | 安全搜索 |
| 回溯法 | 正则+反向引用 | O(2^n) 最坏 | 复杂模式 |
4.7 本章总结
这一章把"匹配"的概念从精确匹配扩展到了三个方向：
- 模糊匹配：容许编辑距离的搜索（BK 树、Trie + DP、Levenshtein 自动机）
- 差异比较：找两个序列的最短编辑脚本（Myers diff，Git 的核心）
- 模式匹配：正则表达式引擎（回溯法 vs Thompson NFA）
核心教训：
- 回溯法简单但危险——ReDoS 是真实的安全威胁
- Thompson NFA 保证线性时间但不支持反向引用
- Myers diff 利用"大多数差异很小"的假设，在实践中极快
- 编辑距离虽然是 O(nm)，但有很多加速技巧（BK 树、Trie、对角线优化）
理解这些算法不仅能帮你解面试题，更能帮你理解：Git 是怎么工作的、搜索引擎是怎么处理拼写错误的、Web 服务为什么会被正则表达式拖垮。