Node.JS正则expression式引擎在大input时失败

这个问题有点复杂，Google使用并没有什么帮助。 我会尽量只介绍它的相关方面。

我有一个大的文件大致如下格式：

示例input ：

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 

上面的例子对我来说似乎很容易，直到我运行它非常大的input文件（49KB）

我曾经尝试过 ：

我正在使用的正则expression式是（不区分大小写和多行修饰符）：

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

问题

上面的正则expression式在小文本文件上工作得非常好。 但在大文件上失败/崩溃引擎。 我已经尝试了以下：

• V8（Node.js）：挂起
• 犀牛：挂起
• Python：挂起
• Java： StackoverflowError （在这个问题结束时发布的栈跟踪）
• IonMonkey（Firefox）：工作！

实际input：

• 我的原始input： http ： //ideone.com/W4sZmB

• 我的正则expression式（为了清晰起见，分成多行）：

   ^.*\\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 

题：

• 我的正则expression是否正确？ 可以进一步优化以避免这个问题？
• 如果这是正确的，为什么其他引擎无限挂起？ 堆栈跟踪的一部分如下：

堆栈跟踪：

 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中看到这个正则expression式的问题

 str = "b" + "a" * 200 + "cbab" /b(a|a)*b/.match str 

这需要永远，而一个基本相同的

 /ba*b/.match str 

匹配很快。

你可以通过使用.*或if来解决这个问题. 与换行符不匹配(.|\n)*

Answer 2

我会试图尝试简化重新。 目前说实话不是很复杂，但是如何：

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

难道这不是仍然做你所追求的，但在线锚的开始和不必要的可选元素在中间？ 可能没有什么区别，但可能值得尝试。

Answer 3

我认为你的问题可能在于，当文件变得越来越长时，你可以匹配来自和来自块的对，大约是nxm / 2。这意味着你得到越来越多的结果，占用越来越多的源文件。 如果文件以ABC开始并以VWX结束，则其中一个匹配将是整个文件。

为了给正则expression式引擎less处理匹配，我​​的第一种方法是分别对(abc|def|ghi)和(pqr|stu|vwx) 。 在得到结果之后，您可以通过比赛中的每一个来尝试find第一个匹配来阻止。 一些伪代码来完成这个将是

 from = regex.match(file, '(abc|def|ghi)') to = regex.match(file, '(pqr|stu|vwx)') for each match in from: for index in to: if index > match: add index, match to results break for each result: parse backwards to the beginning of the line edit the file to remove the matching text 

虽然这会为您自己创造更多的工作，但这意味着正则expression式parsing器不必一次将整个n kB文件保存在内存中，并且可以更有效地parsing小块。