您可能知道有两种不同的正则表达式实现:一种使用回溯(pcre),另一种使用有限自动机(re2).
这两种算法都有其局限性:在特定情况下,pcre可以采用指数时间来查找匹配,而有限自动机不支持反向引用.
PCRE实现支持反向引用,在像匹配的表情非常低效的/a?a?a?a?aaaa/反对aaaa,更多的a的表达和输入有-的时间也就越长,并与他们的30+它会占用大量时间,如果.
具有有限自动机的版本可以很好地处理所有这些实现,并且输入具有O(N)复杂性,但不支持反向引用:
pcre时间对复杂的表达式 - http://i.stack.imgur.com/D4gkC.png NFA处理这些,但不支持反向引用 - http://i.stack.imgur.com/t2EwI.png
有关反向引用的一些信息支持:
RE2 - http://code.google.com/p/re2/
一个重要的例外是RE2 不再支持反向引用 和广义零宽度断言,因为它们无法有效实现.
汤普森NFA - http://swtch.com/~rsc/regexp/regexp1.html
如前所述,没有人知道如何有效地实现具有反向引用的正则表达式,尽管没有人能够证明它也是不可能的.(具体来说,问题是NP完全,这意味着如果有人确实找到了有效的实施方案,那对计算机科学家来说将是一个重大新闻,并且会赢得一百万美元的奖金.)
所以我创建了自己的版本,它既支持反向引用又具有O(N)复杂性.它用haskell编写,大约600行(其中约200个是空白的,约200个类型的声明,可以跳过)行长.它在大约10秒内通过/a?a?aa/反对aa(100个a)来咀嚼,据我所知它是唯一可以匹配的版本
/a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?(a?a?a?a?a?a?a?a?a?a?aaaaaaaaaa)aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\1/
反对
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
在理智(约10秒)的时间.它当然支持基本正则表达式规范中列出的所有其他功能,我在互联网上找到了它.
问题是:它真的是"计算机科学家的重大新闻",如果是这样,我该怎么办？
PS:我将在大约一周内显示源代码 - 我仍然希望使用分析器运行一些测试并替换几个内部数据结构.