防止正则表达式在大匹配时挂起

Question

这是一个很不错的用来匹配日期的正则表达式……不过我在尝试某个网页时，它一直卡在那里，没反应。我想试试这个网页（http://pleac.sourceforge.net/pleac_python/datesandtimes.html），因为上面有很多日期，我想把它们都抓取下来。我不明白为什么在这个网页上会卡住，而在其他网页上却没问题……为什么我的正则表达式会卡住？或者我该怎么改进它，让它更好、更高效呢？

Python代码：

monthnames = "(?:Jan\w*|Feb\w*|Mar\w*|Apr\w*|May|Jun\w?|Jul\w?|Aug\w*|Sep\w*|Oct\w*|Nov(?:ember)?|Dec\w*)"

pattern1 = re.compile(r"(\d{1,4}[\/\\\-]+\d{1,2}[\/\\\-]+\d{2,4})")

pattern4 = re.compile(r"(?:[\d]*[\,\.\ \-]+)*%s(?:[\,\.\ \-]+[\d]+[stndrh]*)+[:\d]*[\ ]?(PM)?(AM)?([\ \-\+\d]{4,7}|[UTCESTGMT\ ]{2,4})*"%monthnames, re.I)

patterns = [pattern4, pattern1]

for pattern in patterns:
    print re.findall(pattern, s)

顺便说一下……当我说我在这个网站上尝试时，其实我是对网页的源代码进行尝试。

Answer 1

Python的正则表达式评估器可能会花费很长时间。很不幸的是，它在最坏的情况下运行时间是指数级的。

我猜你的“s”包含了整个页面的内容。如果是这样的话，这可能会导致正则表达式评估器在处理时出现很长的回溯。也许你应该把页面分成更小的部分，然后分别用正则表达式处理它们。你可以使用像beautifulsoup这样的HTML解析器，逐个处理每个文本节点上的正则表达式。这样可能会减少运行时间。

Answer 2

这个正则表达式写得方式会导致很多回溯。除了建议你在较小的文本块上运行它之外，你还可以使用一个更简单（因此也更快）的正则表达式，来过滤掉那些无法匹配的文本。

Answer 3

你应该看看这本书：《正则表达式精通》。问题是：

(?:[\d]*[\,\.\ \-]+)*

这个过程需要的时间是指数级的。你可以试试：

(?:[\d,. \-]*[,. \-])?

这个方法应该能匹配到相同的内容，但所需时间是线性的。经过检查你的例子，确实能加快速度。

你似乎在某个地方不小心引入了捕获组，比如把 (AM) 改成 (?:AM) 就能解决这个问题。这样我们就能从你上面的例子中得到以下输出：

[' Aug  6 20:43:20 2003', ' Mar 14 06:02:55 1973', ' March 14 06:02:55 AM 1973', ' Jun 16 20:18:03 1981']
['2003-08-06', '2003-08-07', '2003-07-23', '1973-01-18', '3/14/1973', '16/6/1981', '16/6/1981', '16/6/1981', '16/6/1981', '08/08/2003']

具体来说（我提到的那本书对此讲得很好），* 和 + 在像 Python 的 re 这样的非确定性有限自动机中，工作方式有点像循环。原始模式的内部循环会匹配一长串数字，但当后面的模式匹配失败时，它会“一个一个地放弃”这些数字。外部循环会重新运行内部循环在剩下的模式上，当然它会立刻再次抓住这些数字。每当内部循环放弃一个数字时，就会召唤一个新的副本来再次抓住它。最终，当引擎尝试了所有可能的方式来分割那串数字（可能性是指数级的）后，它会把起始点向前移动一个字符……然后再试一次。

另外，你的模式看起来有点疯狂；)