正規表現の量指定子：貪欲・最短・強欲とバックトラック実測

2026年11月改訂： この記事は2021年に韓国語で書いた講座を、日本語の読者向けに書き直したものです。元記事の5つの例を .NET 10、Python 3.9・3.12 の re、PHP 8.5（PCRE2 10.47）、Dart 3.11（JavaScript の規則に従う RegExp）で、同じ入力のまま実行し直しました。マッチ結果はどのエンジンでも同じでしたが、説明が2か所誤っていました。{3} は4桁の数字を除外せず、{2,4} も 12345 を除外しません。アンカーがなければ長い数字の内側でマッチを見つけます。強欲な量指定子、アトミックグループ、バックトラック時間の実測は新しく加えた内容です。

\d{3} と書いたのに想定外の値が通ってしまった人や、正規表現1つでリクエスト処理が固まった経験がある人向けの記事です。量指定子は直前の要素を何回繰り返してよいかを決めます。結果を左右するのは2つで、回数（{n}、{n,m}、*、+、?）とモード（貪欲・最短・強欲）です。回数の規則はエンジン間でほぼ共通ですが、モードはそうではなく、組み合わせを誤ると正規表現の呼び出し1回に数秒かかります。

*・+・? をメタ文字として初めて見る場合は、先にメタ文字の記事をどうぞ。「同じ文字の連続」を探すのは量指定子とは別の技法なので、同じ文字の連続を探す記事で扱います。

回数指定 {n}・{n,}・{n,m} を再確認

* は {0,}、+ は {1,}、? は {0,1} と同じです。元記事の例と、全エンジンの結果です。

パターン：[0-9]{3}       テキスト：12 / 123 / 1234 / 45678（1行に1つ）
結果　　：123、123、456

パターン：\d{3,}\.\d+    テキスト：123.456 / 12.3456 / 1.23456 / 1234.56 / 12345.6
結果　　：123.456、1234.56、12345.6

パターン：\d{2,4}        テキスト：1 / 12 / 123 / 1234 / 12345
結果　　：12、123、1234、1234

元記事は「[0-9]{3} は4桁なら一致しない」「[0-9]{2,4} は 12345 に一致しない」と書いていましたが、結果はそうなっていません。エンジンはパターンが当てはまる位置を探し、123 は 1234 の中に当てはまります。量指定子はその要素が消費する文字数を制限するだけで、前後に何があるかは見ません。「数字全体がその桁数」という意味にしたいなら、境界を付けます。

\b[0-9]{3}\b             → 123 だけ
^\d{2,4}$（複数行モード）  → 12、123、1234

郵便番号の「3桁-4桁」のように桁数そのものが規則の入力では、この違いがそのままバグになります。\d{3}-\d{4} だけだと 1234-56789 の中の 234-5678 にもマッチしてしまうので、^\d{3}-\d{4}$ と書きます。

量指定子がかかるのは直前の1要素だけです。ab+ は b だけを繰り返すので、abab abbb からは ab、ab、abbb が返りました。長いかたまりを繰り返すなら (ab)+ とまとめます。こちらは abab、ab でした。グループはグループの記事で詳しく扱います。

境界ケースも2つ確かめました。前後を逆にした a{3,1} は全エンジンでエラーです。

.NET   : Invalid pattern 'a{3,1}' at offset 6. Illegal {x,y} with x > y.
Python : min repeat greater than max repeat at position 2
PHP    : Compilation failed: numbers out of order in {} quantifier at offset 5
Dart   : FormatException: numbers out of order in {} quantifier.

最小値を省いた {,3} は移植できません。aaaa a{,3} に使うと、Python（3.9・3.12）と PHP は {0,3} と読んで aaa、a と複数の空マッチを返し、.NET と Dart は文字どおりに読んで a{,3} という文字列にマッチしました。Dart の unicode: true はエラーです。{0,3} と書きましょう。

貪欲な量指定子と最短一致

普通に書いた量指定子は貪欲（greedy）で、できるだけ多く取り、後ろのパターンが失敗したときだけ1文字ずつ返します。後ろに ? を付けると最短一致（lazy）になり、最小限だけ取って必要なときだけ伸ばします。元記事の例がいちばん分かりやすいままです。

テキスト：       <b>BOLD!</b><hr><b>BOLD!</b>
<b>.*</b>      → マッチ1件：行全体
<b>.*?</b>     → マッチ2件：<b>BOLD!</b>、<b>BOLD!</b>
<b>[^<]*</b>   → マッチ2件（最短一致と同じ）

