正規表現パフォーマンス最適化ガイド：バックトラック爆発を避け、高速な正規表現を書く

テキストテキスト処理ツール

正規表現パフォーマンス：たった 1 つのパターンがサービス全体を止める

壊滅的バックトラック（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 回

二、よくある壊滅的バックトラックのパターン

パターン 1：ネストした量指定子

// 壊滅的バックトラック
/(a+)+b/     // + のネスト
/(a*)*b/     // * のネスト
/(\w+)+@/    // \w+ のネスト

// 修正：量指定子のネストを避ける
/a+b/        // 単一レベルの量指定子
/(\w+)@/     // 単一レベルの量指定子

パターン 2：順序付きの選択

// 壊滅的バックトラック：選択肢に共通プレフィックスがある
/(a|ab)+c/

// 入力 "abababab..." がマッチしない場合、エンジンは全組み合わせを試す
// バックトラック回数 ≈ O(2^n)

// 修正：共通プレフィックスを括り出す
/a(b?)+c/

パターン 3：重複する量指定子

// 壊滅的バックトラック
/.*.*=/

// 2 つの .* が同じ内容にマッチでき、大量のバックトラックが発生

// 修正：量指定子を統合
/.*=/

パターン 4：後方参照の罠

// 壊滅的バックトラック
/^(b+)(a+)\1$/

// 入力 "bbbbaaaa" では、\1 のバックトラックが b+ のあらゆる分割を試行

// 修正：可能なら後方参照を避けるか、量指定子の範囲を制限
/^(b+)(a+)\1$/.test(input) // 短い入力にのみ使用

三、最適化テクニック

テクニック 1：文字クラスを具体化する

// 遅い：. は任意の文字にマッチし、大量のバックトラックを生む
/.*foo/

// 速い：[^\n]* は改行にマッチせず、バックトラックを削減
/[^\\n]*foo/

// さらに速い：foo の前が英字だけと分かっている場合
/[a-z]*foo/

テクニック 2：アンカーで探索空間を絞る

// 遅い：すべての位置からマッチを試行
/foo/

// 速い：foo が行頭にある場合
/^foo/

// 速い：foo が行末にある場合
/foo$/

// 速い：両端をアンカー
/^foo$/

テクニック 3：非貪欲量指定子の正しい使い方

// シーン：<b> タグの内容を抽出

// 遅い：貪欲量指定子 + バックトラック
/<b>(.*)<\/b>/

// 速い：非貪欲量指定子（ただしバックトラックが残る場合あり）
/<b>(.*?)<\/b>/

// 最速：否定文字クラス（バックトラックゼロ）
/<b>([^<]*)<\/b>/
方法 <b>hello</b><b>world</b> にマッチ バックトラック
(.*) hello</b><b>world 多数
(.*?) hello 少量
([^<]*) hello ゼロ

テクニック 4：アトミックグループ（ES2024+）

// アトミックグループ (?>...) は一度マッチしたらバックトラックしない
const regex = /^(?>a+)+b$/;

// つまり：a+ がマッチしたら、外側の + のために文字を返さない
// "aaab" にマッチ → 成功
// "aaa" にマッチ → 即座に失敗（指数的バックトラックなし）

テクニック 5：強欲な量指定子（一部エンジン）

// 強欲な量指定子 a++ はマッチ後に文字をバックトラックへ渡さない
// JavaScript は未対応だが、アトミックグループでエミュレート可能
const regex = /^(?>(a+))b$/;

テクニック 6：プリコンパイルと再利用

// 遅い：呼び出しのたびに新しい RegExp を生成
function validate(input) {
  return /^[\w.+-]+@[\w-]+\.[\w.]+$/.test(input);
}

// 速い：プリコンパイル
const EMAIL_REGEX = /^[\w.+-]+@[\w-]+\.[\w.]+$/;
function validate(input) {
  return EMAIL_REGEX.test(input);
}

四、パフォーマンス分析ツール

ツールボックスで正規表現をテスト

  1. 正規表現ツールを開く
  2. 正規表現とテスト文字列を入力
  3. マッチ結果と所要時間を確認
  4. 正規表現を調整し、最適化前後の性能を比較

JS 組み込み API で計測

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);
}

七、ベストプラクティス チェックリスト

  1. 量指定子のネストを避ける：(a+)+ → a+
  2. 文字クラスを具体化する：. → [^\\n] など、より具体的なクラスへ
  3. 共通プレフィックスを括り出す：(a|ab) → a(b?)
  4. 非貪欲より否定文字クラス：(.*?) → ([^<]*)
  5. アンカーで探索空間を絞る：^ / $
  6. 正規表現をプリコンパイル：繰り返し生成を避ける
  7. recheck で検査：CI で危険な正規表現を自動チェック
  8. サーバーサイドでタイムアウト保護：正規表現 DoS を防止
  9. 入力長を制限：最悪ケースの影響を抑える
#正则表达式#性能优化#回溯#RegExp#文本处理