Python正規表現実践ガイド：reモジュールの基本からパフォーマンス最適化、ReDoSの内部動作まで

はじめに

正規表現はテキスト処理の強力なツールです。Python の re モジュールは Perl 互換の正規表現をサポートしており、ログ解析、データクレンジング、バリデーションなど幅広い場面で活用できます。

基本パターン

よく使うメタ文字

基本操作

import re

text = "2026-02-26 Error: Connection timeout (retry: 3)"

# match: 先頭からマッチ
m = re.match(r'\d{4}-\d{2}-\d{2}', text)
print(m.group())  # "2026-02-26"

# search: 最初のマッチを検索
m = re.search(r'retry: (\d+)', text)
print(m.group(1))  # "3"

# findall: すべてのマッチをリストで返す
numbers = re.findall(r'\d+', text)
print(numbers)  # ['2026', '02', '26', '3']

# sub: 置換
cleaned = re.sub(r'\d{4}-\d{2}-\d{2}', '[DATE]', text)
print(cleaned)  # "[DATE] Error: Connection timeout (retry: 3)"

グループとキャプチャ

名前付きグループ

log = "2026-02-26 14:30:45 [ERROR] Database connection failed"

pattern = r'(?P<date>\d{4}-\d{2}-\d{2}) (?P<time>\d{2}:\d{2}:\d{2}) \[(?P<level>\w+)\] (?P<message>.+)'
m = re.match(pattern, log)

if m:
    print(m.group('date'))     # "2026-02-26"
    print(m.group('level'))    # "ERROR"
    print(m.group('message'))  # "Database connection failed"
    print(m.groupdict())       # {'date': '2026-02-26', 'time': '14:30:45', ...}

非キャプチャグループ

# (?:...) はグループ化するがキャプチャしない
pattern = r'(?:https?|ftp)://[\w./\-]+'
urls = re.findall(pattern, "Visit https://example.com or ftp://files.example.com")
print(urls)  # ['https://example.com', 'ftp://files.example.com']

先読みと後読み

肯定先読み / 否定先読み

# 肯定先読み: (?=...) — 後に続くがマッチには含まない
passwords = ["abc123", "password", "Str0ng!Pass", "12345"]
strong = [p for p in passwords
          if re.match(r'(?=.*[A-Z])(?=.*\d)(?=.*[!@#$%^&*]).{8,}', p)]
print(strong)  # ['Str0ng!Pass']

# 否定先読み: (?!...) — 後に続かない
# "test" で始まらない行
lines = ["test_func", "main_func", "test_class", "helper"]
non_test = [l for l in lines if re.match(r'(?!test)\w+', l)]
print(non_test)  # ['main_func', 'helper']

肯定後読み / 否定後読み

# 肯定後読み: (?<=...)
text = "Price: $100, Tax: $8, Total: $108"
amounts = re.findall(r'(?<=\$)\d+', text)
print(amounts)  # ['100', '8', '108']

# 否定後読み: (?<!...)
text = "v1.0 v2.0-beta v3.0 v4.0-rc1"
stable = re.findall(r'v[\d.]+(?!-)', text)
print(stable)  # ['v1.0', 'v3.0']

実践パターン集

メールアドレスの抽出

text = "Contact us at info@example.com or support@test.co.jp"
pattern = r'[\w.+-]+@[\w-]+\.[\w.]+'
emails = re.findall(pattern, text)
print(emails)  # ['info@example.com', 'support@test.co.jp']

CSV の安全な分割

# カンマ区切りだがクォート内のカンマは無視
line = 'John,"Doe, Jr.",30,"New York, NY"'
pattern = r',(?=(?:[^"]*"[^"]*")*[^"]*$)'
fields = re.split(pattern, line)
print(fields)  # ['John', '"Doe, Jr."', '30', '"New York, NY"']

IPアドレスの検証

def is_valid_ipv4(ip):
    pattern = r'^(?:(?:25[0-5]|2[0-4]\d|[01]?\d\d?)\.){3}(?:25[0-5]|2[0-4]\d|[01]?\d\d?)$'
    return bool(re.match(pattern, ip))

print(is_valid_ipv4("192.168.1.1"))   # True
print(is_valid_ipv4("256.1.1.1"))     # False

パフォーマンス最適化

コンパイル済みパターン

