正規表現エンジンの仕組みを丁寧に解説 — なぜ`.*`は時々「遅く」なるのか

この記事で伝えること

正規表現（regex）は多くのプログラマが日常的に使うツールですが、その内部でどんな処理が行われているかを意識する機会は少ないのではないでしょうか。この記事を読むと、以下のことがわかります。

• 正規表現がどのように「状態機械（オートマトン）」に変換されて実行されるか
• DFA方式とNFA方式（バックトラック方式）の違い
• なぜ一部の正規表現が「壊滅的バックトラック（catastrophic backtracking）」を起こして極端に遅くなるのか
• 実務で正規表現を書くときに気をつけるべきポイント

コードだけでなく、内部の仕組みを理解することで、「なぜかこの正規表現だけ遅い」という問題に強くなれます。

正規表現は「状態機械」に変換される

正規表現エンジンは、書かれたパターン文字列をそのまま解釈しているわけではありません。内部では以下のようなステップで処理されます。

1. 構文解析: a(b|c)*d のようなパターンを、連結・選択・繰り返しなどの構造を持つ木（AST: 抽象構文木）に変換する
2. 状態機械への変換: ASTを、文字を1つずつ読みながら状態を遷移させる「オートマトン」に変換する
3. マッチング実行: 入力文字列に対して、状態機械を動かしながら一致するかを判定する

ここで重要なのが、状態機械には大きく分けて NFA（非決定性有限オートマトン） と DFA（決定性有限オートマトン） の2種類があるという点です。

NFA方式とDFA方式の違い

DFA方式

DFAは「ある状態である文字を読んだら、次に行く状態は必ず1つに決まる」という性質を持ちます。そのため、入力文字列の長さに比例した時間（線形時間）で必ずマッチング判定が終わります。grepの一部の実装や、GoogleのRE2ライブラリはこの方式を採用しています。

NFA方式（バックトラック方式）

一方、多くのプログラミング言語（Python標準のre、PCRE、JavaScriptの正規表現など）はNFAベースの「バックトラック方式」を採用しています。これは「ある文字を読んだときに複数の遷移先候補があれば、1つを試してダメだったら別の候補に戻ってやり直す」という仕組みです。

バックトラック方式は後方参照（\1など）や先読み（(?=...)）といった高度な機能をサポートできる代わりに、入力によっては指数関数的に時間がかかるという弱点を持っています。

具体例：壊滅的バックトラックを体験する

次のようなパターンを考えてみます。

import re
import time

# (a+)+b というパターン。b がないと大量のバックトラックが発生する
pattern = re.compile(r"(a+)+b")

for n in [10, 15, 20, 25]:
    text = "a" * n  # 末尾にbがない
    start = time.time()
    pattern.match(text)
    elapsed = time.time() - start
    print(f"n={n}: {elapsed:.4f}秒")

実際に実行すると、nが1増えるごとに実行時間がおよそ2倍になっていくのが確認できます。これは(a+)+という「繰り返しの中に繰り返し」があるパターンが、aの数だけ膨大な数の分割パターンを試すためです。例えばaaaaを(a+)+にマッチさせる分割方法は、a|a|a|a、aa|a|a、a|aa|aなど指数関数的に増えていきます。

このような正規表現は「evil regex」とも呼ばれ、Webアプリケーションの入力バリデーションに使われていると、悪意あるユーザーがわざと遅い入力を送りつけることでサービスを止める ReDoS（Regular Expression Denial of Service） 攻撃の原因にもなります。

実務で気をつけるポイント

壊滅的バックトラックを避けるために、以下のような対策が有効です。

• ネストした繰り返しを避ける: (a+)+のような「繰り返しの中の繰り返し」はできるだけ避け、a+のように単純化する
• 曖昧さを減らす: .*を多用せず、[^"]*のように「何にマッチしないか」を明示することで候補を絞り込む
• タイムアウトを設定する: ライブラリによってはマッチングに制限時間を設けられるものもあり、外部入力を扱う場合は検討する
• DFAベースのライブラリを使う: Pythonならreの代わりにre2（GoogleのRE2のPythonバインディング）を使うと、後方参照など一部機能とのトレードオフはあるものの、指数時間の問題を回避できる

筆者の考え・所感

正規表現は「習うより慣れろ」で書けるようになる一方、内部の仕組みを知らないまま使い続けると、思わぬ落とし穴にハマりやすいツールだと感じています。個人的には、正規表現がバックトラックで動いているという事実を知ってから、パターンを書くときに「このパターンは入力次第で候補が爆発的に増えないか」を意識するようになりました。

特に、ユーザー入力をそのままバリデーションする正規表現を書くときは要注意です。自分が「動作確認したから大丈夫」と思っていても、想定していない長さ・パターンの入力が来た瞬間にサーバーのCPUを食いつぶす、というのは実務でも十分起こり得る話です。パフォーマンステストの一環として、意図的に「長くて紛らわしい入力」を正規表現に食わせてみるのは良い習慣だと思います。

また、DFAとNFAという概念自体は、正規表現に限らずコンパイラの字句解析やネットワークプロトコルの状態遷移など、様々な場所に登場する基礎的な考え方です。正規表現をきっかけにオートマトン理論に触れておくと、他の分野の理解にも応用が効くという点も、この分野を学ぶ面白さだと感じています。

まとめ

• 正規表現は内部でNFAまたはDFAという状態機械に変換されて実行される
• DFA方式は線形時間で安全だが、NFA(バックトラック)方式は後方参照などの高機能をサポートできる代わりに指数時間になる場合がある
• (a+)+のようなネストした繰り返しは壊滅的バックトラックを引き起こしやすいため、外部入力を扱う正規表現では特に注意が必要