python:如何中断正则表达式匹配

Question

我迭代了大量下载的文本文件中的行,并在每一行上进行正则表达式匹配.通常,匹配不到一秒钟.但是,有时匹配需要几分钟,有时匹配根本没有完成,代码只是挂起(等了一个小时几次,然后就放弃了).因此,我需要引入某种超时并以某种方式告诉正则表达式匹配代码在10秒左右后停止.我可以忍受这样一个事实,即我将丢失正则表达式应该返回的数据.

我尝试了以下(当然,在一个代码示例中显示了2个不同的,基于线程的解决方案):

def timeout_handler():
    print 'timeout_handler called'

if __name__ == '__main__':
    timer_thread = Timer(8.0, timeout_handler)
    parse_thread = Thread(target=parse_data_files, args=(my_args))
    timer_thread.start()
    parse_thread.start()
    parse_thread.join(12.0)
    print 'do we ever get here ?'

但我既没有得到输出中timeout_handler called的do we ever get here ?行也没有,代码只是被卡住了parse_data_files.

更糟糕的是,我甚至无法停止该程序CTRL-C,而是需要查找python进程号并终止该进程.一些研究表明Python人员知道正在运行的正则表达式C代码:http://bugs.python.org/issue846388

我确实使用信号取得了一些成功:

signal(SIGALRM, timeout_handler)
alarm(8)
data_sets = parse_data_files(config(), data_provider)
alarm(0)

这让我得到timeout_handler called了输出中的一行 - 我仍然可以停止使用我的脚本CTRL-C.如果我现在修改timeout_handler,如下所示:

class TimeoutException(Exception): 
    pass 

def timeout_handler(signum, frame):
    raise TimeoutException()

并且将实际调用包含re.match(...)在try... except TimeoutException子句中,正则表达式匹配实际上会被中断.不幸的是,这只适用于我用来试用东西的简单的单线程沙箱脚本.这个解决方案有一些问题:

• 信号只触发一次,如果有多条有问题的线,我就会卡在第二条线上
• 计时器在那里开始计数,而不是在实际解析开始时
• 由于GIL,我必须在主线程中进行所有信号设置,并且信号仅在主线程中接收; 这与多个文件同时在不同的线程中被解析的事实发生冲突 - 也只引发了一个全局超时异常,我不知道如何知道我需要对哪个线程作出反应
• 我已经多次读过线程和信号不能很好地混合

我也考虑过在一个单独的过程中进行正则表达式匹配,但在我进入之前,我想我最好先检查一下是否有人之前遇到过这个问题并且可以给我一些关于如何解决它的提示.

更新

正则表达式看起来像这样(好吧,其中一个,无论如何,问题也出现在其他正则表达式中;这是最简单的一个):

'^(\d{5}), .+?, (\d{8}), (\d{4}), .+?, .+?,' + 37 * ' (.*?),' + ' (.*?)$'

样本数据:

95756, "KURN ", 20110311, 2130, -34.00, 151.21, 260, 06.0, -9999.0, -9999.0, -9999.0, -9999.0, -9999.0, -9999, -9999, 07.0, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -

如上所述,正则表达式通常表现良好 - 我可以在不到一分钟的时间内解析数百个文件,数百行.但是,当文件完成时 - 代码似乎挂起了包含不完整行的文件,例如

`95142, "YMGD ", 20110311, 1700, -12.06, 134.23, 310, 05.0, 25.8, 23.7, 1004.7, 20.6, 0.0, -9999, -9999, 07.0, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999, -9999

我也得到了正则表达式似乎立即返回并报告不匹配的情况.

更新2

我只是快速阅读了灾难性的文章,但据我所知,到目前为止,这不是原因 - 我没有嵌套任何重复操作符.

我在Mac OSX上,所以我不能使用RegexBuddy来分析我的正则表达式.我尝试过RegExhibit(它显然在内部使用了Perl RegEx引擎) - 而且它也跑掉了.

Answer 1

你正在遇到灾难性的回溯; 不是因为嵌套量词,而是因为你的量化字符也可以匹配分隔符,并且因为它们中有很多,所以在某些情况下你会得到指数时间.

除了它看起来更像是CSV解析器的工作之外,请尝试以下操作:

r'^(\d{5}), [^,]+, (\d{8}), (\d{4}), [^,]+, [^,]+,' + 37 * r' ([^,]+),' + r' ([^,]+)$'

通过明确禁止逗号匹配分隔符,您将极大地加速正则表达式.

例如,如果逗号可能出现在引用的字符串中,那么只需交换[^,]+(在您期望的地方)

(?:"[^"]*"|[^,]+)

为了显示:

在第一个示例中使用正则表达式,RegexBuddy在正则表达式引擎的793步之后报告成功匹配.对于第二个(不完整的行)示例,它在正则表达式引擎的1.000.000步之后报告匹配失败(这是RegexBuddy放弃的地方; Python将继续搅拌).

使用我的正则表达式,成功匹配发生在173步骤中,失败发生在174.