同じパターンを繰り返し使う場合は re.compile() でプリコンパイルします。

# 非効率: ループ内で毎回コンパイル
for line in lines:
    re.search(r'\d{4}-\d{2}-\d{2}', line)

# 効率的: 事前コンパイル
date_pattern = re.compile(r'\d{4}-\d{2}-\d{2}')
for line in lines:
    date_pattern.search(line)

貪欲マッチ vs 非貪欲マッチ

html = '<div>Hello</div><div>World</div>'

# 貪欲（デフォルト）: 最長一致
print(re.findall(r'<div>.*</div>', html))
# ['<div>Hello</div><div>World</div>']

# 非貪欲: 最短一致（?を追加）
print(re.findall(r'<div>.*?</div>', html))
# ['<div>Hello</div>', '<div>World</div>']

正規表現エンジンの内部動作:バックトラッキングと ReDoS

ここまでのパターンはすべて一瞬でマッチします。しかし正規表現エンジンの内部動作を理解していないと、一見無害なパターンが特定の入力に対して指数関数的に遅くなるという落とし穴にはまります。この現象は ReDoS（Regular Expression Denial of Service）と呼ばれ、CWE-1333「非効率な正規表現の複雑さ」に分類される、実務で繰り返しインシデントを引き起こしてきた脆弱性クラスです。

バックトラッキング型エンジン vs 有限オートマトン型エンジン

正規表現エンジンには大きく2つの実装方式があります。

Python の re はバックトラッキング型です。マッチに失敗すると「直前に選んだ分岐点まで戻って、別の可能性を試す」という再帰的な探索を行います。この探索木のサイズは通常は入力サイズに比例しますが、特定のパターン構造では入力サイズに対して指数的に膨れ上がることがあります。

一方、RE2 や Rust の regex クレートは Thompson NFA（1968年に Ken Thompson が考案し、Russ Cox が2007年の記事群で再評価した手法）に基づき、すべての可能な状態を同時に追跡することで、バックトラックなしに入力長に対して線形時間を保証します。その代償として、後方参照のように NFA では原理的に表現できない機能はサポートしません（実際、後方参照を含む正規表現のマッチング判定は NP困難であることが知られています）。表現力の高さと最悪計算量の保証はトレードオフの関係にあります。

なぜバックトラッキングは指数時間になりうるのか

正規表現界で最も有名な「壊滅的バックトラッキング（catastrophic backtracking）」パターンが (a+)+b です。これを 'a' * n（b を含まない、a だけが n 個並んだ文字列）に対してマッチさせるケースを考えます。

外側の (...)+ は内側のグループ (a+) を1回以上繰り返します。内側の a+ は貪欲に a を連続して食べますが、外側の + が繰り返し回数を決めるため、エンジンは「n 個の a を、内側グループが何回・それぞれ何文字ずつ消費するか」のあらゆる分割方法を試すことになります。

n 個の連続した同一文字を、1個以上の要素を持つ連続したグループへ分割する方法の数は**組成数（compositions）**として知られており、\(2^{n-1}\) 通りです。例えば n=4（"aaaa"）の場合、分割は次の8通りです。

• {aaaa}
• {aaa, a} / {a, aaa}
• {aa, aa}
• {aa, a, a} / {a, aa, a} / {a, a, aa}
• {a, a, a, a}

\(2^{4-1} = 8\) 通りと一致します。文字列の末尾に b が存在しないため、エンジンはこれらすべての分割を試した上で最終的に失敗を確定させます。つまりバックトラッキング探索木の葉の数は \(O(2^n)\) で、マッチング（失敗の確定を含む）にかかる時間も \(O(2^n)\) になります。

同様の構造を持つ古典的な危険パターンには次のようなものがあります。

• (a|a)*b — 同じ文字にマッチする2つの選択肢を持つ交替を繰り返す
• (a|aa)*b — 部分的に重なる長さの選択肢を繰り返す
• (.*)* — 任意文字列の繰り返しを二重にネストする

いずれも「同じ入力の一部を複数の異なる方法で消費できる、量指定子のネスト」が根本原因です。なお、すべての ReDoS が指数的とは限りません。例えば CVE-2025-27789 （Babel が名前付きキャプチャグループをトランスパイルする際に生成する .replace 用ポリフィル）は2乗の複雑度を持つケースで、指数ほど劇的ではなくても十分に長い入力に対してはサービス停止を引き起こし得ます。

