Hiệu suất kém của các biểu thức chính quy?

Đăng bởi Eyal Schneider vào ngày 21 tháng 5 năm 2009 Gói java.util.regex đã được thêm vào Java trong phiên bản 1.4. Nó là một công cụ rất mạnh mẽ và người ta cần phải trở thành bậc thầy để sử dụng nó một cách chính xác. Ngay cả khi một biểu thức chính quy là đúng, nó có thể rất chậm nếu không được viết một cách thông minh. Tiếp tục đọc nếu bạn muốn hiểu nguyên nhân của vấn đề hoặc cuộn đến cuối trang nơi bạn sẽ tìm thấy 10 mẹo hữu ích để cải thiện hiệu suất của biểu thức chính quy trong Java.

Có thực sự chậm như vậy không?

Giả sử chúng ta chỉ muốn chọn các dòng chứa chuỗi ký tự "a" và "b". Giải pháp đúng có thể là: (a*b*)* Tuy nhiên, nếu bạn chạy biểu thức với chuỗi chẳng hạn như “aaaaaaaaaaaaaaaaaaaaaaaaaaaaax” , sẽ mất vài phút trước khi nó kết thúc và báo cáo không có kết quả trùng khớp! Tất nhiên, biểu thức chính quy tốt nhất trong trường hợp này sẽ là: (a|b)* Quá trình này mất chưa đến một phần nghìn giây trên máy của tôi có cùng chuỗi. Rõ ràng có vấn đề về hiệu suất ở đây.

Tại sao chuyện này đang xảy ra?

Giống như hầu hết các công cụ regrec, Java sử dụng cách tiếp cận NFA (Non-Deterministic Finite Automata). Công cụ này quét từng thành phần biểu thức chính quy một và tiến tới chuỗi đầu vào tương ứng. Và anh ta có thể quay lại từ đầu để tìm giải pháp thay thế phù hợp nếu đi đến “ngõ cụt”. Các kết quả thay thế có được bằng cách sử dụng các cấu trúc thông thường như định lượng ( *, +, ? ) và các cấu trúc thay thế (ví dụ a|b|c|d ). Kỹ thuật nghiên cứu này được gọi là quay lui. Trong ví dụ khủng khiếp ở trên, công cụ sẽ thực sự xem xét TẤT CẢ các chuỗi phân tách ký hiệu "a" thành các chuỗi nhỏ hơn cho đến khi nhận ra rằng không có kết quả trùng khớp nào. Ví dụ này cho thấy thuật toán quay lui có thể dẫn đến ước tính thời gian theo cấp số nhân như thế nào (tùy thuộc vào độ dài của chuỗi đầu vào). Điều này cũng cho thấy một đặc tính quan trọng của NFA: sẽ luôn có những trường hợp xấu nhất gần như khớp với mô hình. Nếu tìm thấy kết quả phù hợp, việc tìm kiếm sẽ dừng lại. Cách tiếp cận chính khác để sử dụng trong biểu thức chính quy là DFA (Máy tự động hữu hạn xác định). Theo cách tiếp cận này, biểu thức chính quy thực sự xây dựng một máy tự động được sử dụng để duyệt từng ký tự chuỗi đầu vào mà không cần quay lại. Điều này mang lại thời gian tuyến tính cho toàn bộ dữ liệu đầu vào, bất kể độ phức tạp của biểu thức chính quy. Thay vì quét tuần tự một chuỗi để tìm kết quả khớp (như trong NFA), DFA mô phỏng quá trình quét song song. Vậy tại sao Java (và .NET, Perl, Python, Ruby, PHP, v.v.) lại sử dụng NKA mà không phải DKA có hành vi tốt hơn nhiều? Lý do là NKA có một số lợi thế đáng kể:

Biên dịch nhanh hơn và yêu cầu ít bộ nhớ hơn
Cho phép một số tính năng hữu ích (xem hướng dẫn chi tiết của Sun ):

Chụp nhóm và liên kết ngược
Kiểm tra vị trí
Bộ định lượng mở rộng (Tham lam và Lười biếng)

