Làm cách nào để bạn biết hai ký tự đại diện có trùng lặp không?

Question

Cho hai chuỗi với * ký tự đại diện, tôi muốn biết nếu một chuỗi có thể được tạo ra mà sẽ phù hợp với cả hai.

Ví dụ, hai đây là một trường hợp đơn giản của chồng lên nhau:

1. Xin chào * Thế Giới
2. Hel *

Nhưng như vậy là tất cả những:

1. * .csv
2. báo cáo * .csv
3. reportsdump.csv

Có một thuật toán được xuất bản để thực hiện việc này không? Hoặc có lẽ một chức năng tiện ích trong Windows hoặc một thư viện mà tôi có thể gọi hoặc sao chép?

Answer 1

Vì mọi glob có thể được viết dưới dạng biểu thức chính quy và có thể tìm thấy giao điểm của hai biểu thức chính quy (trừ khi chúng không thực sự bình thường, nhưng chúng sẽ nằm trong trường hợp này), bạn có thể tìm thấy giao điểm của hai bóng bằng cách chuyển đổi chúng thành các biểu thức chính quy và sau đó tìm giao điểm của những biểu thức đó. Vì vậy, bạn có thể tìm hiểu xem hai bóng đèn giao nhau bằng cách tìm giao điểm của cụm từ thông dụng và kiểm tra xem nó có trống không.

Tuy nhiên kể từ khi những đống có nhiều hạn chế hơn so với biểu hiện thường xuyên, có một cách nhiều dễ dàng hơn:

Hãy gọi hai globs g1 và g2. Họ cắt nhau iff

1. Cả g1 và g2 đều trống hoặc chỉ chứa ký tự đại diện.
2. Cả g1 cũng không g2 là trống rỗng và là một trong các điều kiện sau đây là đúng (giả sử c1 là nhân vật đầu tiên của g1 và t1 các chuỗi chứa ký tự còn lại - tương tự cho g2 với c2 và t2):
   1. c1 và c2 đều bình đẳng và t1 và t2 giao
   2. c1 và/hoặc c2 là một ký tự đại diện và t1 giao cắt với g2
   3. c1 và/hoặc c2 là một ký tự đại diện và g1 giao cắt với t2

An thực hiện ví dụ trong Haskell:

intersect g1   []   = all (== '*') g1 
intersect []   g2   = all (== '*') g2 
intersect g1@('*':t1) g2@(c2:t2) = intersect g1 t2 || intersect t1 g2 
intersect g1@(c1:t1) g2@('*':t2) = intersect t1 g2 || intersect g1 t2 
intersect (c1:t1)  (c2:t2) = c1 == c2  && intersect t1 t2 

thuật toán này không phải là đặc biệt hiệu quả nếu những đống chứa rất nhiều ký tự đại diện, nhưng nó rất dễ dàng để thực hiện và vì bạn đang có khả năng lên kế hoạch sử dụng điều này với tên tập tin, tôi nghi ngờ bạn sẽ có globs dài hơn 1000 ký tự.

Answer 2

Đối với những gì nó có giá trị, đây là một thực hiện các thuật toán từ câu trả lời sepp2k trong C# (tôi đã sử dụng rõ ràng return true; và return false; cuộc gọi, cùng với ý kiến, cho thuật toán có thể đọc):

public static bool WildcardIntersect(string w1, string w2) 
{ 
    // if both are empty or contain wildcards 
    if ((string.IsNullOrEmpty(w1) || w1 == "*") 
     && (string.IsNullOrEmpty(w2) || w2 == "*")) 
     return true; 

    // if either string is empty, return false 
    // we can do this because we know the other string MUST be non-empty and non-wildcard 
    if (string.IsNullOrEmpty(w1) || string.IsNullOrEmpty(w2)) 
     return false; 

    char c1 = w1[0], // first character of wildcard string 1 
     c2 = w2[0]; // first character of wildcard string 2 
    string remain1 = w1.Substring(1), // remaining of wildcard string 1 
      remain2 = w2.Substring(1); // remaining of wildcard string 2 

    // if first letters match and remaining intersect 
    if ((c1 == c2 && WildcardIntersect(remain1, remain2)) 
     // if either is a wildcard and either remaining intersects with the other whole 
     || ((c1 == '*' || c2 == '*') && (WildcardIntersect(w1, remain2) || WildcardIntersect(remain1, w2)))) 
     return true; 

    // else, no match, return false 
    return false; 
} 

Answer 3

Theo tôi được biết bạn cố gắng xác định xem một regex là trực giao với regex khác? Nếu vậy, đây không phải là vấn đề tầm thường.

Dưới đây là thêm về Theory.

Dưới đây là giải pháp: Java library.

Cách sử dụng:

/** 
* @return true if the two regexes will never both match a given string 
*/ 
public boolean isRegexOrthogonal(String regex1, String regex2) { 
    Automaton automaton1 = new RegExp(regex1).toAutomaton(); 
    Automaton automaton2 = new RegExp(regex2).toAutomaton(); 
    return automaton1.intersection(automaton2).isEmpty(); 
} 

Answer 4

Đây là một C++ thực hiện các thuật toán được đề xuất bởi sepp2k với một thay đổi nhỏ:

bool intersect(const std::string& pattern1, const std::string& pattern2) { 
    if(pattern1.empty() && pattern2.empty()) return true; 
    if("*" == pattern1 || "*" == pattern2) return true; 

    if(pattern2.empty() && '*' == pattern1[0]) return true; 
    if(pattern1.empty() && '*' == pattern2[0]) return true; 

    if(pattern1.empty() || pattern2.empty()) return false; 

    char c1 = pattern1[0]; 
    char c2 = pattern2[0]; 
    string subPattern1 = pattern1.substr(1); 
    string subPattern2 = pattern2.substr(1); 


    if('*' == c1 && '*' == c2) 
     return intersect(pattern1, subPattern2) && intersect(subPattern1, pattern2); 

    if('*' == c1 && intersect(pattern1, subPattern2) 
     || '*' == c2 && intersect(subPattern1, pattern2) 
     || c1 == c2 && intersect(subPattern1, subPattern2)) { 
     return true; 
    } 

    return false; 
}