Node.JS Động cơ Regex không thành công trên đầu vào lớn

Question

Câu hỏi này hơi phức tạp và googling không thực sự hữu ích. Tôi sẽ cố gắng chỉ đưa vào những khía cạnh liên quan của nó.

Tôi có một tài liệu lớn trong khoảng định dạng sau:

Sample 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 

Tôi cố gắng để loại bỏ các phần của văn bản theo dưới đây:

• Từ một trong hai:
  • ABC
  • DEF
  • GHI
• Để một trong hai (trong khi giữ lại từ này):
  • PQR
  • STU
  • VWX

Những lời mà làm "Từ" có thể xuất hiện ở bất kỳ đâu trong dòng (Nhìn vào GHI). Nhưng để loại bỏ toàn bộ dòng cần phải được loại bỏ. (Toàn bộ dòng chứa GHI cần phải được loại bỏ như trong đầu ra mẫu dưới đây)

Sample Output:

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 

Ví dụ trên thực tế dường như dễ dàng đối với tôi cho đến khi tôi chạy nó chống lại tập tin đầu vào rất lớn (49KB)

Những gì tôi đã cố gắng:

Các biểu hiện thường xuyên tôi hiện đang sử dụng là (với trường hợp không nhạy cảm và mu ltiline modifier):

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

Vấn đề

Các công trình regexp trên tuyệt vời trên các tập tin văn bản nhỏ. Nhưng không thành công/làm hỏng động cơ trên các tệp lớn. Tôi đã thử nó so với đồng dưới đây:

• V8 (Node.js): treo cứng
• Rhino: treo cứng
• Python: treo cứng
• Java: StackoverflowError (Stack trace được trả vào cuối của câu hỏi này)
• IonMonkey (Firefox): CÔNG TRÌNH!

Input Thực tế:

• Input ban đầu của tôi: http://ideone.com/W4sZmB

• biểu hiện thường xuyên của tôi (split trên nhiều dòng cho rõ ràng):

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

Câu hỏi:

• Cụm từ thông dụng của tôi có đúng không? Nó có thể được tối ưu hóa thêm để tránh vấn đề này không?
• Trong trường hợp chính xác, tại sao các công cụ khác treo vô hạn? Một phần của stack trace là dưới đây:

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: tôi thêm nhiều thẻ cho câu hỏi này vì tôi đã thử nó trên những môi trường và thí nghiệm thất bại.}

Answer 1

Sự cố là (. | \ S) * vì mọi ký tự khoảng trắng sẽ khớp với cả hai ký tự và nó sẽ cho phép nó đi xuống cả hai tùy chọn. Điều này làm cho nó nhận được lớn hơn theo cấp số nhân.

Bạn có thể thấy vấn đề với regex này trong ruby ​​

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

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

mà mất mãi mãi, trong khi một cách bài bản giống hệt một

/ba*b/.match str 

trận đấu một cách nhanh chóng.

Bạn có thể sửa lỗi này bằng cách sử dụng chỉ .* hoặc nếu . không phù hợp với dòng mới (.|\n)*

Answer 2

Tôi muốn bị cám dỗ để thử đơn giản hóa lại. Nó không phải rất phức tạp tại thời điểm này phải trung thực nhưng làm thế nào về:

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

Không mà vẫn làm những gì bạn đang sau, nhưng với sự khởi đầu của dòng neo và các yếu tố bắt buộc không cần thiết ở giữa? Có thể không tạo ra bất kỳ sự khác biệt nào nhưng nó có thể đáng để thử.

Answer 3

Tôi nghĩ rằng sự cố của bạn có thể nằm trong thực tế là tệp càng dài và lâu hơn, bạn có thể khớp các cặp từ và đến khối bằng khoảng nxm/2. Điều này có nghĩa là bạn nhận được nhiều kết quả hơn. thêm tệp nguồn. Nếu tệp bắt đầu bằng ABC và kết thúc bằng VWX, thì một trong các kết quả trùng khớp sẽ là toàn bộ tệp.

Để cung cấp cho động cơ regex ít khớp hơn để giải quyết, cách tiếp cận đầu tiên của tôi sẽ chỉ là regex trên (abc|def|ghi) và (pqr|stu|vwx) riêng biệt. Sau khi bạn nhận được kết quả, bạn có thể đi qua từng kết quả từ trận đấu và thử và tìm kết quả phù hợp đầu tiên để chặn. Một số psuedo-mã để thực hiện điều này sẽ

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 

Mặc dù điều này tạo ra nhiều việc hơn cho chính mình, nó có nghĩa là phân tích cú pháp regex không nhất thiết phải giữ các tập tin toàn bộ n kB trong bộ nhớ cùng một lúc, và có thể phân tích cú pháp thông qua các khối nhỏ hiệu quả hơn nhiều.