Jak określić, czy dwa symbole wieloznaczne zachodzą na siebie?

Question

Biorąc pod uwagę dwa ciągi znaków z * symbolami wieloznacznymi, chciałbym wiedzieć, czy można utworzyć ciąg znaków pasujący do obu.

Na przykład, te dwa są prostym przypadku nakładania:

1. Witam * Świat
2. Hel *

Ale tak to wszystko z nich:

1. * .csv
2. raportów * .csv
3. reportsdump.csv

Czy opublikowano algorytm? A może funkcja użyteczna w systemie Windows lub bibliotece, którą mógłbym wywołać lub skopiować?

Answer 1

Ponieważ każdy glob może być zapisany jako wyrażenie regularne i można znaleźć przecięcie dwóch wyrażeń regularnych (o ile nie są one naprawdę regularne, ale w tym przypadku są), można znaleźć przecięcie dwóch globów przekształcając je w wyrażenia regularne, a następnie znajdując ich przecięcie. Możesz więc sprawdzić, czy dwa globsy przecinają się, znajdując przecięcie wyrażeń regularnych i sprawdzając, czy są puste.

Jednak ponieważ globs są bardziej ograniczone niż wyrażenie regularne, istnieje znacznie łatwiejszy sposób:

Nazwijmy G1 i G2 dwa Globs. Przecinają się między sobą, co oznacza, że:

1. Zarówno g1, jak i g2 są puste lub zawierają tylko symbole wieloznaczne.
2. Ani G1 ani G2 są puste i jeden z następujących warunków jest spełniony (niech c1 być pierwszym znakiem G1 i t1 ciąg zawierający pozostałe znaki - takie same dla g2 z C2 i t2):
   1. c1 i C2 są równe i T1 i T2 przecinają
   2. C1 i/lub C2 jest wieloznaczny t1 przecina g2
   3. C1 i/lub C2 jest wieloznaczne i G1 przecina t2

Przykładem wdrożenia w 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 

Algorytm ten nie jest szczególnie skuteczne, jeżeli globs zawierają wiele symboli wieloznacznych, ale to jest bardzo łatwe do wykonania, a ponieważ jesteś prawdopodobnie planuje użyć ich nazw, I wątpię, że będziesz mieć kulki dłuższe niż 1000 znaków.

Answer 2

Na co warto, oto jeden implementacja algorytmu z odpowiedzią sepp2k w C# (użyłem wyraźne return true; i return false; połączeń, wraz z uwagami, dla algorytmu czytelności):

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

Jak rozumiem próbujesz ustalić, czy wyrażenie regularne jest ortogonalne względem innego wyrażenia regularnego? Jeśli tak, to nie jest banalny problem.

Oto więcej o Theory.

Oto rozwiązanie: Java library.

Zastosowanie:

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

Oto C++ implementacja algorytmu sugeruje sepp2k z niewielkimi modyfikacjami:

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