回溯者的挑战书：贪婪、懒惰与占有

早上，事务所的门缝里夹着一个黑色信封，里面是一张卡片。所长把卡片对着灯光看了看，放回桌上。“总算来打招呼了。不露脸，只留签名。”

^(a|aa)+$

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

卡片上的韩文写着：“这个模式能给出正确答案。可它为什么这么慢？用模式来回答。”右下角是那个熟悉的签名。

“得知道正则引擎是怎么思考的，才解得开这道题。”所长说，“今天我们去看看引擎的脑子里在想什么。”

8-1. 引擎从前往后试，走不通就退回去（10 分钟）

正则引擎从左边开始，把模式一块一块地往字符串上套。套不上时它不会马上放弃，而是撤销刚才做的一个选择，换一条路再试。这就叫回溯（backtracking）。

第 3 课说过，量词默认会“尽可能多吃”（贪婪）。我们用从 HTML 里取标签的例子来看看结果。

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

抓到的不是四个标签，而是整整一行。跟着引擎走一遍，过程是这样的。

1. < 对上了开头的 <。
2. .+ 是贪婪的，一口气吃到行尾。
3. 接下来要对上模式里的 >，可是已经没有字符了。失败。
4. .+ 把吃掉的字符一个一个吐出来，再重新尝试。吐回最后那个 > 的瞬间，成功。

结果就是“从最外面的 < 到最后一个 >”。错的不是引擎，而是模式。

8-2. 懒惰量词：*? +? ?? {m,n}?（8 分钟）

在量词后面加上 ?，就成了尽可能少吃的懒惰（lazy）量词。它先只吃最少的量，只有后面对不上时才多吃一个字符。

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. 同一个问题，三种答案（4 分钟）

把取标签的几种写法摆在一起看看。

<[^>]+> 用的是第 2 课的否定字符类，只吃“不是 > 的字符”。几乎没有需要回退的地方，所以最快，意思也最清楚。所长是这么说的：“与其偷懒，不如精确。”

8-4. 挑战书的答案：能退回去的路太多了（8 分钟）

现在来看卡片上的模式 ^(a|aa)+$。它寻找“由一个以上连续的 a 组成的整个字符串”，意思和 ^a+$ 一样。

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

问题出在遇到对不上的字符串时。像 aaaa…ab 这样末尾多了个 b，引擎要把这些 a 拆成 a 和 aa 的所有拆法挨个试一遍，才肯承认失败。而拆法的数量会随着 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 分钟）

和所长一起整理回信。修好慢模式的办法有三种。

1. 改写成不重叠的形式。 让同样的字符没法用多种方式拆分。用 ^a+$ 代替 ^(a|aa)+$。
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"') 的结果，再用两种方法（懒惰量词、否定字符类）改成一次只抓一对引号。
2. 说明 (\d+)+$ 为什么是危险的形状，并写出一个意思相同的安全模式。
3. 用 findall 在 "aaaaa" 上分别跑 a{2,4}? 和 a{2,4}+，各会得到什么？去分析室确认一下。