Điều quan trọng cần lưu ý là các thuật ngữ phổ biến NKA và DKA không chính xác khi được sử dụng trong ngữ cảnh của các biểu thức chính quy. Về lý thuyết, hai mô hình này có sức mạnh tính toán như nhau. Điều này có nghĩa là bạn không thể viết một biểu thức chính quy trong một mô hình automata mà không thể biểu diễn được trong một mô hình khác. Trong thực tế, cần có nhiều khả năng hơn để hai loại triển khai này khác nhau về ngữ nghĩa. Động cơ NKA cung cấp tính linh hoạt cao hơn khiến chúng vượt trội hơn DKA về khả năng tính toán. Do tốc độ của DFA và các tính năng độc đáo của NFA, có thêm 2 cách “đúc sẵn” để triển khai biểu thức chính quy. Một số triển khai sử dụng cả hai loại (ví dụ: GNU egrep, chọn một công cụ cụ thể trong thời gian chạy) và một số đã quản lý để triển khai phiên bản kết hợp thực sự (ví dụ: biểu thức chính quy Tcl) với tất cả các lợi ích.

lời khuyên

Sau đây là một số mẹo về cách tránh các vấn đề về hiệu quả của biểu thức chính quy trong Java. Nhiều trong số đó nhằm mục đích giảm lợi nhuận.

1) Biên dịch trước

Trite, nhưng đáng nói. Nếu bạn sử dụng biểu thức chính quy nhiều lần, hãy đảm bảo biên dịch nó trước:

// компиляция p = Pattern.compile(regex, flags); … // использование Matcher a = p.matcher(input);

2) Bộ định lượng lười biếng và Bộ định lượng tham lam

Theo mặc định, các bộ định lượng ( * + ? ) là tham lam. Điều này có nghĩa là họ bắt đầu khớp với chuỗi dài nhất có thể và sau đó dần dần hoạt động trở lại nếu cần. Nếu bạn biết trước rằng các kết quả khớp thường sẽ ngắn, bạn nên sử dụng bộ định lượng lười biếng. Họ bắt đầu từ trận đấu nhỏ nhất và tiến xa hơn nếu cần thiết. Giả sử chúng ta chỉ muốn tìm những dòng khớp với chuỗi "xin chào". .*hello.* thông thường sẽ làm đúng mọi thứ, nhưng nếu chúng ta biết rằng "hello" thường xuất hiện gần đầu văn bản hơn thì .*?hello.* sẽ hoạt động nhanh hơn trung bình.

3) Sử dụng các bộ định lượng siêu tham lam nếu có thể

Không giống như các bộ định lượng lười biếng, ảnh hưởng đến hiệu suất nhưng không ảnh hưởng đến hành vi thông thường, các bộ định lượng siêu tham lam thực sự có thể thay đổi ý nghĩa của một biểu thức chính quy. Khi *+ được sử dụng thay vì * , kết quả khớp đầu tiên sẽ có tính tham lam (nghĩa là kết quả lớn nhất có thể như thể nó chỉ là *), nhưng sẽ không có dự phòng nếu nó thất bại, ngay cả khi điều này khiến toàn bộ tìm kiếm không thành công. Khi nào điều này có thể hữu ích? Giả sử chúng ta cần tìm văn bản trong dấu ngoặc kép. \"[^\"]*\" thông thường sẽ hoạt động tốt. Tuy nhiên, nó sẽ tạo ra sự thụt lề không cần thiết trong các trường hợp phủ định (ví dụ: “bla bla bla). Việc sử dụng \"[^\"]*+\" sẽ loại bỏ rollback mà không thay đổi ý nghĩa của biểu thức. Việc nhóm độc lập đạt được hiệu quả tương tự và thậm chí còn mang lại nhiều quyền kiểm soát hơn (xem hướng dẫn của Sun ).

4) Tránh chụp nhóm