実測:壊滅的バックトラッキングの増大を計測する

理論だけでなく、実際にタイミングを測定します。安全のため signal.alarm によるタイムアウトガードを設け、1回のマッチが3秒を超えたら強制的に打ち切ります（Unix系OS・メインスレッド限定の機能です。Windows やマルチスレッド環境では concurrent.futures.ProcessPoolExecutor と future.result(timeout=...) の組み合わせが移植性のある代替手段になります）。

import re
import time
import signal


class RegexTimeout(Exception):
    """1回の match() 呼び出しが安全タイムアウトを超えたときに送出する。"""


def _on_alarm(signum, frame):
    raise RegexTimeout()


def timed_match(pattern, text, timeout_sec=3):
    """pattern.match(text) を1回実行し、timeout_sec 秒で打ち切る。

    SIGALRM を使うため、壊滅的バックトラッキングが発生しても
    このスクリプト自身が timeout_sec 秒以上ハングすることはない。
    """
    signal.signal(signal.SIGALRM, _on_alarm)
    signal.alarm(timeout_sec)
    start = time.perf_counter()
    try:
        re.match(pattern, text)
        return time.perf_counter() - start
    except RegexTimeout:
        return None
    finally:
        signal.alarm(0)


CATASTROPHIC = r'(a+)+b'

for n in [10, 12, 14, 16, 18, 20, 22, 24, 25, 26]:
    text = 'a' * n  # 末尾に 'b' を置かない = 必ずマッチ失敗する
    t = timed_match(CATASTROPHIC, text, timeout_sec=3)
    print(f"n={n:3d}  time={t}")

Python 3.14 / macOS 上で実際に実行した結果です（1回のみの実測値。壊滅的パターンは繰り返し測定するには遅すぎるため平均化していません）。

2文字増えるごとにおよそ4倍、つまり1文字あたり約2倍というペースで実行時間が増えており、理論値である \(2^{n-1}\) と定性的に一致します（マイクロベンチマーク特有のノイズはありますが、傾向は明確です）。n=10 から n=26 の16文字増加で実行時間はおよそ24,000倍になりました。このベンチマークを n=27 以降まで伸ばすと3秒のタイムアウトに達するため、安全のためそこで打ち切っています。

同じ入力長の範囲で、ネストを解消した安全なパターン a+b を測定すると劇的な違いが分かります（1回では短すぎて測れないため、3,000回の呼び出しを平均しています）。

n=10 から n=26 まで実行時間はほぼ一定（数百ナノ秒オーダーの固定オーバーヘッドが支配的）です。真の線形性を確認するには、もっと大きな n が必要です。同じ a+b を n=1,000 と n=10,000 で測定すると、平均実行時間は 1.06 µs → 8.11 µs となり、入力長が10倍になっても実行時間はおよそ7.6倍にしかならず、指数関数ではなく線形（\(O(n)\) ）に増加していることが確認できます。

両方のパターンを同じ軸でプロットすると、その差は一目瞭然です。

安全な書き換えと Python 3.11 の対策機構

DANGEROUS = r'(a+)+b'      # ネストした量指定子: 壊滅的バックトラッキングの原因
SIMPLIFIED = r'a+b'        # 冗長なネストを解消（意味的に同じ言語を受理）
ATOMIC = r'(?>a+)+b'       # Python 3.11+: アトミックグループでバックトラック禁止
POSSESSIVE = r'(a++)+b'    # Python 3.11+: 所有量指定子でバックトラック禁止

(?>...)（アトミックグループ）と所有量指定子 *+ / ++ / ?+ / {m,n}+ は Python 3.11 で re モジュールに追加されました。どちらも「一度確定した部分にはバックトラックしない」という制約を課すことで、曖昧な分割の探索そのものを打ち切ります。実測でも、ATOMIC と POSSESSIVE は SIMPLIFIED と同等の速度まで高速化されることを確認しました。

いずれも n に対してほぼ線形で、(a+)+b の指数爆発とは無縁です。**「同じ文字集合を消費できる量指定子を入れ子にしない」**が最も基本的な回避ルールですが、既存の複雑なパターンを安全に書き換えられない場合は、アトミックグループや所有量指定子で局所的にバックトラックを封じ込めるのが実践的な選択肢です。

