¿Cómo se puede saber si dos comodines se superponen?

Question

Dadas dos cadenas con * comodines, me gustaría saber si se podría crear una cadena que coincida con ambas.

Por ejemplo, estos dos son un simple caso de solapamiento:

1. Hola * Mundial
2. Hel *

pero también lo son todos ellos:

1. * .csv
2. informes * .csv
3. reportsdump.csv

¿Hay un algoritmo publicado para hacer esto? ¿O tal vez una función de utilidad en Windows o en una biblioteca que pueda llamar o copiar?

Answer 1

Dado que cada globo se puede escribir como una expresión regular y se puede encontrar la intersección de dos expresiones regulares (a menos que no sean realmente regulares, pero lo serían en este caso), puede encontrar la intersección de dos globos transformándolos en expresiones regulares y luego encontrando la intersección de esos. Para que pueda averiguar si dos globos se cruzan, encuentre la intersección de las expresiones regulares y verifique si está vacío.

Sin embargo, desde globos son más limitadas que la expresión regular, hay una manera mucho más fácil:

Vamos a llamar a la G1 y G2 dos globos. Se cruzan iff

1. Tanto g1 como g2 están vacíos o solo contienen comodines.
2. Ni G1 ni g2 están vacías y una de las siguientes condiciones es verdadera (vamos a c1 en el primer carácter del G1 y T1, la cadena que contiene los caracteres restantes - mismo para g2 con C2 y T2):
   1. c1 y c2 son iguales y t1 y t2 se cruzan
   2. c1 y/o c2 es un comodín y t1 se cruza con g2
   3. c1 y/o c2 es un comodín y g1 cruza con t2

un ejemplo de implementación en 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 

Este algoritmo no es especialmente eficiente si los globos contienen una gran cantidad de comodines, pero es muy fácil de implementar y puesto que es muy probable que planean usar esto con los nombres de archivo, me duda que tendrá globos de más de 1000 caracteres.

Answer 2

Por lo que vale la pena, aquí está uno implementación del algoritmo de respuesta de sepp2k en C# (I utiliza explícitas return true; y return false; llamadas, junto con los comentarios, para facilitar la lectura algoritmo):

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

Según entiendo Intentas determinar si una expresión regular es ortogonal a otra expresión regular? Si es así, este no es un problema trivial.

aquí es más sobre Theory.

Aquí es solución: Java library.

Uso:

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

Aquí es una C++ implementación del algoritmo sugerido por sepp2k con unas ligeras modificaciones:

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