Regex cho một tên người dùng tăng tiêu thụ CPU

Question

Chúng tôi có quy tắc sau đây để xác nhận tên của chúng tôi:

• Tên truy cập có thể có ký tự chữ và
• Tên truy cập có thể có một dấu gạch dưới, gạch nối hoặc dấu chấm hết
• Còn bây giờ giả tên người dùng nằm trong ASCII
• Tên người dùng không thể bắt đầu hoặc kết thúc bằng khoảng thời gian
• Tên người dùng không thể bắt đầu, kết thúc hoặc có bất kỳ khoảng trắng nào

Chúng tôi có regex sau cho cùng:

^(([a-zA-Z0-9]+[_-]*[a-zA-Z0-9]*)([\\.]*[a-zA-Z0-9])*)+$ 

Bây giờ cố gắng để phù hợp với một chuỗi Đặc biệt, việc sử dụng CPU tăng lên theo cấp số nhân. Ví dụ:

M45766235H.M96312865E@EXAMPLE.COM 

Rõ ràng, khớp với một chuỗi như trên sẽ không thành công ngay lập tức nhưng tôi muốn biết tại sao lại sử dụng nhiều chu kỳ CPU đó. mã cuối cùng:

import java.util.regex.*; 
public class R { 
    static final Pattern namePattern = Pattern.compile("^(([a-zA-Z0-9]+[_-]*[a-zA-Z0-9]*)([\\.]*[a-zA-Z0-9])*)+$"); 

    public static void main(String... args) { 
     final String userName = "M45766235H.M96312865E@EXAMPLE.COM"; 
     Matcher matcher = namePattern.matcher(userName); 
     System.out.println(matcher.matches()); 
    } 
} 

Trên một dòng khác nhau, tôi viết lại regex như dưới đây và nó hội chợ tốt:

^[\\w]+[\\w-_\\.]*[\\w]+$ 

Answer 1

Khi động cơ biểu hiện thường xuyên sử dụng thụt lùi rất nhiều, quá trình khớp trở nên rất chậm. Backtracking xảy ra rất nhiều khi bạn để các phần khác nhau của biểu thức khớp với các phần chồng chéo của đầu vào, đặc biệt khi không có kết quả khớp: công cụ sẽ thử khả năng phân tách đầu vào giữa các phần của biểu thức chính quy của bạn.

Hãy xem xét ví dụ đơn giản này từ regex của bạn: hãy sử dụng [a-zA-Z0-9]+[_-]*[a-zA-Z0-9]* để phù hợp với M45766235H. Lưu ý rằng có hai tiểu biểu có thể bao gồm tất cả các nhân vật bắt đầu với thứ hai: động cơ phải xem xét tất cả các khả năng:

[a-zA-Z0-9]+ [a-zA-Z0-9]* 
------------ ------------ 
M45766235H <nothing> 
M45766235 H 
M4576623  5H 
M457662  35H 
M45766  235H 
M4576  6235H 
M457   66235H 
M45   766235H 
M4   5766235H 
M   45766235H 

Do không có sự trùng khớp, đó là mười lần lặp lại vô dụng ngay tại đó. Nhưng đó không phải là kết thúc của nó! Khi có các biểu thức con khác trong hỗn hợp có thể tạo ra vùng phủ sóng không rõ ràng, thì mười kết quả phù hợp này sẽ được thử cho mỗi kết quả phù hợp có thể trong chuỗi.

Để nói rằng các hiệu ứng của backtracking sẽ tăng lên nhanh chóng sẽ là một cách nói: chúng nhân lên trong tiến trình hình học, cuối cùng tiêu thụ rất nhiều CPU của bạn.

Yếu tố đạo đức của câu chuyện này là để thử và giảm lượng backtracking. Ví dụ, biểu hiện thứ hai của bạn

^[\\w]+[\\w-_\\.]*[\\w]+$ 

thể được viết lại như thế này:

^\\w[\\w-_\\.]*\\w$ 

Hai biểu thức sẽ phù hợp với cùng một bộ đầu vào, nhưng khi có một trận đấu, biểu thức thứ hai sẽ có một kết hợp duy nhất, trong khi biểu thức ban đầu sẽ có khoảng (N-2)^3 các cách tách chuỗi phù hợp khác nhau giữa ba biểu thức con khớp với các ký tự từ.

Dưới đây là một số thông tin khác về chủ đề liên quan: Performance of Greedy vs. Lazy Quantifiers.