正規表現エンジンと有限オートマトン

はじめに：正規表現の裏側に潜む数学の世界

プログラマであれば、文字列の検索や置換、入力値のバリデーションなどに日常的に「正規表現 (Regular Expression)」を利用していることでしょう。しかし、その簡潔な記法の裏で、どのようなアルゴリズムがテキストを解析しているのかを意識することは少ないかもしれません。

単純に見える正規表現の評価エンジンは、計算機科学の根幹をなす「オートマトン理論 (Automata Theory)」と密接に結びついています。この記事では、チョムスキー階層における正規言語の数学的定義から出発し、非決定性有限オートマトン (NFA) と決定性有限オートマトン (DFA) の違い、そして一部の正規表現エンジンが陥る「壊滅的バックトラック (Catastrophic Backtracking)」のリスクや、それを回避するためのThompson NFAを用いた高速化手法までを深掘りします。

チョムスキー階層と正規言語

計算機科学と言語学の交差点において、ノーム・チョムスキーは形式言語を生成する文法の能力に応じて4つの階層（チョムスキー階層）に分類しました。

タイプ0（句構造文法）: チューリングマシンで認識可能
タイプ1（文脈依存文法）: 線形拘束オートマトンで認識可能
タイプ2（文脈自由文法）: プッシュダウン・オートマトンで認識可能
タイプ3（正規文法）: 有限オートマトンで認識可能

私たちが扱う「正規表現」は、本来この「タイプ3（正規文法）」によって生成される「正規言語 (Regular Language)」を表現するための数学的記法です。正規言語は、状態の数が有限である「有限オートマトン (Finite Automaton)」によって正確に認識・受理することができます。

数学的には、アルファベット $\Sigma$ 上の正規表現は、空集合 $\emptyset$、空文字列 $\varepsilon$、および単一の文字 \in \Sigma$ を基底とし、和集合（選択 $|$）、連接（結合）、およびクリーネ閉包（繰り返し $*$）の3つの演算を有限回適用することで定義されます。

しかし、現代のプログラミング言語に実装されている正規表現（PCREなど）は、後方参照 (Backreference) などの拡張機能を持っているため、厳密にはチョムスキー階層の「正規言語」の枠を超え、文脈に依存するパターンのマッチングも可能になっています。これが、後に述べる計算複雑性の問題を引き起こす一因となっています。

有限オートマトン：NFAとDFA

正規表現を文字列と照合するためには、計算機が解釈できる状態遷移モデル、すなわち有限オートマトンへ変換する必要があります。有限オートマトンには、大きく分けて「非決定性有限オートマトン (NFA)」と「決定性有限オートマトン (DFA)」の2種類が存在します。

非決定性有限オートマトン (NFA: Nondeterministic Finite Automaton)

NFAの特徴は「非決定性」にあります。ある状態において、特定の入力文字を受け取った際の遷移先が複数存在したり、入力を全く消費せずに遷移する（$\varepsilon$ 遷移）ことが許されます。

NFAは正規表現の構造に非常に近く、Thompsonの構成法などのアルゴリズムを用いることで、正規表現からNFAへの変換は正規表現の長さに比例する (N)$ の時間と空間で機械的に行うことができます。しかし、シミュレーション（実行）の際には、複数の可能性を同時に追跡するか、バックトラックを用いて全てのパスを探索する必要があるため、単純な実装では実行時に時間がかかる場合があります。

mermaid graph LR S0["Start"] -- "a" --> S1["State 1"] S1 -- "ε" --> S2["State 2"] S1 -- "ε" --> S3["State 3"] S2 -- "b" --> S4["Accept"] S3 -- "c" --> S4

決定性有限オートマトン (DFA: Deterministic Finite Automaton)

DFAの特徴は、ある状態において特定の入力文字を受け取った際の遷移先が常にただ1つに決定される点です。$\varepsilon$ 遷移も許されません。

遷移先が一意であるため、入力文字列を先頭から1文字ずつ読み込みながら状態を遷移させるだけでマッチングが完了します。文字列の長さを $ とすると、実行時間は (M)$ となり、入力文字列の長さに対して線形時間で非常に高速に動作します。

しかし、NFAからDFAへの変換（部分集合構成法などを使用）には問題があります。NFAの複数の状態の集合をDFAの1つの状態としてマッピングするため、最悪の場合、DFAの状態数は元のNFAの状態数 $ に対して ^N$（指数関数的）に爆発する可能性があります。

壊滅的バックトラック (Catastrophic Backtracking) と ReDoS

多くの現代的な正規表現エンジン（Java, Python, PHP, Ruby, Perlなど）は、「バックトラック付きNFAエンジン」を採用しています。これらは厳密な数学的オートマトンではなく、深さ優先探索（DFS）を用いてマッチするパスを見つける再帰的なアルゴリズムで実装されています。

この手法は、後方参照や先読み (Lookahead) のような強力な機能を実装しやすいという利点がありますが、探索空間が指数関数的に増大する正規表現に対しては致命的な弱点を持ちます。

壊滅的バックトラックのメカニズム

例えば、次のような正規表現と対象文字列を考えてみましょう。

