正規表達式效能優化指南：避免回溯爆炸，寫出高效正規表達式

正規表達式效能：一個表達式拖垮整個服務

災難性回溯（Catastrophic Backtracking）可以讓一個正規表達式比對耗時從毫秒級飆升到小時級。

場景	正規表達式	輸入長度	耗時
正常比對	`/^abc$/`	100	<1ms
線性回溯	`/a*b/`	100	~1ms
指數回溯	`/(a+)+b/`	30	~10s
指數回溯	`/(a)b/`	30	~10s

一、回溯機制原理

NFA 引擎的運作方式

JavaScript 使用 NFA（非確定性有限自動機） 引擎，採用回溯演算法：

輸入: "aaaac"
正規表達式: /(a+)+c/

比對過程:
1. (a+) 比對 "aaaa" → 嘗試 +c → 不符合 'c'
2. 回溯: (a+) 比對 "aaa" → (a+) 比對 "a" → 嘗試 +c → 不符合
3. 回溯: (a+) 比對 "aa" → (a+) 比對 "aa" → 嘗試 +c → 不符合
4. 回溯: (a+) 比對 "aa" → (a+) 比對 "a" → (a+) 比對 "a" → ...
5. ... 指數級回溯

回溯次數計算

對於 /(a+)+b/ 比對 "aaa..."（n 個 a）：

回溯次數 ≈ 2^n

n=10: 約 1,024 次
n=20: 約 1,048,576 次
n=30: 約 1,073,741,824 次

二、常見災難性回溯模式

模式一：巢狀量詞

// 災難性回溯
/(a+)+b/     // 巢狀 + 量詞
/(a*)*b/     // 巢狀 * 量詞
/(\w+)+@/    // 巢狀 \w+

// 修正：避免巢狀量詞
/a+b/        // 單層量詞
/(\w+)@/     // 單層量詞

模式二：有序交替

// 災難性回溯：交替選項有共同前綴
/(a|ab)+c/

// 輸入 "abababab..." 不符合時，引擎嘗試所有組合
// 回溯次數 ≈ O(2^n)

// 修正：提取共同前綴
/a(b?)+c/

模式三：重疊量詞

// 災難性回溯
/.*.*=/

// 兩個 .* 都可以比對相同內容，產生大量回溯

// 修正：合併量詞
/.*=/

模式四：回溯參照陷阱

// 災難性回溯
/^(b+)(a+)\1$/

// 輸入 "bbbbaaaa" 時，\1 的回溯嘗試所有 b+ 的子劃分

// 修正：如果可能，避免回溯參照，或限制量詞範圍
/^(b+)(a+)\1$/.test(input) // 僅用於短輸入

三、優化技巧

技巧一：具體化字元類別

// 慢：. 比對任何字元，大量回溯
/.*foo/

// 快：[^\n]* 不比對換行，減少回溯
/[^\\n]*foo/

// 更快：如果知道 foo 前面只有字母
/[a-z]*foo/

技巧二：錨定減少搜尋空間

// 慢：從每個位置嘗試比對
/foo/

// 快：如果 foo 在行首
/^foo/

// 快：如果 foo 在行尾
/foo$/

// 快：同時錨定
/^foo$/

技巧三：非貪婪量詞的正確使用

// 場景：提取 <b> 標籤內容

// 慢：貪婪量詞 + 回溯
/<b>(.*)<\/b>/

// 快：非貪婪量詞（但注意仍可能有回溯）
/<b>(.*?)<\/b>/

// 最快：排除字元類別（零回溯）
/<b>([^<]*)<\/b>/

方式	比對 `<b>hello</b><b>world</b>`	回溯
`(.*)`	`hello</b><b>world`	多次
`(.*?)`	`hello`	少量
`([^<]*)`	`hello`	零次

技巧四：原子群組（ES2024+）

// 原子群組 (?>...) 一旦比對就不再回溯
const regex = /^(?>a+)+b$/;

// 等價於：如果 a+ 比對了，就不回溯給外層 + 重試
// 比對 "aaab" → 成功
// 比對 "aaa" → 立即失敗（不指數回溯）

技巧五：佔有量詞（部分引擎）

// 佔有量詞 a++ 比對後不釋放給回溯
// JavaScript 不支援，但可用原子群組模擬
const regex = /^(?>(a+))b$/;

技巧六：預編譯 + 複用

// 慢：每次建立新 RegExp
function validate(input) {
  return /^[\w.+-]+@[\w-]+\.[\w.]+$/.test(input);
}

// 快：預編譯
const EMAIL_REGEX = /^[\w.+-]+@[\w-]+\.[\w.]+$/;
function validate(input) {
  return EMAIL_REGEX.test(input);
}

四、效能分析工具

使用工具庫正規表達式測試

開啟正規表達式工具
輸入正規表達式和測試文字
查看比對結果和耗時
調整正規表達式，對比優化前後效能

JS 內建測量

function measureRegex(regex, input, iterations = 1000) {
  const start = performance.now();
  for (let i = 0; i < iterations; i++) {
    regex.test(input);
  }
  const end = performance.now();
  return {
    totalTime: end - start,
    avgTime: (end - start) / iterations,
    iterations,
  };
}

// 對比
const slow = measureRegex(/(a+)+b/, 'a'.repeat(25));
const fast = measureRegex(/a+b/, 'a'.repeat(25));
console.log(`慢: ${slow.avgTime}ms, 快: ${fast.avgTime}ms`);

recheck 函式庫偵測危險正規表達式

npm install recheck

import { check } from 'recheck';

const result = check(/(a+)+b/);
// { safe: false, complexity: 'exponential' }

const result2 = check(/a+b/);
// { safe: true, complexity: 'linear' }

五、常見正規表達式的效能對比

正規表達式	複雜度	安全	優化版
`/(a+)+b/`	指數	❌	`/a+b/`
`/(a\|ab)+c/`	指數	❌	`/a(b?)+c/`
`/..=/`	指數	❌	`/.*=/`
`/(\d+){1,10}/`	多項式	⚠️	`/\d{1,10}/`
`/^[a-z]+$/`	線性	✅	—
`/^\d{4}-\d{2}-\d{2}$/`	常數	✅	—

六、伺服器端防護

逾時保護

function safeRegexTest(regex, input, timeoutMs = 100) {
  const start = Date.now();
  const result = regex.test(input);
  if (Date.now() - start > timeoutMs) {
    throw new Error('Regex timeout: possible catastrophic backtracking');
  }
  return result;
}

RE2 引擎（線性時間保證）

import RE2 from 're2';

// RE2 保證線性時間，無回溯爆炸
const regex = new RE2('(a+)+b');
regex.test('a'.repeat(100)); // 安全，不會卡住

限制輸入長度

function validateWithLimit(regex, input, maxLength = 1000) {
  if (input.length > maxLength) {
    throw new Error(`Input exceeds maximum length: ${maxLength}`);
  }
  return regex.test(input);
}

七、最佳實踐清單

避免巢狀量詞：(a+)+ → a+
具體化字元類別：. → [^\\n] 或更具體的類別
提取共同前綴：(a|ab) → a(b?)
用排除類別替代非貪婪：(.*?) → ([^<]*)
錨定減少搜尋空間：^ / $
預編譯正規表達式：避免重複建立
用 recheck 偵測：CI 中自動檢查危險正規表達式
伺服器端逾時保護：防止正規表達式 DoS
限制輸入長度：減少最壞情況的影響