Python | 正規表現の性能とアンチパターン（上級向け）

Python
2022.03.19
スポンサーリンク

では、先ほどの 完全版 Notebook をそのまま .ipynb ファイルとして生成する Python スクリプト を作ります。

以下のコードを実行すると、regex_backtracking_complete.ipynb という Notebook ファイルが作成され、Jupyter でそのまま開いて学習できます。

import json

# ==========================
# 完全版 Notebook の構造
# ==========================
notebook = {
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 正規表現の性能と爆発的バックトラッキング 完全版\n",
    "\n",
    "このノートブックでは、以下を学習できます：\n",
    "1. 危険パターン vs 安全パターン\n",
    "2. 実際の処理時間の比較\n",
    "3. 爆発的バックトラッキングの分岐図\n",
    "4. 試行回数の指数的増加のアニメーション"
   ]
  },
  {
   "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",
    "from graphviz import Digraph\n",
    "from IPython.display import Image\n",
    "\n",
    "dot = Digraph(comment='Catastrophic Backtracking Example')\n",
    "dot.node('S', 'Start')\n",
    "dot.node('A1', 'a+ を1回目')\n",
    "dot.node('A2', 'a+ を2回目')\n",
    "dot.node('F', 'Fail (bで不一致)')\n",
    "dot.node('M', 'Match (成功)')\n",
    "dot.edges(['SA1', 'A1A2', 'A2F'])\n",
    "dot.edge('A2', 'A1', label='バックトラック')\n",
    "\n",
    "dot.render('backtracking_example', format='png', cleanup=True)\n",
    "Image('backtracking_example.png')"
   ],
   "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_complete.ipynb", "w", encoding="utf-8") as f:
    json.dump(notebook, f, ensure_ascii=False, indent=2)

print("regex_backtracking_complete.ipynb が生成されました。")
Python

✅ 実行すると：

  • regex_backtracking_complete.ipynb というファイルが生成
  • Jupyter Lab / Notebook で開けば：
    1. 危険パターンと安全パターンの表
    2. 処理時間比較
    3. 分岐図（Graphviz）
    4. 試行回数アニメーション

がすべて体験可能になります。

前へ
12345678
Python
スポンサーリンク
シェアする
@lifehackerをフォローする
スポンサーリンク
@lifehacker
スポンサーリンク
タイトルとURLをコピーしました