文字列の検証で、いくつかの正常な例がすぐ通っても、ほかの入力でも速いとは限りません。バックトラッキングを使う照合では、末尾に規則に合わない文字が一つ加わるだけで、失敗に成功よりずっと時間がかかる場合があります。

本文の問いは、最後に「一致しない」と返す式がなぜ大量の処理を必要とし、規則を保ちながらどう減らせるかです。固定したパターンと合成文字列をローカルで実行し、時間の増加、照合結果、キャプチャの差、タイムアウトによる中断を確認しました。サイトのAPI、サービスのスループット、別の正規表現エンジンは試していません。

例の規則は「空でなく、すべて小文字のaで構成される文字列」です。単純な規則だからこそ、必要な判定と式の書き方によるコストを分けて見られます。

規則と照合のインターフェースを決める

Pythonの fullmatch では、次の二つでこの規則を調べられます。

import re

re.fullmatch(r"(a+)+", "aaaa") is not None  # True
re.fullmatch(r"a+", "aaaa") is not None    # True

a+ は一つ以上のaです。(a+)+ は「一つ以上のaを含む部分を、一つ以上並べる」と、繰り返しをさらに一段重ねています。文字列全体が規則を満たすかだけを判定する場合、この追加の段は受け入れる文字列の種類を増やしません。

今回は既定のフラグで fullmatch を使い、文字列全体を検査します。search で部分文字列を探す実験ではありません。インターフェースも条件の一部です。どこかにaがあるかを探すだけなら、ほかの文字を含む入力にも一致する部分があり、問いが変わります。Python：fullmatchとsearchの違い

失敗例は "a" * n を "a" * n + "!" に変えて作ります。aの前半は同じですが、末尾の感嘆符で全体が規則を満たせなくなります。最終的には不一致でも、その答えを得るための探索が短いとは限りません。

成功は速く、末尾の失敗は急に遅くなる

環境は CPython 3.12.14、macOS 27.0.1、arm64 で、標準ライブラリの re のみを使いました。各条件を別の子プロセスで実行し、コンパイル済みの Pattern.fullmatch を3回、perf_counter_ns で計測しています。3回の値と中央値を保存しました。式のコンパイル、入力作成、プロセス起動は、この照合時間には含めません。

入れ子の (a+)+ の結果です。失敗列の全入力長はn+1です。

aの個数naだけの入力：成功の時間末尾に!を付ける：失敗の時間
16< 0.01 ms1.241 ms
18< 0.01 ms4.749 ms
20< 0.01 ms19.320 ms
22< 0.01 ms78.825 ms
24< 0.01 ms311.528 ms

25文字の失敗入力で、すでに約0.31秒かかりました。隣の行へ進むとaは二つしか増えませんが、今回の失敗時間はおよそ4倍になります。成功側には同じ規模の増加がありません。「いくつかの正常入力で速かった」よりも、有用な性能の情報です。

短い呼び出しはマイクロ秒前後かそれより短く、計時自体のコストやマシン状態の影響を受けます。そのため表では0.01ミリ秒未満とし、改善した書き方同士の微小な順位を付けていません。完全な値は添付しています。現在のパターン、入力、環境に限った実験で、Pythonの各バージョンやCPUの共通速度指標ではありません。

失敗してからも、分け方を試せてしまう

貪欲な繰り返しは、通常まずできるだけ多くの文字を消費します。後の条件が成立しないと、前の選択点へ戻って配分を変えます。Pythonの公式チュートリアルも、先に多く照合し、失敗後に戻って試す過程を説明しています。Pythonのチュートリアル：繰り返しとバックトラッキング

(a+)+ では同じ aaaa を4文字の一グループとしても、3と1、2と2、1と3、さらに多いグループとしても扱えます。内側の + は各グループの長さを、外側の + はグループ数を選びます。成功時は最初の大きなグループだけで通ります。末尾に ! がある場合、どの分け方でもそれをaにはできませんが、再試行できる選択が残ります。

分割の組み合わせは直接数えられます。n個のaにはn−1個の隙間があり、各隙間で分けるか分けないかを選ぶため、連続した空でないグループへの分割は 2^(n−1) 通りです。n=24なら 8,388,608 通りです。これは例の潜在的な分け方を数えた分析で、実測したインタープリターの命令数や正確な戻り回数ではありません。

複数の繰り返しが同じ前半を異なる方法で消費でき、失敗が最後に来る点が問題です。照合器は成功経路がないことを確認するため、候補を除外していきます。答えは短くても、それを確定する過程は長くなり得ます。バックトラッキングと状態集合を扱う算法の違いはRuss Coxの原文を参照できます。今回の計測は、そこに掲載された過去のベンチマークとは独立しています。Russ Cox：正規表現の照合算法

診断では、括弧と量指定子が複数あるだけで、この増加が必ず起きるとは判断できません。同じ入力を繰り返し部分へ配分する複数の再試行可能な方法があり、後続の失敗でそれらを除外し続ける必要があるかを調べます。固定した先頭部分で早く失敗する場合、繰り返しが消費する文字の範囲が重ならない場合、エンジンの処理方法が違う場合には、探索過程も変わり得ます。今回検証したのは示したパターンだけで、入れ子の繰り返しを含む式すべてが同じコストとは判断していません。

規則に不要な繰り返しを先に削る

真偽値だけが必要な今回の規則には、a+ で十分です。同じ文字列を複数のaグループへ再配分せず、最も直接的に書けます。受け入れるべき内容を明確にしてから式を選ぶ方が、冗長な式へ修飾を追加するより確認しやすくなります。

