So khớp văn bản giữa các dấu phân cách: biểu thức chính quy tham lam hoặc lười biếng?

Question

Đối với các vấn đề thường gặp nội dung trùng khớp giữa delimiters (ví dụ < và >), có hai mô hình chung:

• bằng cách sử dụng tham lam * hoặc + lượng hóa theo hình thức START [^END]* END, ví dụ <[^>]*> hoặc
• bằng cách sử dụng số liệuhoặc +? lười biếng ở dạng START .*? END, ví dụ: <.*?>.

Có lý do cụ thể nào để ưu tiên cái này cho người khác không?

Answer 1

Một số ưu điểm:

[^>]*:

• biểu cảm hơn.
• Ghi lại dòng mới bất kể cờ /s.
• Được coi là nhanh hơn, bởi vì động cơ không phải quay lại để tìm một trận đấu thành công (với [^>] động cơ không đưa ra lựa chọn - chúng tôi chỉ cung cấp một cách để khớp mẫu với chuỗi).

.*?

• Không "lặp lại code" - nhân vật cuối chỉ xuất hiện một lần.
• Đơn giản trong trường hợp dấu phân cách kết thúc dài hơn một ký tự. (một lớp nhân vật sẽ không hoạt động trong trường hợp này) Một thay thế phổ biến là (?:(?!END).)*. Điều này thậm chí còn tồi tệ hơn nếu dấu phân tách END là một mẫu khác.

Answer 2

Điều đầu tiên rõ ràng hơn, i. e. nó chắc chắn loại trừ dấu phân cách đóng là một phần của văn bản phù hợp. Điều này không được đảm bảo trong trường hợp thứ hai (nếu biểu thức chính quy được mở rộng để khớp với nhiều hơn chỉ là thẻ này).

Ví dụ: Nếu bạn cố gắng để phù hợp với <tag1><tag2>Hello! với <.*?>Hello!, regex sẽ phù hợp

<tag1><tag2>Hello! 

trong khi <[^>]*>Hello! sẽ phù hợp

<tag2>Hello! 

Answer 3

gì hầu hết mọi người không cần xem xét khi tiếp cận câu hỏi như thế này là những gì xảy ra khi regex không thể tìm thấy kết quả phù hợp. Đó là khi hố hoạt động sát thủ có nhiều khả năng xuất hiện nhất. Ví dụ, lấy ví dụ của Tim, nơi bạn đang tìm kiếm một cái gì đó như <tag>Hello!. Hãy xem xét những gì xảy ra với:

<.*?>Hello! 

Động cơ regex tìm thấy một < và nó nhanh chóng tìm thấy một kết thúc >, nhưng không >Hello!. Vì vậy, .*? tiếp tục tìm kiếm > rằng là theo sau là Hello!.Nếu không có một, nó sẽ đi tất cả các cách để kết thúc của tài liệu trước khi nó cho lên. Sau đó, công cụ regex tiếp tục quét cho đến khi tìm thấy một số khác < và thử lại. Chúng tôi đã biết cách điều đó sẽ xảy ra, nhưng động cơ regex thường không; nó đi qua cùng một rigamarole với mỗi < trong tài liệu. Bây giờ xem xét các regex khác:

<[^>]*>Hello! 

Như trước đây, nó nhanh chóng phù hợp với từ < đến >, nhưng không phù hợp với Hello!. Nó sẽ quay trở lại số <, sau đó thoát và bắt đầu quét tìm một số < khác. Nó vẫn sẽ kiểm tra mọi < như regex đầu tiên đã làm, nhưng nó sẽ không tìm kiếm tất cả các cách để kết thúc của tài liệu mỗi khi nó tìm thấy một.

Nhưng thậm chí còn tệ hơn thế. Nếu bạn nghĩ về nó, .*? có hiệu quả tương đương với một lookahead tiêu cực. Nó nói rằng "Trước khi tiêu thụ nhân vật tiếp theo, hãy đảm bảo phần còn lại của regex không thể khớp ở vị trí này." Nói cách khác,

/<.*?>Hello!/ 

... tương đương với:

/<(?:(?!>Hello!).)*(?:>Hello!|\z(*FAIL))/ 

Vì vậy, ở mọi vị trí mà bạn đang thực hiện, chứ không phải chỉ là một nỗ lực trận đấu bình thường, nhưng một lookahead đắt hơn nhiều. (Đó là ít nhất hai lần như tốn kém, vì lookahead có để quét ít nhất một nhân vật, sau đó các . đi trước và tiêu thụ một ký tự.)

((*FAIL) là một trong những backtracking-control verbs (còn được hỗ trợ trong PHP). |\z(*FAIL) phương tiện Perl "hoặc đến cuối tài liệu và từ bỏ".)

Cuối cùng, có một lợi thế khác của phương pháp tiếp cận lớp nhân vật phủ định. Trong khi nó không (như @Bart chỉ ra) đóng vai trò như lượng hóa là sở hữu, không có gì để ngăn chặn bạn từ làm là nó sở hữu, nếu hương vị của bạn hỗ trợ nó:

/<[^>]*+>Hello!/ 

... hoặc quấn nó trong một nhóm nguyên tử:

/(?><[^>]*>)Hello!/ 

Không chỉ những regex này sẽ không bao giờ quay trở lại không cần thiết, họ không phải lưu thông tin trạng thái có thể quay ngược lại được.