防止RegEx在大型比赛中挂起

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

你应该阅读掌握正则表达式.问题是:

(?:[\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']

为了详细介绍(我参考的那本书非常擅长),*和+工作(在NFAs中就像python一样),就像一个循环.原始模式的内部循环将匹配一长串数字,但是当后续模式无法匹配时,它将一次"放弃"一个.然后外循环将重新运行剩余模式的内循环,当然它会立即再次抓取数字.每次内循环的一个实例放弃一个数字时,将召唤一个新副本再次抓取它.最终,一旦引擎经历了每种可能的方式来分割该数字串(指数的可能性),它将向前移动一个字符......然后再试一次.

另一方面,你的模式看起来有点疯狂;)