Как вы узнаете, перекрываются ли две маски?

Question

Учитывая две строки с * подстановочными знаками, я хотел бы знать, может ли быть создана строка, которая бы соответствовала обоим.

Например, эти два являются простой случай перекрытия:

1. Здравствуйте * Мир
2. Hel *

Но так все из них:

1. * .csv
2. отчеты * .csv
3. reportsdump.csv

Есть ли алгоритм, опубликованный для этого? Или, возможно, утилита в Windows или в библиотеке, которую я мог бы вызвать или скопировать?

Answer 1

Поскольку каждый глобус может быть записан как регулярное выражение, и можно найти пересечение двух регулярных выражений (если они не являются действительно регулярными, но они были бы в этом случае), вы можете найти пересечение двух глобусов преобразуя их в регулярные выражения, а затем найдя их пересечение. Таким образом, вы можете узнать, пересекаются ли два глобуса, найдя пересечение регулярных выражений и проверяя, является ли он пустым.

Однако поскольку шарики более ограничены, чем регулярные выражения, есть гораздо простой способ:

Давайте назовем два комков g1 и g2. Они пересекаются, если

1. Оба g1 и g2 пусты или содержат только символы.
2. Ни g1, ни g2 являются пустыми и один из следующих условий (пусть c1 быть первым символом g1 и t1 строка, содержащая оставшиеся символы - то же самое для g2 с c2 и t2):
   1. c1 и c2 равны и t1 и t2 пересекаются
   2. c1 и/или c2 является подстановочным и t1 пересекается с g2
   3. c1 и/или c2 является подстановочным и g1 пересекается с t2

Пример реализации в 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 

Этот алгоритм не особенно эффективно, если шарики содержат много масок, но это очень легко реализовать и, так как вы, вероятно, планирует использовать это с именами файлов, я сомневайтесь, что у вас будут глобусы длиной более 1000 символов.

Answer 2

Для чего это стоит, вот одна реализации алгоритма от ответа sepp2k в C# (я использовал явные return true; и return false; вызовов, наряду с комментариями, для алгоритма читаемости):

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

Как я понимаю вы пытаетесь определить, является ли регулярное выражение ортогональным к другому регулярному выражению? Если это так, это совсем не тривиальная проблема.

Вот больше о Theory.

Вот решение: Java library.

Использование:

/** 
* @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

Вот с ++ реализация алгоритма предложен sepp2k с небольшими изменениями:

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; 
}