では、先ほどの 爆発的バックトラッキングの危険パターン一覧 を Jupyter Notebook形式 に変換し、実際に Python で処理時間を計測できる教材にします。
ノートブックでは、以下の構成にします：
- 説明セル：正規表現の性能・爆発的バックトラッキングの簡単な解説
- 危険パターンリストセル：表形式で危険パターンと安全な書き換え例を掲載
- 実験セル：各危険パターンの処理時間を計測
- 実験セル：安全パターンの処理時間を計測
- まとめセル：どの書き方が安全か一目で分かる
以下はその Jupyter Notebook の Python コード例 です（セル区切り付き、コピーして .ipynb に変換可能）。
# ==========================
# セル1: 説明
# ==========================
"""
# 正規表現の性能と爆発的バックトラッキング実験
このノートブックでは、Pythonの正規表現で起こる
**Catastrophic Backtracking（爆発的バックトラッキング）**を
実際に確認し、どのパターンが危険で、どの書き方が安全かを
学習します。
- Python の re モジュールは NFA を使っているため、貪欲量指定や選択肢の多重ネストで処理が遅くなることがあります。
- 危険パターンと安全パターンの違いを、実際の処理時間で比較します。
"""
# ==========================
# セル2: 危険パターンと安全パターン
# ==========================
patterns = [
{"name":"多重ネスト", "danger": r"(a+)+$", "safe": r"a+$", "text": "a"*30+"b"},
{"name":"選択の共通部分", "danger": r"(a|aa)+$", "safe": r"a+$", "text": "a"*30+"b"},
{"name":"選択の多重共通部分", "danger": r"(a|aa|aaa)+$", "safe": r"a+$", "text": "a"*30+"b"},
{"name":"貪欲な任意文字", "danger": r"(.*a)+b", "safe": r"(.*?a)+b", "text": "a"*25+"b"},
{"name":"オプションと量指定", "danger": r"(a+)?a{30}b", "safe": r"a{31}b", "text": "a"*31+"b"},
{"name":"共通接頭辞OR", "danger": r"(a|b|ab)+c", "safe": r"[ab]+c", "text": "ababababx"},
{"name":"数字多重ネスト", "danger": r"(\d+)*$", "safe": r"\d+$", "text": "1234567x"},
{"name":"選択とキャプチャ", "danger": r"(ab|a)*c", "safe": r"(?:ab|a)*c", "text": "ababababx"},
{"name":"小文字多重ネスト", "danger": r"([a-z]+)+d", "safe": r"[a-z]+d", "text": "aaaaaaaax"},
{"name":"貪欲な.*と繰り返し", "danger": r"(a.*b)+c", "safe": r"(a.*?b)+c", "text": "axxxxxxxbxxxxxxc"},
]
import pandas as pd
df = pd.DataFrame(patterns)
df[["name","danger","safe","text"]]
# ==========================
# セル3: 危険パターンの処理時間計測
# ==========================
import re, time
print("=== 危険パターンの処理時間 ===")
for p in patterns:
start = time.time()
try:
re.match(p["danger"], p["text"])
except Exception as e:
print(p["name"], "Error:", e)
end = time.time()
print(f"{p['name']}: {end-start:.5f} 秒")
# ==========================
# セル4: 安全パターンの処理時間計測
# ==========================
print("=== 安全パターンの処理時間 ===")
for p in patterns:
start = time.time()
try:
re.match(p["safe"], p["text"])
except Exception as e:
print(p["name"], "Error:", e)
end = time.time()
print(f"{p['name']}: {end-start:.5f} 秒")
# ==========================
# セル5: まとめ
# ==========================
"""
# まとめ
- 危険パターンは文字列が長くなると秒単位、場合によっては無限級の時間がかかることがある
- 安全パターンに置き換えると、瞬時にマッチできる
- 置き換えのポイント：
1. 多重ネストを避ける
2. 貪欲量指定を非貪欲にする
3. OR の共通部分は文字クラスや非キャプチャグループでまとめる
4. 明確に回数を指定できる場合は `{m,n}` を使う
- 実務では正規表現を設計する際、まずこの表のパターンをチェックするだけで安全性が大きく向上する
"""
💡 ポイント
- このノートブックは 危険パターン vs 安全パターンの処理時間を体感できる教材 です。
- 実際にセルを実行すると、危険パターンは文字数によっては数秒以上かかるのが体感できます。
- 安全パターンは瞬時に処理されるため、正規表現設計の重要性が直感的に理解できます。