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:我为这个问题添加了几个标签,因为我已经在这些环境中尝试过了,实验失败了。

       

网上收集的解决方案 "Node.JS正则expression式引擎在大input时失败"

问题是(。| \ s)*,因为任何空格字符都会匹配,并且会允许它同时停止这两个选项。 这使得它成倍增长。

你可以在ruby中看到这个正则expression式的问题

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

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

 /ba*b/.match str 

匹配很快。

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

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

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

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

我认为你的问题可能在于,当文件变得越来越长时,你可以匹配来自和来自块的对,大约是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小块。