这article说 Java 中的正则表达式匹配很慢,因为带有“反向引用”的正则表达式不能有效匹配。这篇文章解释了 高效 Thomson 基于 NFA 的匹配算法(发明于 1968 年),该算法适用于 没有“反向引用”的正则表达式。然而 Pattern
javadoc说 Java 正则表达式使用基于 NFA 的方法。
现在我想知道 Java 正则表达式匹配的效率如何以及它使用什么算法。
最佳答案
java.util.regex.Pattern
使用 Boyer–Moore 字符串搜索算法
/* Attempts to match a slice in the input using the Boyer-Moore string
* matching algorithm. The algorithm is based on the idea that the
* pattern can be shifted farther ahead in the search text if it is
* matched right to left.
*/
private void compile() {
----------------------
-----------------------
if (matchRoot instanceof Slice) {
root = BnM.optimize(matchRoot);
if (root == matchRoot) {
root = hasSupplementary ? new StartS(matchRoot) : new Start(matchRoot);
}
} else if (matchRoot instanceof Begin || matchRoot instanceof First) {
root = matchRoot;
} else {
root = hasSupplementary ? new StartS(matchRoot) : new Start(matchRoot);
}
}
关于java - Java中的正则表达式匹配算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19251384/