12

这个问题有点复杂，谷歌搜索并没有真正帮助。我会尽量只介绍它的相关方面。

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

样本输入：

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

我正在尝试根据以下内容删除文本部分：

  • 来自：
    • 美国广播公司
    • 国防军
    • 全球健康指数
  • 对任何一个（同时保留这个词）：
    • 二维码
    • STU
    • 大众汽车

组成“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堆栈跟踪发布在这个问题的末尾）
  • 离子猴子（火狐）：工作！

实际输入：

  • 我的原始输入：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：我在这个问题上添加了几个标签，因为我已经在这些环境中尝试过，但实验失败了。

4

3 回答 3

3

问题是 (.|\s)* 因为任何空格字符都会匹配两者，并且它会允许它同时使用两个选项。这使它成倍地变大。

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

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

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

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

/ba*b/.match str

快速匹配。

您可以通过使用 just.*或 if .doesn't match newlines来解决此问题(.|\n)*

于 2013-09-10T10:34:59.617 回答
0

我很想尝试简化 re. 老实说，目前这并不是很复杂，但是如何：

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

除了行锚的开始和中间不必要的可选元素之外，这难道不是你所追求的吗？可能没有任何区别，但可能值得一试。

于 2013-05-16T08:48:25.273 回答
0

我认为您的问题可能在于随着文件变得越来越长，您可以匹配成对的 from 和 to 块大约 nxm / 2。这意味着您获得的结果呈指数级增长，占用了越来越多的源文件。如果文件以 ABC 开头并以 VWX 结尾，则其中一个匹配项将是整个文件。

为了让正则表达式引擎处理更少的匹配项，我的第一种方法是仅单独使用正(abc|def|ghi)则表达式(pqr|stu|vwx)。获得结果后，您可以遍历每个匹配项并尝试找到要阻止的第一个匹配项。完成此操作的一些伪代码是

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

尽管这为您自己创造了更多的工作，但这意味着正则表达式解析器不必一次将整个 n kB 文件保存在内存中，并且可以更有效地解析小块。

于 2013-07-25T07:04:44.610 回答