ReDoS:実世界の脆弱性としての壊滅的バックトラッキング

壊滅的バックトラッキングは学術的な好奇心の対象ではなく、実運用で繰り返し重大インシデントを引き起こしてきた確立された脆弱性クラスです。攻撃者は数十〜数百文字程度の短い入力を送るだけで、サーバーの CPU を長時間占有させ、他のリクエストを処理不能にできます。

Node.js エコシステムでは、広く使われる引数エスケープ用パッケージ cross-spawn の正規表現に ReDoS が存在した CVE-2024-21538 のように、依存パッケージが実際に脆弱性を抱えていた例が繰り返し報告されています。Python の re モジュール自体には組み込みのタイムアウトや計算量の上限機構がありません。信頼できない入力（ユーザー投稿、外部API応答など）を正規表現に通す前に、入力長を制限する、あるいは本記事のようにタイムアウトで保護する設計が必須です。第三者ライブラリの regex パッケージ（PyPI）は timeout 引数を関数に直接渡せるため、stdlib の re からの移行先として有力です。

一方、RE2 や Rust の regex クレートのような有限オートマトン型エンジンは、設計上 ReDoS が原理的に発生しません（その代わり後方参照などの表現力を犠牲にしています）。信頼できない入力を大量に処理するサービス（WAF、ログパイプライン、API Gateway 等）では、正規表現エンジンの選択自体がセキュリティ上の意思決定になります。

近年の研究・実例では、以下が参考になります。

• Bhuiyan, M. H. M., Çakar, B., Burmane, E. H., Davis, J. C., & Staicu, C.-A. (2025). “SoK: A Literature and Engineering Review of Regular Expression Denial of Service (ReDoS).” ASIA CCS ‘25. ReDoS の検知・防止・緩和に関する研究を体系的に整理したサーベイ。Cloudflare や Stack Overflow の実際の障害事例にも言及している。
• Su, W., Huang, H., Li, R., Chen, H., & Ge, T. (2024). “Towards an Effective Method of ReDoS Detection for Non-backtracking Engines.” USENIX Security ‘24. RE2 のような非バックトラック型エンジンでも実装の内部最適化次第では性能劣化が起こりうることを示し、検知手法を提案。
• CVE-2024-21538 （cross-spawn、npm）。広く依存される引数エスケープパッケージの正規表現に存在した ReDoS。実運用のサプライチェーンにおけるリスクを示す実例。

re モジュールの主要フラグ

pattern = re.compile(r'''
    (?P<year>\d{4})   # 年
    -(?P<month>\d{2}) # 月
    -(?P<day>\d{2})   # 日
''', re.VERBOSE)

関連記事

• Pythonデコレータ完全ガイド - デコレータと正規表現を組み合わせたバリデーションパターンが実用的です。
• Python asyncio入門 - 非同期テキスト処理における正規表現の活用法です。
• Pythonでプログレスバーを自作する - Pythonの実践的なTipsを紹介しています。
• Matplotlib実践Tips：論文品質のグラフを作る - Python実践Tipsとして可視化のベストプラクティスを紹介しています。

参考文献

• Python re module documentation
• Friedl, J. E. F. (2006). Mastering Regular Expressions (3rd ed.) . O’Reilly Media.
• Regular Expressions 101 - オンラインテストツール
• DevToolBox 正規表現テスター - ブラウザ上でリアルタイムに正規表現をテストできる無料ツールです。
• Bhuiyan, M. H. M., Çakar, B., Burmane, E. H., Davis, J. C., & Staicu, C.-A. (2025). “SoK: A Literature and Engineering Review of Regular Expression Denial of Service (ReDoS).” ASIA CCS ‘25.
• Su, W., Huang, H., Li, R., Chen, H., & Ge, T. (2024). “Towards an Effective Method of ReDoS Detection for Non-backtracking Engines.” USENIX Security ‘24.
• CVE-2024-21538 — Regular Expression Denial of Service (ReDoS) in cross-spawn - GitHub Advisory Database.
• CWE-1333: Inefficient Regular Expression Complexity - MITRE.
• OWASP: Regular expression Denial of Service - ReDoS
• Cox, R. (2007). “Regular Expression Matching Can Be Simple And Fast.” - Thompson NFA によるバックトラックなし線形時間マッチングの解説。RE2 設計の背景。