a+、アトミックグループを使う (?>a+)+、所有的量指定子の a++ も試しました。24個のaと最後の ! では次の結果です。

パターン全体に一致するか3回の計測の中央値
(a+)+いいえ311.528 ms
a+いいえ< 0.01 ms
(?>a+)+いいえ< 0.01 ms
a++いいえ< 0.01 ms

計時した成功・失敗入力に加え、空文字列、一つのa、複数のa、感嘆符付き、末尾改行付きも確認しました。さらに a、b、!、改行からなる長さ0–5の 1,365文字列を列挙しました。4パターンの判定は一致し、a から aaaaa までの5文字列だけが通りました。

有限の列挙は境界確認を補うものです。今回の受け入れ集合が同じことは、「空でないaの部分を一つ以上結合しても、空でないaの列になる」ことからも説明できます。任意の複雑な正規表現の書き換えを証明するものではありません。変更時は、正常な例だけでなく、規則の説明と失敗位置をカバーする入力を残す必要があります。

インターフェースには別の差もあります。(a+)+ が aaa に一致した後の .groups() は実測で ('aaa',)、残りの3パターンは空のタプルでした。同じ文字列を受け入れても、キャプチャの結果まで同じとは限りません。 呼び出す側がグループ番号、名前、置換内容を使うなら、その出力も調べます。真偽値の等価性だけで、呼び出し全体も等価とはしていません。

アトミックグループと所有的量指定子は選択を捨てる

Pythonは 3.11 からアトミックグループと所有的量指定子をサポートします。アトミックグループは退出後に内部の戻り先を捨て、所有的量指定子はできるだけ照合した後、後続部分のために文字を返しません。再試行を減らせますが、後の条件が成功できるかにも影響します。Python 3.11：追加された正規表現構文、構文の意味

実際に実行した短い反例です。

re.fullmatch(r"a+a", "aa") is not None   # True
re.fullmatch(r"a++a", "aa") is not None  # False

通常の a+ は最初に二つのaを消費しますが、最後のリテラルaに文字がなくなると一つ戻し、全体が一致します。a++ は消費後に戻さないため、最後のaが文字を得られず失敗します。入力は有効な aa でも、プラスを一つ足すことで結果が変わりました。

これらを使う前に、捨てるバックトラッキングが必要な成功に使われていないことを確かめます。境界が分かっている場合に使える構文で、遅い式すべてに自動追加する修正ではありません。今回の全aの文字列を調べるだけの規則では、明確な a+ がすでに必要な仕事を満たします。

待機の中断と不一致の確定は別の結果

32個のaと末尾の ! を入れ子の式で調べる例も実行し、subprocess.run の通信待機に 2秒のタイムアウトを設定しました。今回は完了した子プロセスの出力が得られず、TimeoutExpired を受けて中断と記録しています。照合結果は空のままで、False が返った測定を作っていません。

このタイムアウトは表の照合時間と測定範囲が違います。待機にはプロセス作成後に残る初期化と照合呼び出しが含まれ、作成と終了処理にはさらに実時間がかかる可能性があります。公式文書では、run はタイムアウト後に子プロセスを終了させ、その終了を待ちます。プロセス作成自体を中断できる保証はありません。Python：subprocess.runのタイムアウト

したがって「正規表現にちょうど2秒かかった」とは書けず、完了まで何秒必要かも算出できません。実験がどう待機を制限し、未完了を明確に残したかを示しています。外部の待機制限でパターンの計算量は変わりません。同じプロセス管理をサービスへ組み込んだ場合のコストも検証していません。

アプリケーションでは、成功、通常の不一致、待機のタイムアウトを別々に記録することも必要です。後の二つをどちらも「無効」と扱うと、判定が完了したかを見失います。制御できない入力を扱う場合、長さの上限は一度に処理する材料を制限できます。ただし、式が適切であることの証明や、失敗例の時間増加を調べる代わりにはなりません。許容するテキスト量と応答時間からしきい値を決める必要があり、本文では本番サービスへそのまま使える共通の値を提示していません。

実験を取得して、自分の失敗例を確認する

完全な実験パッケージを展開し、そのディレクトリで実行します。

python3.12 regex-backtracking-lab.py regex-backtracking-output

標準ライブラリだけを使い、Python 3.11以降が必要です。今回は3.12.14を使いました。スクリプト、実行説明、今回の完全な結果、生の計測CSVも取得できます。CSVは完了した条件だけで、中断例はJSONに別途記録します。再実行のミリ秒値は環境で変わります。

自分の式では、受け入れる規則とキャプチャ出力を書き、正常、空値、改行、成功に近いが後半で失敗する例を用意します。関係する前半を少しずつ長くして、失敗時間の増え方を調べます。今回は短い合成入力だけを試し、実際のテキスト分布、同時負荷、プログラム全体の遅延は測っていません。

エンジンの選択でも境界は変わります。RE2は入力長に対して線形の照合時間を保証する一方、後方参照や先読み・後読みなどはサポートしないと公式に説明しています。これは設計文書の内容で、本文ではRE2をインストールしたり比較したりしていません。変更には構文と照合出力の確認が必要です。RE2：時間の保証とサポート範囲

この問題を調べるには、「規則は正しいか」と「失敗を確定するまでに何をするか」を両方考えます。成功入力は早く一つの経路を見つけられても、失敗入力は多くの経路を除外する必要があります。本例では不要なグループの繰り返しを削ることで、規則を直接表せました。 アトミックグループ、所有的量指定子、外部タイムアウトにはそれぞれ役割がありますが、照合の意味、キャプチャのインターフェース、未完了状態も確認します。戻り値だけを見て失敗の過程を調べなければ、今回最も大きかったコストを見落とします。