全エンジンで同じでした。実務では3つ目のほうがよいことが多いです。中に入ってよい文字を否定クラスで決めておけば、戻る余地そのものがありません。最短一致にも意外な結果があります。\d{2,4}? を 12345 に使うと 12、34、\d??\d を 12 に使うと 1、2 でした。最短一致はどの長さから試すかを変えるだけで、成功するはずのマッチを失敗させることはありません。

強欲な量指定子とアトミックグループ

強欲な（possessive）量指定子は貪欲に取り、決して返しません。速さだけでなく結果も変わります。

テキスト：abc1
\w+\d        → abc1        （\w+ が abc1 を取り、1 を返す → \d が 1）
\w++\d       → マッチなし   （\w++ は 1 を返さない）
(?>\w+)\d    → マッチなし   （アトミックグループ：同じ動き）
[a-z]++\d    → abc1        （クラスが 1 を取れないので返す必要がない）

対応状況でエンジンが分かれます。エラーメッセージを覚えておくと原因にすぐ気づけます。

.NET 10    : Invalid pattern '\w++\d' at offset 4. Nested quantifier '+'.
Python 3.9 : multiple repeat at position 3
Python 3.9 : unknown extension ?> at position 1
Dart 3.11  : FormatException: Nothing to repeat \w++\d
Dart 3.11  : FormatException: Invalid group (?>\w+)\d

Python のドキュメントでは両方とも 3.11 で追加された機能とされており、実際に 3.9 は拒否し、3.12 は受け付けました。.NET では ++ の代わりにアトミックグループ (?>…) を使います。(?>\w+) は \w++ と同じ意味です。JavaScript、つまり Dart と Flutter にはどちらもないので、パターンの構造そのものを直すことになります。

バックトラック爆発の実測：(a+)+b

強欲・アトミックの形が本領を発揮するのは、マッチが失敗するときです。(a+)+b では、連続する a を内側の + と外側の + で分ける方法が指数的にあり、バックトラック型のエンジンはそれをすべて試してから失敗を宣言します。入力は "a" × n + "!b" です。! があるので必ず失敗しますが、入力の中に b は存在します。呼び出し1回の時間、Release ビルド、Apple Silicon Mac での結果です。

.NET 既定エンジンをもう一度測ると n = 22、24 は 773 ms と 3,047 ms で、.NET Compiled と Dart の2回目は表との差が4%以内でした。2文字増えるごとに約4倍です。このペースなら数十文字でリクエストが止まります。

直したパターンです。どれも aaab には今までどおり aaab でマッチすることを確認しました。

• (?>a+)+b（.NET、Python 3.12、PHP）と a++b（Python 3.12、PHP）：どの n でも 0.00 ms。a+ が一度取ったかたまりを分け直す余地がありません。
• 本来の意図であろう a+b：Dart を含む全エンジンで 0.00 ms。
• .NET の RegexOptions.NonBacktracking＋元の (a+)+b：0.01 ms 以下。ただしこのオプションはアトミックグループとは併用できません：RegexOptions.NonBacktracking is not supported in conjunction with expressions containing: 'atomic subexpressions (?> pattern)'。

PHP は違う動きをし、その違いが落とし穴です。JIT が有効な既定の状態で preg_match('/(a+)+b/', …) は、n = 16 では 0.52 ms で 0 を返しましたが、n ≥ 20 では約2 ms で false を返し、preg_last_error_msg() は Backtrack limit exhausted でした（pcre.backtrack_limit = 1,000,000）。JIT を切ると約12.5 ms 後に同じエラーです。サーバーは固まりませんが、if (preg_match(...)) だけで判定すると false を「マッチなし」として素通りします。また、入力に b がまったくないとき、PCRE2 は必須文字がないことを先に調べて 0.00 ms で 0 を返しました。.NET にはその近道がなく、"a" × 24 で 4,509 ms かかりました。

実務での量指定子の選び方

後方参照を含むパターンで同じ爆発がどう現れるかは後方参照の記事にあります。繰り返しグループの中の区切りが省略可能というだけで、26文字で2秒のタイムアウトに達しました。

検証方法

.NET 10.0.14（Regex.Matches、Stopwatch、Release）、Python 3.9.6・3.12.14（re.finditer、time.perf_counter）、PHP 8.5.6＋PCRE2 10.47（preg_match_all、hrtime、JIT あり・なし）、Dart 3.11.5（RegExp.allMatches、dart compile exe、Stopwatch）。Node.js は入っていなかったので、JavaScript の規則は Dart で確かめました。マッチの検証はパターンと入力を1つの JSON ファイルから読み、全エンジンが同じバイト列を見るようにしています。時間はウォームアップ後の1回の値なので、ベンチマークではなく桁を見るためのものです。

2026年11月、Apple Silicon Mac（macOS）で実測。