では、今まで作った内容を そのまま Jupyter Notebook (.ipynb) ファイルとして保存可能 にするコード例を作ります。これを実行すると、Notebook ファイルが生成され、すぐに開いて学習・実験できます。
Notebook を .ipynb に保存する Python コード
import json
# ==========================
# ノートブック構造の作成
# ==========================
notebook = {
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 正規表現の性能と爆発的バックトラッキング実験\n",
"このノートブックでは、Python の正規表現で起こる\n",
"**Catastrophic Backtracking** を体感・可視化します。\n",
"- 危険パターン vs 安全パターンの処理時間比較\n",
"- バックトラックの分岐図\n",
"- アニメーションによる指数的増加の可視化"
]
},
{
"cell_type": "code",
"metadata": {},
"source": [
"# 危険パターンと安全パターン\n",
"patterns = [\n",
" {\"name\":\"多重ネスト\", \"danger\": r\"(a+)+$\", \"safe\": r\"a+$\", \"text\": \"a\"*30+\"b\"},\n",
" {\"name\":\"選択の共通部分\", \"danger\": r\"(a|aa)+$\", \"safe\": r\"a+$\", \"text\": \"a\"*30+\"b\"},\n",
" {\"name\":\"貪欲な任意文字\", \"danger\": r\"(.*a)+b\", \"safe\": r\"(.*?a)+b\", \"text\": \"a\"*25+\"b\"},\n",
" {\"name\":\"オプションと量指定\", \"danger\": r\"(a+)?a{30}b\", \"safe\": r\"a{31}b\", \"text\": \"a\"*31+\"b\"},\n",
" {\"name\":\"共通接頭辞OR\", \"danger\": r\"(a|b|ab)+c\", \"safe\": r\"[ab]+c\", \"text\": \"ababababx\"},\n",
" {\"name\":\"数字多重ネスト\", \"danger\": r\"(\\d+)*$\", \"safe\": r\"\\d+$\", \"text\": \"1234567x\"}\n",
"]\n",
"\n",
"import pandas as pd\n",
"df = pd.DataFrame(patterns)\n",
"df[\"name danger safe text\" .split()]"
],
"execution_count": None,
"outputs": []
},
{
"cell_type": "code",
"metadata": {},
"source": [
"# 危険パターンの処理時間計測\n",
"import re, time\n",
"print('=== 危険パターンの処理時間 ===')\n",
"for p in patterns:\n",
" start = time.time()\n",
" try:\n",
" re.match(p['danger'], p['text'])\n",
" except Exception as e:\n",
" print(p['name'], 'Error:', e)\n",
" end = time.time()\n",
" print(f\"{p['name']}: {end-start:.5f} 秒\")"
],
"execution_count": None,
"outputs": []
},
{
"cell_type": "code",
"metadata": {},
"source": [
"# 安全パターンの処理時間計測\n",
"print('=== 安全パターンの処理時間 ===')\n",
"for p in patterns:\n",
" start = time.time()\n",
" try:\n",
" re.match(p['safe'], p['text'])\n",
" except Exception as e:\n",
" print(p['name'], 'Error:', e)\n",
" end = time.time()\n",
" print(f\"{p['name']}: {end-start:.5f} 秒\")"
],
"execution_count": None,
"outputs": []
},
{
"cell_type": "code",
"metadata": {},
"source": [
"# 爆発的バックトラッキングのアニメーション例\n",
"import matplotlib.pyplot as plt\n",
"import matplotlib.animation as animation\n",
"\n",
"n_max = 15\n",
"x = list(range(1, n_max+1))\n",
"y = [2**(i-1) for i in x] # 試行回数指数増加\n",
"\n",
"fig, ax = plt.subplots()\n",
"line, = ax.plot([], [], 'ro-', lw=2)\n",
"ax.set_xlim(0, n_max+1)\n",
"ax.set_ylim(0, max(y)*1.1)\n",
"ax.set_xlabel('文字列長 n')\n",
"ax.set_ylabel('バックトラック試行回数')\n",
"ax.set_title('Catastrophic Backtrackingの試行回数増加')\n",
"\n",
"def init():\n",
" line.set_data([], [])\n",
" return line,\n",
"\n",
"def animate(i):\n",
" line.set_data(x[:i+1], y[:i+1])\n",
" return line,\n",
"\n",
"ani = animation.FuncAnimation(fig, animate, frames=n_max, init_func=init, blit=True, repeat=False)\n",
"plt.show()"
],
"execution_count": None,
"outputs": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"name": "python",
"version": "3.11"
}
},
"nbformat": 4,
"nbformat_minor": 5
}
# ==========================
# 保存する
# ==========================
with open("regex_backtracking_tutorial.ipynb", "w", encoding="utf-8") as f:
json.dump(notebook, f, ensure_ascii=False, indent=2)
print("regex_backtracking_tutorial.ipynb が生成されました。")
💡 このコードを実行すると：
regex_backtracking_tutorial.ipynbという Notebook ファイルが作成されます- Jupyter Lab / Notebook で開くとすぐに 危険パターン vs 安全パターンの処理時間 や アニメーションで指数増加を体感 できます
- そのまま教材・演習用に使えます