algorithm - 如何判断两个通配符是否重叠？

Question

给定两个带有 * 通配符的字符串，我想知道是否可以创建一个匹配两者的字符串。

例如，这两个是一个简单的重叠情况：

1. 你好世界
2. 赫尔*

但所有这些也是如此：

1. *.csv
2. 报告*.csv
3. 报告转储文件

是否有为此发布的算法？或者也许是 Windows 中的实用程序函数或我可以调用或复制的库？

Answer 1

由于每个 glob 都可以写成一个正则表达式，并且可以找到两个正则表达式的交集（除非它们不是真正的正则，但在这种情况下它们会是），你可以通过将它们转换为来找到两个 glob 的交集正则表达式，然后找到它们的交集。所以你可以通过查找正则表达式的交集并检查它是否为空来找出两个glob是否相交。

但是，由于 glob 比正则表达式更受限制，因此有一种更简单的方法：

我们称这两个 glob 为 g1 和 g2。它们相交 iff

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

如果 glob 包含大量通配符，则此算法不是特别有效，但它很容易实现，并且由于您可能计划将其与文件名一起使用，我怀疑您的 glob 会超过 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

您可以在模式长度的总和中以线性时间解决此问题：

如果两个字符串都以非通配符开头或结尾，请检查它们是否匹配，直到一个模式遇到通配符（否则它们不匹配）。这将问题减少到至少一种模式以通配符开头并且至少一种模式以通配符结尾的情况。如果两种模式都有通配符（某处），那么它们必须匹配：

• 如果 p1 以通配符开头而 p2 以通配符结尾，则使用 p1 通配符吃掉所有 p2 直到它的最后一个通配符，然后使用 p2 通配符吃掉所有 p1
• 如果 p1 以通配符开头和结尾，则使用其起始通配符吃掉 p2 直到它的第一个通配符，然后使用 p2 通配符吃掉 p1 到它的最后一个通配符，然后使用最后一个 p1 通配符吃掉剩下的p2

否则，一个字符串 (p1) 没有通配符，而另一个字符串 (p2) 有字符串 s1,s2,... 用通配符标点。因此，只需搜索 p1 中第一次出现的 s1，然后搜索第一次出现的 s2（从 p1 中匹配的结尾开始），等等。如果找到所有字符串，则模式匹配，否则不匹配不。

Answer 4

据我了解，您尝试确定一个正则表达式是否与另一个正则表达式正交？如果是这样，这不是一个非常重要的问题。

这是有关理论的更多信息。

这是解决方案：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 5

这是 sepp2k 建议的算法的 c++ 实现，稍作修改：

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