操作して学ぶ
正規表現エンジン可視化
正規表現はオートマトン（NFA）にコンパイルできます。パターンを Thompson 構成で状態機械に変換し、 入力を1文字ずつ送りながら「今どの状態が生きているか」を追って照合の仕組みを見てください。
aabb
0/4 文字消費・生存状態 6 個
青＝現在生きている状態。二重丸＝受理状態。破線＝ε遷移（文字を消費しない）。
正規表現は Thompson 構成で ε-NFA にコンパイルできます。照合は「今いる状態の集合」を1文字ごとに更新するだけ—— 状態数は高々一定なので入力長に線形で済みます。バックトラック方式が(a+)+ で指数爆発するのと対照的で、これが RE2 などが速い理由です。
なぜこの方式は速いのか
- 状態は常に「集合」：分岐しても候補を同時に保持するので、状態数は高々一定。1文字進めるコストも一定。
- 入力長に線形：全体で O(入力長 × 状態数)。
(a+)+のような入れ子でも爆発しない。 - バックトラック方式との違い：PCREなど多くの言語標準は後方参照のためにバックトラックし、最悪ケースで指数時間（ReDoS）に。RE2やRustのregexはこのNFA方式で最悪計算量を保証している。