2

我们遇到以下正则表达式的问题：

(.*?)\|\*\|([0-9]+)\*\|\*(.*?)

它应该匹配以下内容：|*25 *|

我们正在使用 .Net Framework 4 RegEx 类，代码如下：

string expression = "(.*?)" + 
       Regex.Escape(Constants.FIELD_START_DELIMITER_BACK_END) + 
       "([0-9]+)" + 
       Regex.Escape(Constants.FIELD_END_DELIMITER_BACK_END) + 
       "(.*?)";
Regex r = new Regex(expression);
r.Matches(contentText)

40.000 个字符的文本花费的时间太长（例如 60 秒）。

但是对于 180.000 的文本，它的速度是可以接受的（3 秒或更短）

文本之间的唯一区别在于第一个文本（速度较慢的文本）全部包含在一行中，没有换行符。这可能是一个问题吗？那是影响性能吗？

谢谢

4

2 回答 2

5

@David Gorsline 的解决方案（来自评论）是正确的：

string expression =
    Regex.Escape(Constants.FIELD_START_DELIMITER_BACK_END) + 
    "([0-9]+)" + 
    Regex.Escape(Constants.FIELD_END_DELIMITER_BACK_END);

具体来说，它是(.*?)在一开始让你进入。它所做的是接管做正则表达式引擎应该做的事情——扫描正则表达式可以匹配的下一个位置——并且做起来效率要低得多。在每个位置，(.*?)有效地执行前瞻以确定正则表达式的下一部分是否可以匹配，只有当匹配失败时，它才会继续并消耗下一个字符。

但即使你使用了更高效的东西，比如[^|]*，你仍然会减慢它的速度。但是，不要使用该部分，正则表达式引擎可以扫描正则表达式的第一个常量部分，可能使用像 Boyer-Moore 或 Knuth-Morris-Pratt 这样的算法。所以不要担心你想要匹配的位周围有什么；只需告诉正则表达式引擎您要查找的内容并避开它。

另一方面，尾随 (.*?)几乎没有影响，因为它从来没有真正做任何事情。?转身不情愿，.*那么要让它继续前进并消耗下一个角色需要什么？只有在正则表达式中有一些东西迫使它这样做时，它才会这样做。例如，foo.*?bar消耗从下一个“foo”到下一个“bar”的所有内容，但在消耗完“foo”后foo.*?立即停止。将不情愿的量词作为正则表达式中的最后一件事是没有意义的。

于 2012-04-13T23:45:48.263 回答
2

您已经回答了您的问题：问题在于.无法匹配换行符（默认情况下不匹配），这导致许多失败的尝试 - 几乎每个位置都有一个 40000 字符串。
在长但单行的文件上，引擎可以在文件上一次通过匹配模式（假设存在成功的匹配 - 如果不存在，我怀疑它需要很长时间才能失败......）。
在包含许多行的较短文件上，引擎尝试从第一个字符开始匹配。它匹配.*?到第一行的末尾（这是一个惰性匹配，所以会发生更多事情，但让我们忽略它），然后失败。现在，它再次从第二个字符开始统计，不是第二行！即使在匹配数字之前，这也会导致 n² 复杂度。

一个简单的解决方案是.匹配换行符：

Regex r = new Regex(expression, RegexOptions.Singleline);

您还可以确保使用绝对开始和结束锚点从头到尾匹配，\A并且\z：

string expression = "\\A(.*?)" + 
   Regex.Escape(Constants.FIELD_START_DELIMITER_BACK_END) + 
   "([0-9]+)" + 
   Regex.Escape(Constants.FIELD_END_DELIMITER_BACK_END) + 
   "(.*?)\\z";

另一个注意事项：正如大卫在评论中建议的那样，\|\*\|([0-9]+)\*\|\*应该工作得很好。即使您需要“捕获”匹配前后的所有文本，您也可以使用匹配的位置轻松获取它。

于 2012-04-13T19:35:48.183 回答