使用正则表达式提取两个短语之间的所有单词

Question

我正在尝试使用以下正则表达式提取两个短语之间的所有单词：

b(?:itemW+(?:w+W+){0,2}?(?:1|one)W+(?:w+W+){0,3}?business)b(.*)b(?:itemW+(?:w+W+){0,2}?(?:3|three)W+(?:w+W+){0,3}?legalW+(?:w+W+){0,3}?proceedings)b

我正在运行此正则表达式的文档是 10-K 文件。文件太长，无法在此处发布(例如，请参阅下面的 regex101 url(，但基本上它们是这样的：

ITEM 1. BUSINESS
lots of words
ITEM 2. PROPERTIES
lots of words
ITEM 3. LEGAL PROCEEDINGS

我想提取ITEM 1和ITEM 3之间的所有单词。请注意，每个 10-K 文件的字幕可能略有不同，因此我允许每个单词之间使用几个单词。

我不断收到灾难性的回溯错误，我不知道为什么。例如，请参阅 https://regex101.com/r/zgTiyb/1。

我做错了什么？

Answer 1

灾难性回溯几乎有一个主要原因：

找到可能的匹配项，但无法完成。

您为正则表达式提供了太多可供尝试的位置。这达到了 PCRE 的回溯限制。一个快速的解决方法是删除正则表达式中唯一的点星号，以便用限制性量词替换它，即

.{0,200}

在此处观看现场演示

但更好的方法是重新构造正则表达式：

bitemb.*?b(?:1|one)b(*COMMIT)W+(?:w+W+){0,2}?businessbh*R+(?:(?!itemh+(?:3|three)b)[sS])*+itemh+(?:3|three)bW+(?:w+W+){0,3}?legalW+(?:w+W+){0,3}?proceedingsb

在此处观看现场演示

您自己的正则表达式需要在给定的输入字符串上执行 ~45K 步数才能找到这两个匹配项。相比之下，这个修改后的正则表达式需要 ~8K 个步骤来完成任务。这是一个巨大的进步。

后者不需要s标志(也不应该启用(。我使用回溯动词(*COMMIT)如果找到可能的匹配项但可能无法完成，则会导致早期失败。

@Sebastian Proske 的解决方案匹配三个子字符串，但我认为第三个匹配不是预期的匹配。这巨大的第三场比赛是你的正则表达式中断的唯一原因。

请阅读此答案以更好地了解此问题。

Answer 2

这并不是真正的灾难性回溯，只是大量的文本和正则表达式 101 中相对较低的回溯限制。在这种情况下，.*的使用不是最佳的，因为它将在到达文本文件的整个其余部分后匹配，然后逐个字符回溯以匹配其后面的部分 - 这意味着要处理大量字符。

似乎你也可以在那个地方坚持w+W+，并使用懒惰匹配而不是贪婪来获得结果，比如

b(?:itemW+(?:w+W+){0,2}?(?:1|one)W+(?:w+W+){0,3}?business)bW+(?:w+W+)*?b(?:itemW+(?:w+W+){0,2}?(?:3|three)W+(?:w+W+){0,3}?legalW+(?:w+W+){0,3}?proceedings)b

请注意，pcre 引擎优化(?:w+W+)以(?>w++W++)因此通过无单词块而不是单个字符来工作。