防止RegEx挂在大火柴上

Question

这是一个很好的日期正则表达式。。。但是它无限期地挂在我尝试过的这一页上。。。我想试试这个页面（http://pleac.sourceforge.net/pleac_python/datesandtimes.html），因为它确实有很多日期，我想把它们都抓到。我不明白为什么它挂在其他页面上。。。为什么我的regexp挂起和/或我如何清理它以使它更好/更有效率？在

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

正则表达式的编写方式将导致大量的回溯。除了在较小的文本块上运行它的技巧之外，您还可以使用一个更简单（因而更快）的regex来过滤不匹配的文本。在

Answer 2

Python正则表达式求值器可能需要很长时间。不幸的是，它在最坏的情况下是指数时间。在

我想你的“s”包含了整个页面的副本。如果是这样，这可能会导致正则表达式计算器中出现很长的回溯。也许您应该将页面分成更小的块，然后通过正则表达式单独运行它们。您可以使用类似beauthoulsoup这样的HTML解析器，在每个文本节点上单独运行正则表达式。这可能会减少运行时间。在

Answer 3

你应该读Mastering Regular Expressions。问题是：

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

这需要指数时间。尝试使用：

^{pr2}$

它应该匹配相同的东西，但需要线性时间。检查了你的例子，这确实加快了速度。在

您似乎还意外地将捕获组引入到您的模式中，例如将（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']

为了深入了解细节（我所参考的这本书非常擅长），*和+的工作方式（在NFAs中，比如python的re）就像一个循环。原始模式的内部循环将匹配一长串数字，但当后续模式无法匹配时，它将一次“放弃”一个数字。然后外循环将在剩余的模式上重新运行内部循环，当然它会立即再次获取数字。每次内循环的一个实例放弃一个数字时，将调用一个新的副本来再次获取它。最终，一旦引擎完成了分割数字串的所有可能的方法（可能性的指数级），它将把起始点向前移动一个字符…然后再试一次。在

另一方面，你的模式看起来有点疯狂；）