biểu hiện thường xuyên đi vào vòng lặp vô hạn

Question

Tôi đang phân tích cú pháp (loài) tên có dạng:

Parus Ater 
H. sapiens 
T. rex 
Tyr. rex 

mà thường có hai nhiệm kỳ (nhị thức) nhưng đôi khi có 3 hoặc nhiều hơn.

Troglodytes troglodytes troglodytes 
E. rubecula sensu stricto 

tôi đã viết

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s*[a-z]+)* 

mà làm việc hầu hết thời gian nhưng đôi khi đi vào một vòng lặp vô hạn. Phải mất một thời gian để theo dõi nó đã được trong regex phù hợp và sau đó tôi nhận ra nó là một lỗi đánh máy và tôi nên viết

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s+[a-z]+)* 

hoạt động đúng.

Câu hỏi của tôi là:

• tại sao vòng lặp này xảy ra?
• có cách nào để tôi có thể kiểm tra các lỗi regex tương tự trước khi chạy chương trình không? Nếu không, sẽ rất khó để bẫy chúng trước khi prgram được phân phối và gây ra vấn đề.

[Lưu ý: Tôi không cần biểu thức tổng quát hơn cho các loài - có đặc điểm kỹ thuật regex chính thức 100+ cho tên loài - đây chỉ là bộ lọc ban đầu]. Chú ý: Vấn đề nảy sinh bởi vì mặc dù hầu hết các tên đã được trích xuất chính xác thành 2 hoặc đôi khi 3/4 thuật ngữ (như chúng in nghiêng) có một vài sai tích cực (như "Homo sapiens lives in big cities like London") và trận đấu thất bại tại "L". ]

LƯU Ý: Khi gỡ lỗi, tôi thấy rằng regex thường hoàn thành nhưng rất chậm (ví dụ: trên các chuỗi đích ngắn hơn). Nó là có giá trị mà tôi tìm thấy lỗi này thông qua một trường hợp bệnh lý. Tôi đã học được một bài học quan trọng!

Answer 1

Để giải quyết phần đầu tiên của câu hỏi, bạn nên đọc trên catastrophic backtracking. Về cơ bản, điều đang xảy ra là có quá nhiều cách để phù hợp với biểu thức chính quy của bạn với chuỗi của bạn và trình phân tích cú pháp liên tục theo dõi lại để thử và làm cho nó hoạt động.

Trong trường hợp của bạn, đó có thể là sự lặp lại lồng nhau: (\s*[a-z]+)* Điều này có thể gây ra một số vòng rất rất lạ. Như Qtax đã chỉ ra một cách thành thạo, thật khó để nói mà không có thêm thông tin.

Phần thứ hai của câu hỏi của bạn, thật không may, không thể trả lời. Về cơ bản nó là Halting problem. Vì Biểu thức chính quy về cơ bản là một máy trạng thái hữu hạn có đầu vào là một chuỗi, bạn không thể tạo một giải pháp chung dự đoán cụm từ thông dụng nào sẽ quay trở lại thảm họa, và sẽ không.

Theo một số mẹo để làm cho cụm từ thông dụng của bạn chạy nhanh hơn? Đó là một con giun lớn. Tôi đã dành rất nhiều thời gian để học các cụm từ thông dụng, và một số thời gian tối ưu hóa chúng, và đây là những gì tôi thấy thường giúp:

