RE2 / J:Java中的线性时间正则表达式匹配
RE2是一个正则表达式引擎,其运行时间与输入大小成线性关系。 RE2 / J是RE2到纯Java的移植。
Java的标准正则表达式包java.util.regex和许多其他广泛使用的正则表达式包(例如PCRE,Perl和Python)使用回溯实现策略:当模式提供两个替代方案(例如a|b ,引擎将尝试匹配子模式a第一,如果该收益率不匹配,这将重置输入流,并尝试匹配b代替。
如果这些选择被深层嵌套,则此策略需要先对输入数据进行指数级传递,然后才能检测到输入是否匹配。 如果输入很大,则很容易构造一个运行时间将超过Universe寿命的模式。
1