正規表現の仕組み — 「注文番号だけ」を見つけるルール

ひよこ

注文番号だけを探したいとき、正規表現を使うの？

ペンギン先生

文字の並び方をルールで書いて探せるよ。たとえば注文番号を「ORD-とASCIIの数字3桁」と決めれば、ORD-[0-9]{3}でその並びを探せる。まずは下の短い例を動かしてみよう。

ひよこ

角かっこと波かっこには、どんな意味がある？

ペンギン先生

[0-9]は0から9のうち1文字、{3}はその条件を3回繰り返す意味だよ。ORD-はそのままの文字。少しずつ分けると、記号だけの呪文ではなく読める条件になるんだ。

ひよこ

見つかったら、入力全体が正しいってこと？

ペンギン先生

検索と入力全体の検証は別だよ。ORD-1234でも、途中のORD-123だけは見つかる場合がある。Pythonならfullmatchなどで全体を見る。何桁を許すかなど、先に入力の仕様を決めるんだ。

ひよこ

中では、文字を順に確かめているの？

ペンギン先生

文字に応じて次の状態へ進む考え方で理解できるよ。ただし実際のエンジンには複数の実装がある。NFAとDFAは状態のモデル、バックトラッキングは候補を戻って試す方法で、同じものの名前ではないんだ。

ひよこ

NFAなら、必ず戻りながら試すの？

ペンギン先生

そうとは限らないよ。複数の候補の状態を同時に持って進む実装もある。RE2もNFA/DFA等の手法を組み合わせる。NFAは遅い、DFAなら何でも最速、という二分では覚えないようにしよう。

ひよこ

同じルールでも、急に遅くなることがある？

ペンギン先生

曖昧な繰り返しを戻って試すと、入力によって候補が大きく増える場合があるよ。ReDoSというサービス妨害にもつながる。入力の長さやパターン、エンジンの保証を合わせて考えるんだ。

ひよこ

できるだけ短く取る「怠惰」にすれば安全？

ペンギン先生

探す順を変える機能で、計算量の問題を必ず解決するものではないよ。RE2は固定した式に対し入力長に線形な照合を目指すけれど、後方参照や先読み等の対応に制限がある。必要な機能も確認しよう。

ひよこ

メールやHTMLも、この方法だけで分かる？

ペンギン先生

メールの書式チェックと届けられることは別だよ。HTML、JSON、CSV等の構造を読むときは専用パーサーを使おう。固定した文字を探すだけなら通常の文字列検索も分かりやすい。まずは目的に合う小さな条件から始めよう。

まずは、「ORD-と数字3桁」を探す

長い一覧から注文番号だけを拾うとき、正規表現で文字の並びのルールを書けます。Python 3が使えるなら、regex-demo.pyとして保存し、python regex-demo.pyで試してみましょう。

import re

pattern = r"ORD-[0-9]{3}"
text = "受付 ORD-123 / 問い合わせ ORD-456"
print(re.findall(pattern, text))
print(bool(re.fullmatch(pattern, "ORD-123")))
print(bool(re.fullmatch(pattern, "ORD-1234")))

['ORD-123', 'ORD-456']
True
False

検索して見つけることと、入力全体がルールに合うことは別です。findallは一致する部分を集め、fullmatchは入力全体を見ます。この例は独自に決めた注文番号の書式で、実在する店舗の番号を検証するルールではありません。

Pythonの\dはASCII以外のUnicodeの数字にも一致し得ます。言語・フラグで意味が違うので、ここでは対象を明示して[0-9]にしています。

状態のモデルと、試し方を分ける

文字を読んで次の状態へ進む図は、仕組みを理解する助けになります。DFAは現在の状態と入力から次が一意に決まるモデル、NFAは複数の可能性を持つモデルです。

NFAだから必ずバックトラッキングするわけではありません。候補を同時に進める実装もあり、RE2のように複数の手法を使うエンジンもあります。後方参照等の拡張機能も含めると、理論上の正規言語のモデルだけでは実際の機能すべてを説明できません。

もう少し詳しく：ReDoSと使い分け

戻って候補を試す実装では、曖昧な繰り返しと不一致になる入力等の組み合わせで、計算量が大きくなる場合があります。入力上限、時間制限の有無、パターンの見直し、エンジン選定を合わせて考えます。怠惰な量指定子に替えるだけで安全になるとは限りません。

RE2は式を固定したときの入力長に対する線形な照合時間を保証しますが、後方参照やlook-aroundには対応しません。入力の長さだけでなく式の複雑さやメモリの条件もあります。「どんな式でも最速」とは違います。

2019年7月2日のCloudflareの障害報告では、WAFの式による過剰なバックトラッキングと、展開や保護の仕組み等の複合した問題が説明されています。短い式を本物の原因の式として置き換えず、詳しく調べる場合は一次報告を読みましょう。

メールの書式だけで到達先や所有者は分かりません。HTML・JSON・CSV等には専用パーサーがあり、固定文字の有無だけなら通常の文字列検索も候補です。速度は目的と入力で測り、どちらが常に速いとは決めません。

🐧 ペンギン先生のまとめ：「正規表現」って出てきたら「文字の並び方を書いて、探すためのルール」と思えばだいたいOK！

データを読む形式はシリアライズの仕組み、Pythonでの練習はPython入門へ進めます。

参考資料

• Python：re — findall/fullmatch・繰り返し・Unicodeの数字
• MDN：Regular expressions — パターンと検索・各記号の役割・実装ごとの文法
• Google：RE2 — 入力長の線形性と対応しない拡張機能
• Cloudflare：2019年7月2日の障害報告 — 原因の正規表現と過剰なバックトラッキング・展開等の条件