Come si capisce se due caratteri jolly si sovrappongono?

Question

Dato due stringhe con * caratteri jolly, vorrei sapere se è possibile creare una stringa che corrisponda a entrambe.

Per esempio, questi due sono un semplice caso di sovrapposizione:

1. Ciao * Mondiale
2. Hel *

ma lo sono anche tutti questi:

1. * .csv
2. segnalazioni * .csv
3. reportsdump.csv

Esiste un algoritmo pubblicato per fare ciò? O forse una funzione di utilità in Windows o in una libreria che potrei essere in grado di chiamare o copiare?

Answer 1

Poiché ogni glob può essere scritto come un'espressione regolare e l'intersezione di due espressioni regolari può essere trovata (a meno che non siano realmente regolari, ma in questo caso si tratterebbe di), è possibile trovare l'intersezione di due globi trasformandoli in espressioni regolari e quindi trovandone l'intersezione. Quindi puoi scoprire se due globi si intersecano trovando l'intersezione delle espressioni regolari e controllando se è vuoto.

Tuttavia, poiché gocce sono più limitati rispetto espressioni regolari, c'è un modo molto facile:

Chiamiamo il g1 due gocce e g2. Si intersecano iff

1. Entrambi g1 e g2 sono vuoti o contengono solo caratteri jolly.
2. Né g1 né g2 sono vuote e una delle seguenti condizioni (diciamo c1 essere il primo carattere di g1 e t1 la stringa contenente i caratteri rimanenti - stesso per g2 con c2 e t2):
   1. c1 e c2 sono uguali e t1 e t2 intersecano
   2. c1 e/o c2 è un carattere jolly e t1 interseca con g2
   3. c1 e/o C2 è un carattere jolly e g1 interseca con t2

Un esempio di implementazione in 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 

Questo algoritmo non è particolare efficiente se le gocce contengono un sacco di caratteri jolly, ma è molto facile da implementare e da allora è molto probabile intenzione di usare questo con i nomi dei file, ho dubito che avrai globi più lunghi di 1000 caratteri.

Answer 2

Per quello che vale, ecco uno implementazione dell'algoritmo dalla risposta di sepp2k in C# (io ho usato esplicite return true; e return false; chiamate, insieme ai commenti, per l'algoritmo leggibilità):

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

quanto ho capito si tenta di determinare se una regex è ortogonale a un'altra espressione regolare? Se è così, questo non è un problema banale.

Qui è più su Theory.

Ecco la soluzione: Java library.

Usage:

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

Ecco un C++ implementazione dell'algoritmo suggerito da sepp2k con lievi modifiche:

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