Comment dites-vous si deux jokers se chevauchent?

Question

Étant donné deux chaînes avec * caractères génériques, je voudrais savoir si une chaîne pourrait être créée qui correspondrait à la fois.

Par exemple, ces deux sont un simple cas de chevauchement:

1. Bonjour * Monde
2. Hel *

Mais alors sont tous ces:

1. * .csv
2. rapports * .csv
3. reportsdump.csv

Existe-t-il un algorithme publié pour cela? Ou peut-être une fonction utilitaire dans Windows ou une bibliothèque que je pourrais être en mesure d'appeler ou de copier?

Answer 1

Puisque chaque glob peut être écrit comme une expression régulière et que l'intersection de deux expressions régulières peut être trouvée (à moins qu'elles ne soient pas vraiment régulières, mais elles seraient dans ce cas), vous pouvez trouver l'intersection de deux globes en les transformant en expressions régulières et en trouvant l'intersection de celles-ci. Vous pouvez donc déterminer si deux globules se croisent en recherchant l'intersection des expressions régulières et en vérifiant si elles sont vides.

Cependant depuis globs sont plus limitées que l'expression régulière, il y a une beaucoup plus facile:

Appelons les deux petites boules g1 et g2. Ils se croisent ssi

1. Les deux g1 et g2 sont vides ou contiennent uniquement des caractères génériques.
2. Ni g1 ni g2 sont vides et l'une des conditions suivantes est remplie (Soit c1 le premier caractère de g1 et t1 la chaîne contenant les caractères restants - même pour g2 avec c2 et t2):
   1. c1 et c2 sont égaux et t1 et t2 se coupent
   2. c1 et/ou c2 est un caractère générique et t1 croise g2
   3. c1 et/ou c2 est un caractère générique et g1 intersection avec t2

Un exemple d'implémentation dans 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 

Cet algorithme n'est pas particulièrement efficace si les globs contiennent beaucoup de jokers, mais il est très facile à mettre en œuvre et que vous envisagez probablement l'utiliser avec les noms de fichiers, je doute que vous aurez plus de 1000 globs globs.

Answer 2

Pour ce que ça vaut la peine, voici une mise en œuvre de l'algorithme de la réponse de sepp2k en C# (j'ai utilisé explicitement return true; et return false; appels, ainsi que les commentaires, pour une meilleure lisibilité de l'algorithme):

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

Comme je comprends vous essayez de déterminer si une regex est orthogonale à une autre regex? Si oui, ce n'est pas un problème trivial.

Voici plus sur Theory.

Voici la solution: Java library.

Utilisation:

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

Voici un C++ implémentation de l'algorithme proposé par sepp2k avec de légères modifications:

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