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

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实现），但很多正则表达式实现并不能很好地处理非贪婪匹配，尤其是在查找操作失败的情况下。我不知道Java正则表达式实现是否属于这个类别，但没有理由诱惑命运。

其次，它没有意义。正则表达式搜索的语义是找到第一个可能的匹配，这与.*?的语义相同。要获取捕获(.*?)，只需要从前一个匹配结束（或字符串的开始）到当前匹配开始的子字符串。这是微不足道的，尤其是因为你已经在跟踪上一场比赛的结束了。

Answer 2

你是如何阅读文件的？如果您逐行读取文件BufferedReader#readLine()或Scanner#nextLine()，则只需将\G添加到正则表达式的开头。它首次应用正则表达式时的行为类似\A，将匹配锚定到字符串的开头。如果该比赛成功，则下一个find()将停留在前一场比赛结束的位置。如果没有找到匹配的匹配，它会放弃，并且不会在该字符串中查找更多匹配项。

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

至于为什么你的正则表达式太慢了，这是因为正则表达式引擎在放弃之前必须在每个非匹配行上进行多次匹配尝试 - 可能有数百次。如果认识到某条生产线上的第一次尝试失败，那么在该生产线上进一步的尝试就不会有什么好处。所以它会向前推进一个位置并再次尝试。它始终如一地为整条线路做好准备。

如果您只希望每行有一个匹配，那么我会说使用起始行锚点（在MULTILINE模式下为^）。