6

我正在解析形式的（物种）名称：

Parus Ater
H. sapiens
T. rex
Tyr. rex

通常有两个术语（二项式），但有时有 3 个或更多。

Troglodytes troglodytes troglodytes 
E. rubecula sensu stricto

我写

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s*[a-z]+)*

大部分时间都有效，但偶尔会进入无限循环。花了一些时间才发现它在正则表达式匹配中，然后我意识到这是一个错字，我应该写

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s+[a-z]+)*

正确执行。

我的问题是：

  • 为什么会发生这个循环？
  • 有没有办法在运行程序之前检查类似的正则表达式错误？否则可能很难在 prgram 分发之前捕获它们并导致问题。

[注意：我不需要更通用的物种表达式——物种名称有一个正式的 100 多行正则表达式规范——这只是一个初始过滤器]。

注意：出现问题是因为尽管大多数名称被精确地提取为 2 或偶尔 3/4 项（因为它们是斜体），但仍有一些误报（如"Homo sapiens lives in big cities like London"）并且匹配在“L”处失败。]

注意：在调试时，我发现正则表达式经常完成但速度很慢（例如在较短的目标字符串上）。我通过一个病态的案例发现了这个错误，这是很有价值的。我学到了重要的一课！

4

2 回答 2

7

要解决您问题的第一部分，您应该阅读catastrophic backtracking。本质上，正在发生的事情是有太多方法可以将您的正则表达式与您的字符串匹配，并且解析器会不断地回溯以尝试使其工作。

在您的情况下，它可能是嵌套的重复： (\s*[a-z]+)*这可能会导致一些非常非常奇怪的循环。正如 Qtax 巧妙地指出的那样，如果没有更多信息，就很难判断。

不幸的是，您的问题的第二部分无法回答。这基本上是停机问题。由于正则表达式本质上是一个有限状态机，其输入是一个字符串，因此您无法创建一个通用解决方案来预测哪些正则表达式将灾难性地回溯，而哪些不会。

至于让你的正则表达式运行得更快的一些技巧？那是一大罐虫子。我花了很多时间自己研究正则表达式，并花一些时间优化它们，这就是我发现的通常有帮助的内容：

  1. 如果您的语言支持，请在循环之外编译您的正则表达式。
  2. 只要有可能，当您知道它们有用时添加锚点。特别是^对于字符串的开头。另请参阅： 字边界
  3. 避免像瘟疫一样的嵌套重复。如果您必须拥有它（您将拥有它），请尽力向引擎提供提示，以缩短任何意外的回溯。
  4. 利用风味结构来加快速度。我偏爱非捕获组和所有格量词。它们不会出现在每种口味中，但是当它们出现时，您应该使用它们。还可以查看原子组
  5. 我总是认为这是真的：你的正则表达式越长，你就越难让它变得高效。 正则表达式是一个伟大而强大的工具，它们就像一个超级聪明的锤子。 不要陷入把一切都看成钉子的陷阱。有时，您正在寻找的字符串函数就在您的眼皮底下。

希望这对您有所帮助。祝你好运。

于 2013-04-10T08:04:28.270 回答
2

对于第一个正则表达式：

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s*[a-z]+)*

(\s*[a-z]+)*正如评论中指出的那样，发生灾难性的回溯。但是，仅当您使用 验证字符串时它才成立，因为这是遇到无效字符导致引擎尝试回溯而不是返回匹配（循环）String.matches()的唯一情况。Matcher

让我们匹配一个无效的字符串(\s*[a-z]+)*：

inputstringinputstring;

(Repetition 1)
\s*=(empty)
[a-z]+=inputstringinputstring
FAILED

Backtrack [a-z]+=inputstringinputstrin
(Repetition 2)
\s*=(empty)
[a-z]+=g
FAILED

(End repetition 2 since all choices are exhausted)
Backtrack [a-z]+=inputstringinputstri
(Repetition 2)
\s*=(empty)
[a-z]+=ng
FAILED

Backtrack [a-z]+=n
(Repetition 3)
\s*(empty)
[a-z]+=g
FAILED

(End repetition 3 since all choices are exhausted)
(End repetition 2 since all choices are exhausted)
Backtrack [a-z]+=inputstringinputstr

至此，您应该已经注意到了问题所在。让我们定义T(n)为检查长度为 n 的字符串与模式不匹配的工作量。从回溯的方法，我们知道T(n) = Sum [i = 0..(n-1)] T(i)。由此，我们可以推导出T(n + 1) = 2T(n)，这意味着回溯过程的时间复杂度是指数级的！

更改*为+ 完全避免了该问题，因为重复实例只能从空格字符和英文字母字符之间的边界开始。相反，第一个正则表达式允许重复实例在任意 2 个字母字符之间开始。

为了证明这一点，(\s+[a-z]+\s*)*当无效的输入字符串包含许多用多个连续空格分隔的单词时，会给你回溯地狱，因为它允许重复实例在多个位置开始。这遵循以下公式b^d，其中b是最大连续空格数（减 1），d是空格序列数。它没有您拥有的第一个正则表达式那么严重（每次重复至少需要一个英文字母和一个空格字符，而不是在您的第一个正则表达式中每次重复一个英文字母），但这仍然是一个问题。

于 2013-04-10T08:54:41.917 回答