2009-01-06 38 views
8

Có cách nào để kiểm tra nếu cụm từ thông dụng "chứa" một cụm từ thông dụng khác không?
Ví dụ:
cụm từ thông dụng "chứa" một cụm từ thông dụng khác

RegEX1 = "a.*b"; 
RegEx2 = "a1.*b"; 

RegEX1 "chứa" RegEX2.

Theo như tôi biết - điều này không thể được thực hiện, tôi có sai không?


OK, joel.neely đã cho thấy rằng nó có thể được thực hiện (chưa đọc nó ...) học tập.

Nó có thể được thực hiện bằng ngôn ngữ lập trình không, C#?
Hiệu quả sẽ như thế nào? Mất bao lâu để kiểm tra 1000 cặp?

Trả lời

6

Có.

This paper chứa thảo luận chi tiết về chủ đề (xem phần 4.4).

+2

Bạn có thể làm rõ "có" của mình không. Tôi nghĩ rằng bạn đang nói "Có, bạn đã sai" và trích dẫn bài báo cho thấy làm thế nào nó có thể được thực hiện (từ một cái nhìn nhanh vào giấy). Nhưng nó sẽ là giá trị chính tả mà ra một cách rõ ràng. –

+1

Bài báo được đề cập chỉ nói "Đó là kết quả nổi tiếng cho hai biểu thức chính quy B và R, có thể dễ dàng giải đoán được liệu B có gộp R" hay không và mô tả "mô hình nội dung". Ngoài ra, phương pháp của bài báo dường như đơn giản liệt kê tất cả các chuỗi có độ dài Clueless

+1

Được chấp nhận mặc dù không đưa ra cách thực tế để đạt được ... – Dror

0

Chuyển đổi hai biểu thức thành các máy trạng thái tương đương và kiểm tra tất cả các đường dẫn trong cả hai máy đều cho phép cùng một kết quả phù hợp, nên thực hiện thủ thuật. Các lemme bơm rõ ràng nên được minded, do đó, tránh xem xét lại các nút cũ.

Nó sẽ chỉ hoạt động cho cụm từ thông dụng "đơn giản" (hoặc thực tế, bạn có gì, biểu thức đệ quy perls mang tính biểu cảm hơn).

Trong khi biểu đồ của máy trạng thái có thể có số lượng lớn đường dẫn, nó vẫn sẽ bị giới hạn (đặc biệt nếu nguồn cho biểu thức là con người). Vì vậy, bạn sẽ tìm thấy tất cả các đường dẫn cho phép của RegEX1, và kiểm tra, mỗi lần lượt, nếu nó cho phép trong RegEX2. Nếu tất cả các đường dẫn đều hợp lệ, bạn sẽ biết rằng đường dẫn được chứa trong đường dẫn khác.

+0

Có thể (trong một thời gian hợp lý) để chạy một thử nghiệm để có được một hệ thống phân cấp của biểu thức chính quy (vài trăm trong số họ)? bạn có thể cung cấp con trỏ cho mã không? – Dror

+0

Tôi không thấy lý do tại sao nó sẽ không thể, và trong thời gian tốt là tốt. Bạn sẽ phải xây dựng này từ đầu mặc dù, đó không phải là tầm thường. – Svend

+0

kiểm tra "tất cả các đường dẫn hợp lệ" cho tất cả các cặp có thể mất một thời gian rất dài. "kiểm tra tất cả các đường dẫn trong cả hai máy" như bạn nói có thể là vô hạn, hoặc tôi đang thiếu một cái gì đó? – Dror

Các vấn đề liên quan