ここでは 正規表現の性能・効率問題とアンチパターン、特に catastrophic backtracking（爆発的バックトラッキング） について、Python 初心者以上向けにやさしく解説します。実例つきで「なぜ遅くなるのか」「どう避けるか」を整理します。
1. 正規表現の内部処理
- Python の
reモジュールは NFA（非決定性有限オートマトン）方式を使っています。 - 正規表現は マッチできるパターンの分岐を順に試す ことで結果を探します。
- この試行回数が膨大になる場合、処理が極端に遅くなることがあります。
2. Catastrophic Backtracking（爆発的バックトラッキング）
- 「マッチできるかどうかを試す分岐が多すぎて、処理時間が指数的に増える現象」
- 特に ネストした量指定や選択パターン が絡むと起こります。
例：典型的な危険パターン
import re
pattern = r"(a+)+$"
text = "a" * 30 + "b"
import time
start = time.time()
re.match(pattern, text)
print("経過秒:", time.time() - start)
解説
(a+)+は「a が1回以上の塊が1回以上」の意味。- 文字列
"a"*30 + "b"は最後にbがあるためマッチしません。 - Python は「a の塊の取り方を何通りも試す → 最後に b で失敗 → 別の分け方で再試行」を行うため、組み合わせが指数的に増えます。
- 文字数が増えると 処理時間が爆発的に伸びる（数秒 → 数十秒 → 数分）ことがあります。
3. 他のアンチパターン
選択パターンの組み合わせ
pattern = r"(cat|catt|cattl|cattle)+$"
text = "cattlcattlcattl" # マッチしない場合
re.match(pattern, text)
- 選択肢が多く、共通部分がある場合にバックトラッキングが増えます。
- 「cat」「catt」「cattl」「cattle」の共通部分
catがネックになります。
ネストした量指定
pattern = r"(a|aa)*$"
text = "a" * 20 + "b"
- 「a または aa の0回以上」の組み合わせをすべて試す → 遅くなる。
4. 避け方・対策
1. 過剰なグループ化を避ける
- 不要な括弧
()はキャプチャをしない(?:...)に置き換える。
2. 貪欲量指定の組み合わせを避ける
(a+)+よりa+を使う。.*の多用も危険。
3. Possessive / Atomic の考え方
- Python 標準の
reには直接はないが、後方参照やグループ内マッチの再試行を減らす工夫が有効。 - 例：分割して処理、もしくは
regexモジュール（サードパーティ）を使うと atomic グループや possessive 修飾子が使える。
4. 非貪欲（lazy）量指定で試行回数を減らす
*?/+?にすると「最小マッチ」を優先。
text = "<div>abc</div><div>def</div>"
re.findall(r"<div>.*?</div>", text) # 非貪欲で効率的
5. 文字列長が大きい場合は分割して処理
- ログや大きなファイルは、行単位やチャンク単位で処理すると安全。
6. 単純なパターンなら正規表現を使わず文字列操作で
str.find,str.split,str.startswithなどでも対応できる場合はそちらを優先。
5. 性能チェック
- Python では
timeモジュールで計測可能。 - 実務で長い文字列を扱う場合は「この正規表現で数百万文字にマッチできるか？」を事前にテストするのが重要。
import time, re
pattern = r"(a+)+$"
text = "a" * 25 + "b"
start = time.time()
re.match(pattern, text)
end = time.time()
print("処理時間:", end - start)
- 処理が 0.1 秒以下なら許容、数秒以上ならアンチパターンの可能性あり。
6. まとめ
- 正規表現は強力だが危険もある → 長さや量指定、選択パターンに注意。
- catastrophic backtracking は「分岐が多すぎて指数時間」になるパターン。
- 避ける方法：
- 不要なグループ化を避ける（
(?:)） - 貪欲量指定の多重ネストを避ける
- 非貪欲
*?/+?を活用 - 大きなテキストは分割して処理
- 必要なら文字列操作や
regexモジュールを使う
- 不要なグループ化を避ける（
- 実務では「パターンの長さ・テキスト量・バックトラック可能性」を意識して設計することが重要。