为自定义键值对优化正则表达式

Question

我正试图从一个大文件中提取一些键值对及其前面的文本，但使用的正则表达式运行速度非常慢，因此需要优化。

输入由具有1或2个键值对的相当短的字符串组成，如

one two three/1234==five/5678 some other text

或

one two three/1234==five/5678 some other text four/910==five/1112 more text

使用的（显然是次优的）正则表达式是

(.*?)s*([^ /]+)s*/s*([d]+)s*==s*([^ /]+)s*/s*([d]+)s*

（空格可能出现在字符串中的许多区域中，因此会出现重复的s*元素。）

测试上述内容的示例代码：

  public static void main(String[] args) {
    String text = "one two three/1234==five/5678 some other text";
    text = "one two three/1234==five/5678 some other text four/910==five/1112 more text";
    String regex = "(.*?)\s*([^ /]+)\s*/\s*([\d]+)\s*==\s*([^ /]+)\s*/\s*([\d]+)\s*";
    Matcher matcher = Pattern.compile(regex).matcher(text);
    int end = 0;
    System.out.println("--------------------------------------------------");
    while (matcher.find()) {
      System.out.println(""" + matcher.group(1) + """);
      System.out.println(matcher.group(2) + " == " + matcher.group(3));
      System.out.println(matcher.group(4) + " == " + matcher.group(5));
      end = matcher.end();
      System.out.println("--------------------------------------------------");
    }
    System.out.println(text.substring(end).trim());
  }

输出是键值对，加上前面的文本（所有提取的字段都是必需的）。例如，对于较长的字符串，输出为：

--------------------------------------------------
"one two"
three == 1234
five == 5678
--------------------------------------------------
"some other text"
four == 910
five == 1112
--------------------------------------------------
more text

换句话说，matcher.find()方法运行1或2轮，这取决于字符串是短形式还是长形式（分别为1或2个键值对）。

问题是提取速度低，有时，根据输入字符串的变化，find()方法需要大量时间才能完成。

对于正则表达式，有没有更好的形式可以显著加快处理速度？

Answer 1

将(.*?)放在正则表达式的开头从来都不是一个好主意。

首先，它可能很慢。尽管理论上可以有效地处理非贪婪匹配（例如，参见Russ-Cox的re2实现），但许多regex实现并不能很好地处理非贪心匹配，尤其是在find操作将失败的情况下。我不知道Java regex实现是否属于这一类，但没有理由冒险。

其次，这毫无意义。正则表达式搜索的语义是，将找到第一个可能的匹配，这与.*?的语义相同。要获得捕获(.*?)，只需要从上一个匹配的末尾（或字符串的开头）到当前匹配的开头的子字符串。这很琐碎，尤其是因为你已经在追踪上一场比赛的结束。

Answer 2

您是如何读取文件的？如果使用BufferedReader#readLine()或Scanner#nextLine()逐行读取文件，则只需将G添加到正则表达式的开头即可。第一次应用正则表达式时，它的作用类似于A，将匹配项锚定在字符串的开头。如果该匹配成功，则下一个find()将被锚定到上一个匹配结束的位置。如果它没有找到从开始的匹配，它就会放弃，不再在该字符串中寻找任何匹配。

编辑：我假设要匹配的每个序列，无论是一个键/值对还是两个，都在自己的行上。如果你一次读一行文件，你可以在每一行上运行问题中的代码。

至于为什么您的正则表达式如此缓慢，这是因为正则表达式引擎必须在每个不匹配的行上进行多次匹配尝试，可能有数百次，然后才能放弃。意识到如果在给定线路上的第一次尝试失败，那么在该线路上的进一步尝试就不会有任何好处，这还不够聪明。所以它向前冲了一个位置，然后再试一次。它一直在这样做。

如果你只期望每行有一个匹配，我会说使用行首锚（MULTILINE模式中的^）。