Node.JS Regex引擎在大输入时失败

Question

问题有点复杂,谷歌搜索并没有真正帮助.我将尽力只涉及它的相关方面.

我有一个大约以下格式的大型文档:

样本输入:

ABC is a word from one line of this document. It is followed by
some random line
PQR which happens to be another word.
This is just another line
I have to fix my regular expression.
Here GHI appears in the middle.
This may be yet another line.
VWX is a line
this is the last line 

我想根据以下内容删除文本部分:

• 从以下任何一个:
  • ABC
  • DEF
  • GHI
• 要么(保留这个词):
  • PQR
  • STU
  • VWX

组成"From"的单词可以出现在一行中(看GHI).但是为了移除,需要移除整条线.(需要删除包含GHI的整行,如下面的示例输出中所示)

样本输出:

PQR which happens to be another word.
This is just another line
I have to fix my regular expression.
VWX is a line
this is the last line 

上面的例子对我来说实际上似乎很容易,直到我针对非常大的输入文件运行它(49KB)

我尝试过的:

我目前使用的正则表达式是(不区分大小写和多行修饰符):

^.*\b(abc|def|ghi)\b(.|\s)*?\b(pqr|stu|vwx)\b

问题

上面的正则表达式可以很好地处理小文本文件.但是在大文件上失败/崩溃引擎.我试过它反对下面:

• V8(Node.js):挂起
• 犀牛:挂起
• Python:挂起
• Java :( StackoverflowError在这个问题的末尾发布了堆栈跟踪)
• IonMonkey(火狐):工作!

实际输入:

• 我的原始输入:http://ideone.com/W4sZmB

• 我的正则表达式(为清晰起见,分为多行):

  ^.*\\b(patient demographics|electronically signed|md|rn|mspt|crnp|rt)\\b
   (.|\\s)*?
   \\b(history of present illness|hpi|chief complaint|cc|reason for consult|patientis|inpatient is|inpatientpatient|pt is|pts are|start end frequency user)\\b
  

题:

• 我的正则表达是否正确？是否可以进一步优化以避免此问题？
• 如果它是正确的,为什么其他引擎无限挂起？堆栈跟踪的一部分如下:

堆栈跟踪:

Exception in thread "main" java.lang.StackOverflowError
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4218)
    at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
    at java.util.regex.Pattern$CharProperty.match(Pattern.java:3345)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
    at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
    at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)

^{PS:我在这个问题上添加了几个标签,因为我已经在这些环境中尝试了它并且实验失败了.}

Answer 1

问题是 (.|\s)* 因为任何空格字符都会匹配这两个选项，并且它将允许它进入两个选项。这使得它呈指数级增长。

您可以在 ruby​​ 中看到此正则表达式的问题

str = "b" + "a" * 200 + "cbab"

/b(a|a)*b/.match str

这需要很长时间，而基本相同的

/ba*b/.match str

匹配很快。

您可以通过使用 just.*或 if.不匹配换行符来解决此问题(.|\n)*