正则表达式匹配耗时差异排查：re1与re2执行时长悬殊原因分析

这事儿核心原因是正则引擎的回溯爆炸（backtracking explosion），咱们来拆解分析：

先看你的测试场景 #

你的测试数据是一长串纯0字节：

data = b'000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'

re1为什么慢到离谱？ #

re1的模式是：

re1 = b'.*00.*00.*00.*00.*76.*62.*55.*75.*'

因为你的数据里根本没有76、62这些非0字符，正则引擎会陷入疯狂的回溯尝试：

1. 第一个.*是贪婪匹配，会先吃掉所有的0，然后尝试找后面的00——发现已经到字符串末尾了，于是回溯，把.*的长度减1，再找00，直到找到；
2. 接着第二个.*又贪婪吃掉剩下的所有0，再尝试找下一个00，找不到就继续回溯；
3. 这个过程要重复四次（因为有四个.*00段），每次都要尝试无数种.*和00的分割组合；
4. 等好不容易把四个.*00的组合都试完，发现后面的76根本不存在，于是又要回溯调整前面每一个.*的长度，再重新尝试所有可能的组合……

这种指数级增长的回溯次数，直接把耗时拉到了30秒。

re2为什么快得飞起？ #

再看re2的模式：

re2 = b'.*aa.*00.*00.*6f.*63.*20.*6d.*75.*'

它的第一个段是.*aa——而你的数据里连一个aa都没有。正则引擎只需要从头到尾扫一遍数据，发现找不到aa，立刻就知道整个模式不可能匹配，直接终止匹配流程，所以耗时只有1秒左右。

怎么优化这种问题？ #

如果你需要保留类似re1的匹配逻辑，又想避免回溯爆炸，可以：

• 把最不可能出现的字符放在模式最前面：比如把.*76移到re1的最开头，这样引擎会快速发现没有76，直接终止，不会做后面的无用回溯；
• 避免贪婪匹配的嵌套重复：如果可以，用更精确的匹配代替.*，比如如果你知道00之间的内容是特定长度，就不要用模糊的.*；
• 慎用非贪婪匹配：非贪婪匹配（.*?）有时候能减少回溯，但在这个场景下，因为后面的字符不存在，还是会有大量回溯，所以最有效的还是让引擎尽早判断匹配失败。

举个优化后的re1例子：

# 把最不可能出现的76放在最前面，引擎会快速判断匹配失败
re1_optimized = b'.*76.*00.*00.*00.*00.*62.*55.*75.*'

内容的提问来源于stack exchange，提问作者Yogev Shitrit