正则表达式的简化？

[ispinfx]

有工具可以把正则简化（如下面的r2简单成r1）的吗？或者re.compile会简化正则表达式（结果看起来不会）吗？

# -*- coding: utf-8 -*-

import itertools
import re

string = "".join(map(str, range(1000000)))

r1 = r"[13579]{3}"
r2 = rf'{"|".join(map("".join, itertools.product("13579", repeat=3)))}'

r1 = re.compile(r1)
r2 = re.compile(r2)

match1 = re.findall(r1, string)
match2 = re.findall(r2, string)

assert sorted(match1) == sorted(match2)

结果：

In [78]: %timeit re.findall(r1, string)
167 ms ± 520 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [79]: %timeit re.findall(r2, string)
1.08 s ± 2.69 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

[f6x]

这个 r2 写的真牛

[ispinfx]

@f6x 只是一个例子…

[abersheeran]

mark……如果真的有，给我也说一声。

[geelaw]

很可惜正则表达式最小化问题是 PSPACE-complete，所以不应该期待高效算法。

另外，最小化 NFA 也是 PSPACE-complete，而最小化 DFA 则是多项式时间可解的。然而从正则表达式算出最小 DFA 的意义也不是很大，除非是做编译器的 lexer——从正则表达式到 DFA，规模可以以指数级增长，只有精心设计的正则语言才适合用 DFA 表示。

[Lemeng]

有，就太好了