正規表現: ^(a+)+$
対象文字列: aaaaaaaaaaaaaaaaaaaX

文字列の末尾が X であるため、この正規表現は最終的にマッチに失敗するはずです。しかし、バックトラック付きNFAエンジンは失敗を確信するために、全ての可能なグループ化の組み合わせを試行しようとします。

最初、外側の + は文字列全体 aaaaaaaaaaaaaaaaaaa を1つのグループとして飲み込もうとしますが、末尾の $ にマッチしないためバックトラックします。
次に、aaaaaaaaaaaaaaaaaa との2つのグループに分けて試行します。
それでもダメなら、aaaaaaaaaaaaaaaaa と a、あるいは aaaaaaaaaaaaaaaaa ととのように、分割のパターンを次々と生成して探索を続けます。

入力文字数 $ に対して、試行回数は ^n$ に比例して増加します。文字数がわずか20〜30文字程度でも、計算量は数億回を超え、CPU使用率が100%に張り付いてプログラムがハングアップしたように見えます。これが「壊滅的バックトラック (Catastrophic Backtracking)」です。

正規表現によるDoS攻撃 (ReDoS)

この特性を悪用したのが ReDoS (Regular Expression Denial of Service) と呼ばれる攻撃手法です。攻撃者が意図的にバックトラックを誘発するような文字列をサーバーに送信することで、サーバーのCPUリソースを枯渇させ、サービスをダウンさせることができます。

Webアプリケーションにおいて、ユーザー入力を検証するための正規表現が脆弱である場合、このReDoS攻撃の標的となり得ます。例えば、メールアドレスのバリデーションなどで複雑な正規表現（ネストした量指定子など）を使っている場合は特に注意が必要です。

Thompson NFAと高速なエンジンの実装手法

ReDoSを防ぎ、どのような入力に対しても予測可能で安定したパフォーマンスを保証するためには、バックトラックに依存しない正規表現エンジンの実装が必要です。Go言語の egexp パッケージや、Rustの egex クレート、そしてGoogleの RE2 エンジンなどは、このようなアプローチを採用しています。

Thompson NFAシミュレーション

バックトラックによる深さ優先探索の代わりに、幅優先探索（BFS） のように「現在取り得る全てのアクティブな状態」を集合として同時に保持・更新していく手法が Thompson NFA シミュレーションです。

アルゴリズムの概要は以下の通りです。

初期化: 正規表現からNFAを構築し、開始状態から $\varepsilon$ 遷移で到達可能な全ての状態の集合（クロージャ）を「現在の状態集合」とする。
文字の消費: 入力文字列を1文字読み込む。
状態の更新: 「現在の状態集合」に含まれる各状態について、読み込んだ文字で遷移可能な状態を全て集める。
$\varepsilon$ 閉包の計算: ステップ3で集めた状態から、さらに $\varepsilon$ 遷移で到達可能な全ての状態を追加し、それを新しい「現在の状態集合」とする。
繰り返し: 入力文字列が尽きるまでステップ2〜4を繰り返す。
判定: 文字列を読み終えた時点で、「現在の状態集合」の中に「受理状態」が含まれていればマッチ成功、含まれていなければ失敗。

このアプローチの最大の利点は、ある入力文字に対して各状態を最大でも1回しか評価しない点です。入力文字列の長さを $、正規表現から構築されたNFAの状態数（正規表現の長さに比例）を $ とすると、実行時間は (M \times N)$ となり、バックトラックエンジンのような指数関数的な計算時間の爆発（(2^M)$）は絶対に起こりません。

DFAキャッシュ（Lazy DFA）

Thompson NFA シミュレーションは安全ですが、全ての遷移のたびに状態の集合を計算するため、純粋なDFA（実行時間 (M)$）に比べると定数倍のオーバーヘッドがあります。

そこで、現代的な高速エンジンでは「Lazy DFA（遅延DFA）」という最適化がよく用いられます。これは、NFAからDFAへの変換を事前のコンパイル時に全て行うのではなく、実行時に必要になった遷移（部分集合）だけを動的に計算し、その結果をメモリ（キャッシュ）に保存しておく手法です。

これにより、同じ遷移が再度必要になった場合はキャッシュされたDFAの遷移を (1)$ で引くことができ、DFAの高速性とNFAの省メモリ性・安全性を両立させています。

まとめ

正規表現は、単なる便利なツールではなく、その背後にはオートマトンという深い計算機科学の理論が存在します。

NFA は正規表現からの変換が容易ですが、実行時に複数のパスを考慮する必要があります。
DFA は実行が非常に高速ですが、変換時に状態数が爆発するリスクがあります。
多くの言語で採用されているバックトラック付きNFAエンジンは機能が豊富ですが、壊滅的バックトラックによるReDoSのリスクを抱えています。
Thompson NFA や Lazy DFA を採用したエンジン（RE2など）は、どのような入力に対しても線形時間のパフォーマンスを保証し、セキュアなシステム構築に不可欠です。

パフォーマンスやセキュリティがクリティカルに要求されるシステムを設計する際には、自分が使っているプログラミング言語の正規表現エンジンが「どのタイプの実装」であるかを理解し、用途に応じて適切なエンジンや正規表現の書き方を選択することが重要です。