1. Biên dịch các biểu thức chính quy của bạn bên ngoài vòng lặp, nếu ngôn ngữ của bạn hỗ trợ nó.
2. Bất cứ khi nào có thể, hãy thêm anchors khi bạn biết chúng hữu ích.Đặc biệt là ^ để bắt đầu chuỗi. Xem thêm: Word Boundaries
3. Tránh lặp lại lồng nhau như bệnh dịch hạch. Nếu bạn phải có nó (mà bạn sẽ), làm tốt nhất của bạn để cung cấp gợi ý cho động cơ để ngắn mạch bất kỳ backtracking ngoài ý muốn.
4. Tận dụng lợi thế của cấu trúc hương vị để tăng tốc độ. Tôi là một phần của Non-Capturing groups và possessive quantifiers. Họ không xuất hiện trong mọi hương vị, nhưng khi họ làm, bạn nên sử dụng chúng. Ngoài ra, hãy xem Atomic Groups
5. Tôi luôn thấy điều này là đúng: Biểu thức chính quy càng dài, Bạn càng gặp nhiều rắc rối khi làm cho nó hiệu quả. Cụm từ thông dụng là một công cụ tuyệt vời và mạnh mẽ, chúng giống như một chiếc búa siêu thông minh. Don't fall into the trap of seeing everything as a nail. Đôi khi chức năng chuỗi bạn đang tìm kiếm nằm ngay dưới mũi của bạn.

Hy vọng điều này sẽ giúp bạn. Chúc may mắn.

Answer 2

Đối với regex đầu tiên:

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s*[a-z]+)* 

Các quay lui thảm khốc xảy ra do (\s*[a-z]+)* như đã chỉ ra trong các nhận xét. Tuy nhiên, nó chỉ đúng nếu bạn đang xác thực chuỗi với String.matches(), vì đây là trường hợp duy nhất gặp phải ký tự không hợp lệ khiến động cơ thử và quay lại, thay vì trả về kết quả khớp (vòng Matcher).

Chúng ta phù hợp với một chuỗi không hợp lệ đối với (\s*[a-z]+)*:

inputstringinputstring; 

(Repetition 1) 
\s*=(empty) 
[a-z]+=inputstringinputstring 
FAILED 

Backtrack [a-z]+=inputstringinputstrin 
(Repetition 2) 
\s*=(empty) 
[a-z]+=g 
FAILED 

(End repetition 2 since all choices are exhausted) 
Backtrack [a-z]+=inputstringinputstri 
(Repetition 2) 
\s*=(empty) 
[a-z]+=ng 
FAILED 

Backtrack [a-z]+=n 
(Repetition 3) 
\s*(empty) 
[a-z]+=g 
FAILED 

(End repetition 3 since all choices are exhausted) 
(End repetition 2 since all choices are exhausted) 
Backtrack [a-z]+=inputstringinputstr 

Bởi bây giờ, bạn nên có chú ý đến vấn đề này. Hãy để chúng tôi xác định T(n) vì lượng công việc để kiểm tra một chuỗi độ dài n không khớp với mẫu. Từ phương pháp quay ngược lại, chúng tôi biết T(n) = Sum [i = 0..(n-1)] T(i). Từ đó, chúng ta có thể lấy được T(n + 1) = 2T(n), điều đó có nghĩa là quá trình backtracking là theo cấp số nhân trong thời gian phức tạp!

Thay đổi *-+tránh những vấn đề hoàn toàn, kể từ khi một thể hiện của sự lặp lại chỉ có thể bắt đầu từ ranh giới giữa một nhân vật không gian và một nhân vật bảng chữ cái tiếng Anh. Ngược lại, regex đầu tiên cho phép một sự lặp lại để bắt đầu ở giữa bất kỳ 2 ký tự bảng chữ cái nào.

Để chứng minh điều này, (\s+[a-z]+\s*)* sẽ cung cấp cho bạn backtracking địa ngục khi chuỗi đầu vào không hợp lệ chứa nhiều lời mà được tách ra với nhiều không gian liên tiếp, vì nó cho phép nhiều địa điểm cho một trường hợp lặp lại để bắt đầu. Công thức này theo công thức b^d trong đó b là số lượng không gian liên tiếp tối đa (trừ 1) và d là số chuỗi không gian. Nó ít nghiêm trọng hơn regex đầu tiên bạn có (nó đòi hỏi ít nhất một bảng chữ cái Englsh và một ký tự không gian cho mỗi lần lặp lại, trái ngược với một bảng chữ cái tiếng Anh cho mỗi lần lặp lại trong regex đầu tiên của bạn), nhưng nó vẫn là một vấn đề.