Theo mặc định, bất kỳ biểu thức nào trong ngoặc đơn đều được coi là một nhóm. Điều này có ảnh hưởng nhỏ đến hiệu suất. Làm cho nhóm của bạn trở nên "không thể bị bắt" bất cứ khi nào có thể bằng cách bắt đầu chúng bằng (?: thay vì ( .

5) Sử dụng xen kẽ một cách khôn ngoan

Khi sử dụng tính năng xen kẽ (ví dụ Paul|Jane|Chris ), thứ tự mà công cụ cố gắng khớp các tùy chọn giống như thứ tự chúng xuất hiện. Bạn có thể tận dụng tính năng này và đặt các tùy chọn phổ biến nhất gần đầu. Điều này sẽ cải thiện thời gian phản hồi tích cực trung bình.

6) Tránh mơ hồ

Viết biểu thức chính quy theo cách giảm thiểu số lượng kết quả khớp khác nhau trong chuỗi đầu vào. Ví dụ: biểu thức chính quy (a*b*)* được đưa ra ở đầu bài viết cho phép diễn giải chuỗi "aabb" theo quá nhiều cách: (a2b2) (a1)(a1)(b1)(b1) (a2)(b2) (a1)(a1b2) etc… Regexp (a|b)*, mặt khác, chỉ diễn giải duy nhất sự kết hợp tích cực. Điều này rất quan trọng để giảm lợi nhuận trong các trường hợp gần khớp.

7) Xem trước

Xem trước cho phép bạn thêm các hạn chế về trình tự ở bên trái/phải của vị trí hiện tại. Đặc biệt, với cái nhìn tiêu cực, bạn có thể tìm kiếm các dòng không chứa một số chuỗi (chúng ta sẽ làm gì nếu không có thứ này!). Làm thế nào điều này có thể giúp tăng năng suất? Giả sử chúng ta muốn lấy URL từ thẻ liên kết. Hãy xem xét biểu thức chính quy sau: a .* href=(\S*).*/ Đối với các thẻ thông thường, biểu thức này sẽ chỉ khớp với địa chỉ nếu văn bản chứa thuộc tính "href" (\S được sử dụng cho tất cả các ký tự ngoại trừ dấu phân cách). Nhưng trên một số thẻ bất thường, chẳng hạn, việc khôi phục sẽ xảy ra. Ví dụ: “a href= href=href=…. href=thứ gì đó.” Biểu thức chính quy sau đây sẽ ngăn điều này xảy ra khi thay thế “.*” trong biểu thức bằng nội dung nào đó không khớp với “href”: a ((?!href).)* href=(\S*)((?!href).)*/

8) Chỉ định độ dài

Java chứa trình tối ưu hóa biểu thức chính quy để kiểm tra độ dài của chuỗi đầu vào so với độ dài tối thiểu và tối đa thu được từ biểu thức chính quy. Điều này cho phép bạn ngừng tìm kiếm ngay lập tức trong một số trường hợp. Để hỗ trợ cơ chế này, số lần lặp lại phải được chỉ định bất cứ khi nào có thể (ví dụ: [01]{6} khớp với tất cả các chuỗi nhị phân dài sáu ký tự).

9) Chọn các dòng giống nhau

Đôi khi các chuỗi giống nhau được ẩn bên trong các nhóm hoặc các lựa chọn thay thế: (hello|hell|heel) Biểu thức này có thể được đơn giản hóa thành: he(llo|ll|el) Bằng cách thực hiện việc này, chúng tôi cung cấp thêm thông tin cho trình tối ưu hóa biểu thức chính quy.

10) Kiểm tra biểu thức chính quy của bạn

Có thể là khôn ngoan nếu bạn kiểm tra biểu thức chính quy trước khi nó được sử dụng trong một ứng dụng quan trọng về hiệu năng. Viết một điểm chuẩn vi mô để kiểm tra biểu thức của bạn trên nhiều dữ liệu đầu vào khác nhau. Hãy đảm bảo kiểm tra dữ liệu có độ dài khác nhau và cả dữ liệu gần giống với mẫu của bạn.

Liên kết:

http://java.sun.com/docs/books/tutorial/essential/regex/index.html http://www.javaworld.com/javaworld/jw-09-2007/jw-09-optimizingregex.html?page =1 http://www.softec.st/en/OpenSource/DevelopersCorner/RegularExpressions/RegularExpressionEngines.html http://www.devarticles.com/c/a/Java/NFA-DFA-POSIX-and-the-Mechanics -of-Biểu hiện-Xử lý/