Java中的正则表达式匹配算法

Question

该文章说,在Java的正则表达式匹配是缓慢的,因为与"反向引用"正则表达式不能有效地匹配.这篇文章解释了有效的 Thomson基于NFA的匹配算法(发明于1968年),该算法适用于没有 "反向引用"的正则表达式.然而,Pattern javadoc说Java regexp使用基于NFA的方法.

现在我想知道Java regexp匹配的效率如何以及它使用的算法.

Answer 1

java.util.regex.Pattern使用 Boyer\xe2\x80\x93Moore 字符串搜索算法

\n\n

/* Attempts to match a slice in the input using the Boyer-Moore string\n * matching algorithm. The algorithm is based on the idea that the\n * pattern can be shifted farther ahead in the search text if it is\n * matched right to left.\n */\n\nprivate void compile() {\n    ----------------------\n    -----------------------\n\n   if (matchRoot instanceof Slice) {\n        root = BnM.optimize(matchRoot);\n        if (root == matchRoot) {\n            root = hasSupplementary ? new StartS(matchRoot) : new Start(matchRoot);\n        }\n    } else if (matchRoot instanceof Begin || matchRoot instanceof First) {\n        root = matchRoot;\n    } else {\n        root = hasSupplementary ? new StartS(matchRoot) : new Start(matchRoot);\n    }\n}\n

\n