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

Question

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

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

1. Hello * World
2. Hel *

Но так же все это:

1. *. * CSV 1014 *
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

Вот реализация c ++ алгоритма, предложенного 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;
}

Answer 3

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

Вот еще о Теория.

Вот решение: Библиотека Java.

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

/**
 * @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 в 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;
}