pac*_*cak -4 regex complexity-theory
您可能知道有两种不同的正则表达式实现:一种使用回溯(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:我将在大约一周内显示源代码 - 我仍然希望使用分析器运行一些测试并替换几个内部数据结构.
use*_*556 11
我相信你很困惑.所有正则表达式都可以用离散有限自动机(DFA)表示,并且(因此)可以在O(n)时间内求解.Perl正则表达式(PREG)(以及由许多语言提供的正则表达式库)匹配比正则表达式更大的语言,即:PREG中存在正则表达式.
如果你想更多地搜索常规语言.每个常规语言都可以用正则表达式表示(因此名称相似),每个正则表达式都代表一种常规语言.PREG可以代表不是常规语言的东西.
此外,没有人喜欢这样的人说"我能做到这一点,这真是太棒了,但我不会解释如何".仅凭这一点就足以让你不相信(忽略你误解了正则表达式是什么).