バックトラッカーの挑戦状：欲張り・怠惰・強欲

朝、事務所のドアの隙間に黒い封筒が挟まっています。中にはカードが1枚。所長はカードを明かりにかざして眺め、机の上に置きます。「やっと挨拶に来たか。顔の代わりに署名で」

^(a|aa)+$

이 패턴은 정답을 맞힌다. 그런데 왜 이렇게 느린가?
답은 패턴으로 보내라.
                                        (a+)+$

カードの文面は韓国語です。訳すとこうなります。「このパターンは正解を当てる。なのに、なぜこんなに遅いのか？ 答えはパターンで送れ」

「正規表現エンジンがどう考えるのかを知らないと解けない問題だね」と所長。「今日はエンジンの頭の中をのぞいてみよう」

8-1. エンジンは前から試し、行き詰まったら引き返す (10分)

正規表現エンジンは、パターンを左から1かけらずつ文字列に当てはめていきます。合わなくてもすぐにはあきらめず、直前に下した選択を1つ取り消して別の道を試します。これをバックトラック（backtracking）と呼びます。

3限目で、量指定子は基本的に「できるだけたくさん食べる（欲張り）」と説明しました。HTML からタグを抜き出す例で、その結果を見てみましょう。

html = "<b>bold</b> and <i>it</i>"
re.findall(r"<.+>", html)   # ['<b>bold</b> and <i>it</i>']

タグ4つではなく、行全体が1つとして捕まりました。エンジンのしたことを追ってみると、こうなります。

1. < が先頭の < に合います。
2. .+ は欲張りなので、行末まですべて食べます。
3. 次にパターンの > を合わせたいのに、残りの文字がありません。失敗。
4. .+ が食べた文字を1つずつ返しながら再挑戦します。最後の > を返してもらった瞬間に成功します。

結果は「いちばん外側の < から、いちばん最後の > まで」。間違っているのはエンジンではなく、パターンのほうです。

8-2. 怠惰な量指定子：*? +? ?? {m,n}? (8分)

量指定子の後ろに ? を付けると、できるだけ少なく食べる怠惰な（lazy）量指定子になります。まずは最小限だけ食べ、後ろが合わないときだけ1文字ずつ追加で食べます。

re.findall(r"<.+?>", html)          # ['<b>', '</b>', '<i>', '</i>']
re.findall(r"a+?", "aaa")           # ['a', 'a', 'a']
re.findall(r"a??", "a")             # ['', 'a', '']
re.search(r"\d{2,4}?", "12345").group()   # '12'

怠惰な量指定子が変えるのは「どこで止まるか」です。だから、タグのように終わりの目印がはっきりしたものを短く捕まえたいときに便利です。

8-3. 同じ問題に、3つの答え (4分)

タグを抜き出す方法を並べてみます。

<[^>]+> は2限目の否定クラスで、「> 以外の文字」だけを食べます。引き返すことがほとんどないので、いちばん速く、意味もはっきりしています。所長いわく、「怠けるより、正確に」。

8-4. 挑戦状の答え：引き返す道が多すぎる (8分)

いよいよカードのパターン ^(a|aa)+$ を見てみます。このパターンは「a が1つ以上続く文字列全体」を探します。意味は ^a+$ と同じです。

bool(re.fullmatch(r"^(a|aa)+$", "aaaa"))   # True
bool(re.fullmatch(r"^a+$", "aaaa"))        # True

問題は、合わない文字列に出会ったときです。aaaa…ab のように末尾に b が付いていると、エンジンは a の並びを a と aa に分けるすべての方法を1つずつ試してから、ようやく失敗を認めます。分け方の数は、a が増えるほど爆発的に増えていきます。

事務所のパソコン（Python 3.14）で実際に計った時間です。

a が4つ増えるたびに、約7倍ずつ遅くなっています。同じ割合なら、40個では10秒を軽く超えます。このように重なり合う選択肢を持つ繰り返しが、バックトラックを爆発させる典型的な形です。(a+)+ のように繰り返しの中に繰り返しがあるものも同じ仲間です。

8-5. 返さない量指定子：*+ ++ ?+ {m,n}+ (6分)

Python 3.11 から、量指定子の後ろに + を付けると強欲な（possessive）量指定子になります。一度食べた文字は、後ろが失敗しても返しません。引き返す道そのものをなくしてしまうのです。

re.fullmatch(r"a*a", "aaa")    # <re.Match object; span=(0, 3), match='aaa'>
re.fullmatch(r"a*+a", "aaa")   # None

a*+a はどんな文字列にもマッチしません。a*+ が a を全部持っていって返さないので、後ろの a が合わせる文字が残らないからです。逆に、この性質のおかげでカードのパターンも直せます。

re.search(r"^(?:a|aa)++$", "a" * 28 + "b")   # None（すぐに終わる）

++ がグループの繰り返しを強欲にするので、失敗したら別の分け方を試さずに、すぐあきらめます。

8-6. まるごと返さないグループ：(?>...) (4分)

アトミックグループ（atomic group）(?>...) も 3.11 から使えます。グループの中が一度マッチすると、その結果をまるごと確定させ、中へは引き返しません。強欲な量指定子は、実はアトミックグループの省略形です。a++ は (?>a+) と同じです。

re.fullmatch(r"(?>a+)b", "aab")   # <re.Match object; span=(0, 3), match='aab'>
re.fullmatch(r"(?>a+)a", "aaa")   # None

事件解決 (10分)

所長と一緒に返事をまとめます。遅いパターンを直す方法は3つです。

1. 重ならないように書き直す。 同じ文字を何通りにも分けられないようにする。^(a|aa)+$ の代わりに ^a+$。
2. 引き返す道をなくす。 強欲な量指定子 ^(?:a|aa)++$ や、アトミックグループ ^(?>(?:a|aa)+)$。
3. 外側で防ぐ。 入力の長さを制限し、他人から送られたパターンは時間制限のある場所でだけ実行する。この分析室がパターンを別プロセスで動かし、0.3秒を超えたら止めているのが、まさにその仕組みだ。（サードパーティのパッケージ regex には timeout 引数がある。）

import time
text = "a" * 40 + "b"
start = time.perf_counter()
print(re.search(r"^a+$", text))             # None
print(time.perf_counter() - start < 0.01)   # True

新人探偵はカードの裏に ^a+$ と書いて、封筒に入れます。所長がうなずきます。「短くて、読めて、速い。いい返事だ」

練習問題

1. re.findall(r'".+"', 'say "hi" and "yo"') の結果を予想し、引用符で囲まれた部分を1つずつ捕まえるように、2つの方法（怠惰な量指定子、否定クラス）で直してみましょう。
2. (\d+)+$ がなぜ危険な形なのかを説明し、同じ意味の安全なパターンを書いてみましょう。
3. a{2,4}? と a{2,4}+ を "aaaaa" に findall で当てると、それぞれ何が出てくるでしょうか。分析室で確かめてみましょう。