Java 正则表达式挂在一个长字符串上

Question

我正在尝试编写一个 REGEX 来验证一个字符串。它应该符合要求，即它应该只有大写和小写英文字母（a 到 z，A 到 Z）（ASCII：65 到 90、97 到 122）AND/OR 数字 0 到 9（ASCII： 48 到 57) AND 字符 - _ ~ (ASCII: 45, 95, 126)。前提是它们不是第一个或最后一个字符。它也可以有字符。（点、句点、句号）(ASCII: 46) 前提是它不是第一个或最后一个字符，并且它没有连续出现两次或更多次。我试过使用以下

Pattern.compile("^[^\W_*]+((\.?[\w\~-]+)*\.?[^\W_*])*$");

它适用于较小的字符串，但它不适用于长字符串，因为我在 cpu 中遇到线程挂起问题和巨大的尖峰。请帮忙。

无效字符串的测试用例：

"aB78."
"aB78..ab"
"aB78,1"
"aB78 abc"
".Abc12"

有效字符串的测试用例：

"abc-def"
"a1b2c~3"
"012_345"

Answer 1

您的正则表达式受到 catastrophic backtracking 的影响，这导致 O(2ⁿ)（即指数）求解时间。

虽然在 link 之后会提供更详尽的解释，但简而言之，问题是当输入与不匹配时，引擎回溯第一个 * term 去尝试term的数量的不同组合，但是因为所有组或多或少都匹配相同的东西，所以分组方式的组合数量随着回溯的长度呈指数增长——在这种情况下不匹配的输入是整个输入。

解决方案是重写正则表达式，这样它就不会发生灾难性的回溯：

不要使用群组群组
使用所有格量词，例如 .*+（从不回溯）
在不匹配时提前失败（例如，使用锚定的负面展望）
使用 {n,m} 样式量词限制术语出现的次数

或以其他方式缓解问题

Answer 2

正如@MarounMaroun 已经评论过的那样，您并没有真正的模式。按照以下方法遍历字符串可能会更好：

public static boolean validate(String string) {
    char chars[] = string.toCharArray();

    if (!isSpecial(chars[0]) && !isLetterOrDigit(chars[0]))
        return false;
    if (!isSpecial(chars[chars.length - 1])
            && !isLetterOrDigit(chars[chars.length - 1]))
        return false;
    for (int i = 1; i < chars.length - 1; ++i)
        if (!isPunctiation(chars[i]) && !isLetterOrDigit(chars[i])
                && !isSpecial(chars[i]))
            return false;
    return true;
}

public static boolean isPunctiation(char c) {
    return c == '.' || c == ',';
}

public static boolean isSpecial(char c) {
    return c == '-' || c == '_' || c == '~';
}

public static boolean isLetterOrDigit(char c) {
    return (Character.isDigit(c) || (Character.isLetter(c) && (Character
            .getType(c) == Character.UPPERCASE_LETTER || Character
            .getType(c) == Character.LOWERCASE_LETTER)));
}

测试代码：

public static void main(String[] args) {
    System.out.println(validate("aB78."));
    System.out.println(validate("aB78..ab "));
    System.out.println(validate("abcdef"));
    System.out.println(validate("aB78,1"));
    System.out.println(validate("aB78 abc"));
}

输出：

false
false
true
true
false

Answer 3

解决方案应该尝试找到否定而不是尝试匹配整个字符串的模式。

Pattern bad = Pattern.compile( "[^-\W.~]|\.\.|^\.|\.$" );
for( String str: new String[]{ "aB78.", "aB78..ab", "abcdef",
        "aB78,1", "aB78 abc" } ){
    Matcher mat = bad.matcher( str );
    System.out.println( mat.find() );
}

（值得注意的是，初始语句 "string...should have only" 如何引导程序员尝试通过在整个长度上解析或匹配有效字符而不是更简单的否定搜索来创建肯定断言。）

Answer 4

问题

这是由于灾难性的回溯。让我通过将正则表达式简化为与原始正则表达式的子集匹配的正则表达式来展示它发生的位置：

^[^\W_*]+((\.?[\w\~-]+)*\.?[^\W_*])*$

因为[^\W_*]和[\w\~-]可以匹配[a-z]，所以我们将它们替换为[a-z]:

^[a-z]+((\.?[a-z]+)*\.?[a-z])*$

由于 \.? 是可选的，让我们删除它们：

^[a-z]+(([a-z]+)*[a-z])*$

你可以看到([a-z]+)*，这是导致灾难性回溯的正则表达式的经典示例(A*)*，以及最外层重复(([a-z]+)*[a-z])*可以扩展到[=27=的事实] 进一步加剧了这个问题（想象一下拆分输入字符串以匹配您的正则表达式可以具有的所有扩展的排列数）。而且这不是在前面提到 [a-z]+ ，这是雪上加霜，因为它的形式是 A*A*.

解决方案

您可以使用此正则表达式根据您的条件验证字符串：

^(?=[a-zA-Z0-9])[a-zA-Z0-9_~-]++(\.[a-zA-Z0-9_~-]++)*+(?<=[a-zA-Z0-9])$

作为 Java 字符串文字：

"^(?=[a-zA-Z0-9])[a-zA-Z0-9_~-]++(\.[a-zA-Z0-9_~-]++)*+(?<=[a-zA-Z0-9])$"

正则表达式分解：

^                                      # Assert beginning of the string
(?=[a-zA-Z0-9])                        # Must start with alphanumeric, no special
[a-zA-Z0-9_~-]++(\.[a-zA-Z0-9_~-]++)*+
(?<=[a-zA-Z0-9])                       # Must end with alphanumeric, no special
$                                      # Assert end of the string

由于.不能连续出现，也不能作为字符串的开始或结束，我们可以认为它是[a-zA-Z0-9_~-]+字符串之间的分隔符。所以我们可以这样写：

[a-zA-Z0-9_~-]++(\.[a-zA-Z0-9_~-]++)*+

所有量词都具有所有格，以减少 Oracle 实现中的堆栈使用并加快匹配速度。请注意，不宜在任何地方使用它们。由于我的正则表达式的编写方式，即使没有所有格量词，也只有一种方法可以匹配特定的字符串。

Shorthand

因为这是 Java 并且在默认模式下，您可以将 a-zA-Z0-9_ 缩短为 \w 并将 [a-zA-Z0-9] 缩短为 [^\W_] （尽管第二个是其他程序员有点难以阅读）：

^(?=[^\W_])[\w~-]++(\.[\w~-]++)*+(?<=[^\W_])$

作为 Java 字符串文字：

"^(?=[^\W_])[\w~-]++(\.[\w~-]++)*+(?<=[^\W_])$"

如果将正则表达式与 String.matches() 一起使用，则可以删除锚点 ^ 和 $。

Java 正则表达式挂在一个长字符串上

Java Regex hung on a long string

java

regex

string

问题

解决方案

Shorthand