Node.JS Regex-Engine schlägt auf großen Eingang

Question

Die Frage ist ein wenig kompliziert, und Googeln hat nicht wirklich geholfen. Ich werde versuchen, nur relevante Aspekte einzubringen.

Ich habe ein großes Dokument in etwa folgendem Format:

Beispieleingabe:

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 

Ich versuche, den Abschnitt des Textes entsprechend der unten zu entfernen:

• Von beiden:
  • ABC
  • DEF
  • GHI
• Um eines (unter Beibehaltung dieses Wort):
  • PQR
  • STU
  • VWX

Die Worte, die machen up "Von" kann überall in einem erscheinen Linie (Schau dir GHI an). Aber zum Entfernen muss die gesamte Linie entfernt werden. (Die gesamte Linie GHI muss wie nachstehend in der Beispielausgabe entfernt werden)

Beispielausgabe:

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 

Das obige Beispiel tatsächlich schien mir leicht, bis ich es gegen sehr große Eingabedateien lief (49KB)

Was ich versucht:

Der reguläre Ausdruck ich bin derzeit mit ist (mit Groß- und Kleinschreibung und mu ltiline Modifikator):

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

Problem

Die oben regexp funktioniert wunderbar auf kleine Textdateien. Aber schlägt fehl/stürzt die Engine auf große Dateien ab. Ich habe es gegen die unten versucht:

• V8 (Node.js): Hängt
• Rhino: Hängt
• Python: Hängt
• Java: StackoverflowError (Stack-Trace am Ende dieser Frage gepostet)
• IonMonkey (Firefox): FUNKTIONIERT!

Actual Input:

• Mein ursprünglicher Eingang: http://ideone.com/W4sZmB

• Mein regulärer Ausdruck (split über mehrere Zeilen für Klarheit):

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

Frage:

• Ist mein regulärer Ausdruck korrekt? Kann es weiter optimiert werden, um dieses Problem zu vermeiden?
• Wenn es richtig ist, warum hängen andere Motoren unendlich? Ein Teil der Stack-Trace ist unten:

Stack Trace:

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: Ich füge mehrere Tags auf diese Frage, da ich es auf diesen Umgebungen und das Experiment gescheitert versucht haben.}

Answer 1

Das Problem ist die (. | \ S) *, weil jedes Leerzeichen beide passt und es beide Möglichkeiten erlaubt. Dadurch wird es exponentiell größer.

Sie können das Problem mit dieser Regex in Ruby sehen

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

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

, die für immer dauert, während ein im Wesentlichen identischen

/ba*b/.match str 

Matches schnell.

Sie können dieses Problem beheben, indem entweder nur .* oder wenn . mit Zeilenumbrüchen nicht überein (.|\n)*

Answer 2

Ich wäre versucht zu versuchen, die Re zu vereinfachen. Es ist nicht sehr im Moment kompliziert, ehrlich zu sein, aber wie wäre es:

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

Heißt das nicht, noch tun, was Sie nach, aber mit dem Beginn der Linie Anker und dem unnötigen optionales Element in der Mitte? Könnte keinen Unterschied machen, aber es könnte einen Versuch wert sein.

Answer 3

Ich denke, Ihr Problem könnte in der Tatsache liegen, dass mit immer länger werdenden Dateien Paare von und von Blöcken um ungefähr nxm/2 gehen können. Das bedeutet, dass Sie exponentiell mehr Ergebnisse erhalten, die mehr aufnehmen und mehr der Quelldatei. Wenn die Datei mit ABC begann und mit VWX endete, wäre eine der Übereinstimmungen die gesamte Datei.

Um der Regex-Engine weniger Übereinstimmungen zu geben, wäre mein erster Ansatz, nur (abc|def|ghi) und (pqr|stu|vwx) separat zu regex. Nachdem Sie die Ergebnisse zurückbekommen haben, können Sie jeden von match durchlaufen und versuchen, den ersten passenden Block zu finden. Einige psuedo-Code, dies zu erreichen

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 

wäre zwar für sich selbst mehr Arbeit schafft, bedeutet dies, dass die Regex-Parser nicht die gesamte n kB Datei im Speicher auf einmal zu halten hat, und kann analysiert werden durch kleine Blöcke viel effektiver.