0

我有一些过程，它运行在一些包含大量奇怪数据的文件上。该过程需要找到一些字符串并将其替换为其他内容。这是功能：

 private static string ReplaceRegex(string inputText, string regex, string replacement)
        {
            return (replacement != null)?new Regex(regex, RegexOptions.IgnoreCase).Replace(inputText, replacement).Trim(): string.Empty;
        }

它在大多数情况下都能正常工作，但是一旦我将一个长度为 3491 个字符的 inputText 传递给这个函数，并且这个字符串作为一个正则表达式：

"\[HYPERLINK\]\s*(?:\<[\s\S]*?\>)*\s*([\s\S]*?)\s*(?:\<[\s\S]*?\>)*\s*\[\/HYPERLINK]\s*(?:\<NO1\>)?\s*(?:\<WC1?\>)?\s*\[URL\]\s*(?:\<NO1?\>)?\s*(?:\<WC1?\>)?\s*([\s\S]*?)\s*(?:\<NO1?\>)?\s*(?:\<WC1?\>)?\s*\[\/URL\](?:\<NO1?\>)?(?:\<WC1?\>)?"

过程卡住了。

我在等待系统会抛出 OutOfMemory 异常，但它没有，它只是卡住了。我等待它响应几个小时，但它没有响应。

有什么想法可以解决这个问题吗？

编辑：谢谢大家。

老实说，我在项目中继承了这段代码，现在试图弄清楚发生了什么。我不知道为什么有人这样做。

4

6 回答 6

4

你有所谓的“灾难性回溯”。

基本上，当您有一个可变长度表达式（*,+等）后跟一个“重叠”（即两个表达式可以匹配同一组字符）可变长度表达式时，您可能会陷入拉锯战两种表达方式。这通常仅在整个表达式失败并且 .NET regex enginge 尝试在重叠表达式之间移动输入文本时发生，因此在测试中经常会错过它。

您的表达式有许多可能导致此问题的子表达式，但这里有一个示例：

\s*([\s\S]*?)

第一部分 ,\s*可以匹配零个或多个空白字符。第二个，[\s\S]*?, 也可以匹配零个或多个空白字符（除了非空白字符）。如果您的输入在第一次尝试时失败并且有多个空白字符要匹配，这将导致灾难性的回溯。

我也在这里写了一些关于这个问题的文章：
如何识别邪恶的正则表达式？

于 2013-09-20T18:00:45.143 回答
3

问题几乎可以肯定是回溯。正则表达式是贪婪的。一般规则是采用“最左边最长”的匹配。像.*Foo.*Bar.*贪婪的东西：

  • 第一个.*将消耗整个源文本。
  • 然后，由于后面没有Foo，它将开始回溯，缩短匹配直到它有一个Foo。
  • 下一个.*将再次从源文本中的当前点到结尾的所有内容。
  • 又会失败，因为Bar没有找到。

  • 所以它再次回溯，直到Bar找到 a 。此时您应该注意，如果没有Bar找到，回溯会继续往后，寻找另一个Foo.

    您可以想象由带有大量回溯的复杂正则表达式创建的那种组合爆炸。

  • final.*将消耗从该点到字符串末尾的所有内容。

所以...

获取 Jeffrey Fried 的作品，掌握正则表达式

主正则表达式封面

它将极大地帮助您。

于 2013-09-20T17:49:40.053 回答
1

[\s\S]*?正在变成一个贪婪的怪物： 

 \[HYPERLINK\]

 ( [\s\S]*? )                 # This turns into a greedy monster

 \[\/HYPERLINK\]              # as soon as one of   <- this

 \s* 
 (?: \<NO1\> )?
 \s* 
 (?: \<WC1?\> )?
 \s* 

 \[URL\]                      # or  <- this


 ( [\s\S]*? )                      #  This turns into a greedy monster of a greedy monster


 \[\/URL\]                   # or   <- this   are missing

编辑：您可能可以通过以下方式解决此问题，但如果这太严格，您至少需要一些中间表达式锚来打破它。

 # \[HYPERLINK\]\s*(?:\<[^>]*\>)*\s*((?:(?!\[\/HYPERLINK\]|\<[^>]*\>)[\S\s])*)\s*(?:\<[^>]*\>)*\s*\[\/HYPERLINK\]\s*(?:\<NO1\>)?\s*(?:\<WC1?\>)?\s*\[URL\]\s*(?:\<NO1?\>)?\s*(?:\<WC1?\>)?\s*((?:(?!\[\/URL\]|\<[^>]*\>)[\S\s])*)\s*(?:\<NO1?\>)?\s*(?:\<WC1?\>)?\s*\[\/URL\](?:\<NO1?\>)?(?:\<WC1?\>)?

 \[ HYPERLINK \]

 \s* 
 (?: \< [^>]* \> )*
 \s* 
 (
      (?:
           (?! \[\/HYPERLINK \] | \< [^>]* \> )
           [\S\s] 
      )*
 )
 \s* 
 (?: \< [^>]* \> )*
 \s* 

 \[\/HYPERLINK\]

 \s* 
 (?: \<NO1\> )?
 \s* 
 (?: \<WC1?\> )?
 \s* 

 \[URL\]

 \s* 
 (?: \<NO1?\> )?
 \s* 
 (?: \<WC1?\> )?
 \s* 
 (
      (?:
           (?! \[\/URL\] | \< [^>]* \> )
           [\S\s] 
      )*
 )
 \s* 
 (?: \<NO1?\> )?
 \s* 
 (?: \<WC1?\> )?
 \s* 

 \[\/URL\]

 (?: \<NO1?\> )?
 (?: \<WC1?\> )?
于 2013-09-20T17:33:45.493 回答
0

这可能与您使用大量*'s 的事实有关。创建一个正则表达式非常容易，它可以通过消耗所有资源来削弱您的系统，尤其是在创建如此大的资源时。

就个人而言，我会尝试在其中添加一些限制（例如.{1,100}）。

于 2013-09-20T15:56:39.690 回答
0

我对您拥有的(?:\<[\s\S]?>)和类似的重复模式感兴趣。[\s\S]?匹配“一个空格或非空格字符”。我认为这在功能上等同于正则表达式.

您还有类似\s*([\s\S]*?)\s*“零个或多个空格，后跟零个或多个（空格或非空格），后跟零个或多个空格”之类的东西。这在技术上是合法的，但在实际意义上很奇怪。

即使“它有效”，我还是建议您以一种可维护的方式重写您的正则表达式，或者找到一种不使用正则表达式来解析字符串的方法。

于 2013-09-20T17:13:20.863 回答
0

当您知道那里会有数据时，请退出使用*（零个或多个）并通过使用（一个或多个）给解析器更好的处理提示。+仅*在or类型的情况下使用，您不希望它失败并且不允许包含任何内容。

于 2013-09-20T18:13:42.153 回答