Tại sao cụm từ thông dụng có thể có thời gian chạy theo hàm mũ?

Question

Có thể viết một Regex cần trong một số trường hợp thời gian chạy theo hàm mũ. Ví dụ như vậy là (aa|aa)*. Nếu có một đầu vào của một số lẻ của a s nó cần thời gian chạy theo cấp số nhân.

Thật dễ dàng để kiểm tra điều này. Nếu đầu vào chỉ chứa a s và có chiều dài 51, Regex cần vài giây để tính toán (trên máy của tôi). Thay vào đó, nếu độ dài đầu vào là 52 thì thời gian tính toán của nó không đáng chú ý (tôi đã thử nghiệm điều này bằng trình phân tích cú pháp-Regex của JavaRE).

Tôi đã viết bộ phân tích cú pháp Regex để tìm lý do cho hành vi này, nhưng tôi không tìm thấy nó. Trình phân tích cú pháp của tôi có thể tạo một số AST hoặc NFA dựa trên Regex. Sau đó, nó có thể dịch NFA thành DFA. Để làm điều này, nó sử dụng powerset construction algorithm.

Khi tôi phân tích cú pháp Rgex được đề cập ở trên, trình phân tích cú pháp tạo NFA với 7 trạng thái - sau khi chuyển đổi chỉ còn lại 3 trạng thái trong DFA. DFA đại diện cho Regex (aa)* hợp lý hơn, có thể được phân tích cú pháp rất nhanh.

Vì vậy, tôi không hiểu tại sao có các trình phân tích cú pháp có thể quá chậm. Lý do cho điều này là gì? Họ không dịch NFA sang DFA? Nếu có, tại sao không? Và lý do kỹ thuật tại sao chúng tính toán chậm như vậy?

Answer 1

Russ Cox has a very detailed article about why this is and the history of regexes (part 2, part 3).

Kết hợp cụm từ thông dụng có thể đơn giản và nhanh chóng, sử dụng các kỹ thuật dựa trên tự động hữu hạn đã được biết đến nhiều thập kỷ. Ngược lại, Perl, PCRE, Python, Ruby, Java và nhiều ngôn ngữ khác có cách triển khai biểu thức chính quy dựa trên tính năng quay lại đệ quy đơn giản nhưng có thể rất chậm. Ngoại trừ backreferences, các tính năng được cung cấp bởi việc triển khai backtracking chậm có thể được cung cấp bởi các triển khai dựa trên automata với tốc độ nhanh hơn và ổn định hơn đáng kể.

Phần lớn, nó đi xuống đến sự phát triển các tính năng không thường xuyên trong các biểu thức "thường xuyên" như backreferences, và (tiếp theo) sự thiếu hiểu biết của hầu hết các lập trình viên rằng có những lựa chọn thay thế tốt hơn cho regexes mà không có các tính năng như vậy (đó là nhiều người trong số họ).

Khi viết trình soạn thảo văn bản vào đầu những năm 1980, Rob Pike đã viết một biểu thức chính quy mới, được Dave Presotto trích xuất vào thư viện xuất hiện trong ấn bản thứ tám.Việc thực hiện của Pike kết hợp theo dõi submatch thành một mô phỏng NFA hiệu quả nhưng, giống như phần còn lại của nguồn ấn bản thứ tám, không được phân phối rộng rãi. Bản thân Pike không nhận ra rằng kỹ thuật của anh ta là mới. Henry Spencer đã thực hiện lại giao diện thư viện phiên bản thứ tám từ đầu, nhưng sử dụng backtracking và phát hành triển khai của mình vào miền công cộng. Nó đã trở nên được sử dụng rộng rãi, cuối cùng là cơ sở cho việc triển khai biểu thức chính quy chậm được đề cập trước đó: Perl, PCRE, Python, v.v. (Trong phòng thủ của mình, Spencer biết rằng các thói quen có thể chậm, và anh ta không biết rằng một thuật toán hiệu quả hơn đã tồn tại. Anh thậm chí còn cảnh báo trong tài liệu này, “Nhiều người dùng đã tìm thấy tốc độ hoàn toàn phù hợp, mặc dù thay thế bên trong của egrep mã này sẽ là một sai lầm. ”) Việc thực hiện biểu thức chính quy của Pike, mở rộng để hỗ trợ Unicode, được cung cấp miễn phí với sam vào cuối năm 1992, nhưng thuật toán tìm kiếm biểu thức chính quy đặc biệt hiệu quả đã không được chú ý.

Answer 2

Cụm từ thông dụng tuân theo formal definition này được tính theo thời gian tuyến tính, vì chúng có các automatas hữu hạn tương ứng. Chúng được xây dựng chỉ từ dấu ngoặc đơn, thay thế | (đôi khi được gọi là tổng hợp), sao Kleene * và nối.

Mở rộng cụm từ thông dụng bằng cách thêm, ví dụ: tham chiếu ngược có thể dẫn đến các biểu thức chính quy hoàn chỉnh NP. Ở đây bạn có thể tìm thấy an example of regular expression nhận ra các số không phải là số nguyên tố.

Tôi đoán rằng, việc triển khai mở rộng như vậy có thể có thời gian đối sánh phi tuyến tính ngay cả trong các trường hợp đơn giản.

Tôi đã thực hiện thử nghiệm nhanh trong Perl và biểu thức chính quy của bạn tính nhanh như nhau cho số lẻ và số chẵn của 'a'.