String matching where one string contains wildcard characters



  • Hi,

    keine algorithmen frage:
    Given two strings where first string may contain wild card characters and second string is a normal string. Write a function that returns true if the two strings match. The following are allowed wild card characters in first string.

    * --> Matches with 0 or more instances of any character or set of characters.
    ? --> Matches with any one character.

    testcases:

    assert(compare("g*ks", "geeks")); // Yes
    assert(compare("ge?ks*", "geeksforgeeks")); // Yes
    assert(compare("g*k", "gee"));  // No because 'k' is not in second
    assert(compare("*pqrs", "pqrst")); // No because 't' is not in first
    assert(compare("abc*bcd", "abcdhghgbcd")); // Yes
    assert(compare("abc*c?d", "abcd")); // No because second must have 2 instances of 'c'
    assert(compare("*c*d", "abcd")); // Yes
    assert(compare("*?c*d", "abcd")); // Yes
    

    hier mein code:

    bool compare(string filename, string wild) {
    	enum match { match_full, match_once, match_any };
    	match m = match_full;
    
    	int i = 0;
    	int j = 0;
    	int stored_j = 0;
    
    	while(i < filename.size()) {
    		if (j > (filename.size() - 1)) {
    			return false;
    		}
    
    		// Matches any single character of filename.
    		if(wild[j] == '?') {
    			m = match_once;
    		}
    		// Matches with 0 or more characters of filename.
    		else if(wild[j] == '*') {
    			m = match_any;
    			j++;
    			stored_j = j;
    		}
    
    		switch(m) {
    			case match_once:
    				i++; 
    				j++;
    				m = match_full;
    				continue;
    			case match_any:
    				i++;
    				if (filename[i] != wild[j]) {
    					continue;
    				} else {
    					m = match_full;
    				}
    			case match_full:
    				if(filename[i] == wild[j]) {
    					i++;
    					j++;
    				} else {
    					j = stored_j;
    				}
    		}
    	}
    
    	if(j == wild.size()) {
    		return true;
    	}
    	return false;
    }
    

    kann man meinen algo irgendwie fixen, verschoenern?



  • Algoman1 schrieb:

    verschoenern?

    Statt m lioeber mehr Bedeutung in die Position im Code legen.

    Algoman1 schrieb:

    fixen

    Bin jetzt nicht sicher, aber
    compare("?cd", "abcd")
    schreckt mich. Der erste * soll wie weit matchen? *="" oder *="a" oder *="ab"? Kann man vorher nicht wissen! Danach kommt auf jeden Fall der COde, der das ? matcht. Und danach erst beim c="c" kanns Ergebnis gefunden werden, viel zu spät, um noch was am * retten zu können.
    Die naheliegende Lösung wäre, für einen * alle Möglichkeiten durchzuprobieren und den Rest rekursiv matchen zu lassen.


  • Mod

    volkard schrieb:

    Algoman1 schrieb:

    verschoenern?

    Statt m lioeber mehr Bedeutung in die Position im Code legen.

    Algoman1 schrieb:

    fixen

    Bin jetzt nicht sicher, aber
    compare("?cd", "abcd")
    schreckt mich. Der erste * soll wie weit matchen? *="" oder *="a" oder *="ab"? Kann man vorher nicht wissen! Danach kommt auf jeden Fall der COde, der das ? matcht. Und danach erst beim c="c" kanns Ergebnis gefunden werden, viel zu spät, um noch was am * retten zu können.

    Müsste sich durch Eleminierung des match_once-Falles lösen lassen, statt diesen zu speichern und im switch zu verarbeiten, kann man auch gleich beim ersten if alles richtig machen und match unverändert belassen.



  • Ich würd da ja Rekursion gegenwerfen. Kurz und dreckig:

    // C-Strings für einfache Rekursionsmöglichkeit. Ginge auch mit Iteratoren,
    // wäre aber mehr Boilerplate für wenig Vorteil.
    bool compare(char const *glob, char const *str) {
      if(*glob == '*') {
        do {
          if(compare(glob + 1, str)) {
            return true;
          }
        } while(*str++);
        return false;
      } else if(*glob == '?') {
        return *str != '\0' && compare(glob + 1, str + 1);
      } else if(*str != *glob) {
        return false;
      } else if(*str) {
        return compare(glob + 1, str + 1);
      }
    
      return true;
    }
    
    // Für Kosmetik.
    bool compare(std::string const &wildcard, std::string const &filename) {
      return compare(wildcard.c_str(), filename.c_str());
    }
    

    Da ist jetzt bestimmt noch Verschönerungspotential drin -- insbesondere ist es unter bestimmten Umständen extrem unperformant, also sollte man keine Romane dagegenwerfen und von speziell für Unhandhabbarkeit gecrafteten Wildcards Abstand nehmen (foo************************bar wird lang auszuwerten dauern) -- aber korrekt sein sollte es schonmal. Wenn du Anwender davon abhalten willst, sich selbst zu trollen, wäre mit

    bool compare(char const *glob, char const *str) {
      if(*glob == '*') {
        while(*glob == '*') {
          ++glob;
        }
    
        do {
          if(compare(glob, str)) {
            return true;
          }
        } while(*str++);
        return false;
      } else if(*glob == '?') {
        return *str != '\0' && compare(glob + 1, str + 1);
      } else if(*str != *glob) {
        return false;
      } else if(*str) {
        return compare(glob + 1, str + 1);
      }
    
      return true;
    }
    

    schon großes Gefahrenpotential entfernt, aber letztendlich hast du das Problem potentiell bei allem, was mehrere * beinhaltet. ?f?o*?o*?b*?a*?r*? performant zu matchen, erfordert mehr Magie.

    Ansonsten: Auf welcher Plattform bist du unterwegs? In der glibc gibt es eine Funktion glob, die mehr Magie beinhaltet. Vielleicht ist das für dich ein gangbarer Weg. Unter Windows gibt es eine Funktion PathMatchSpec, die ähnliches zu tun scheint.



  • Vorschlag für eine O(n+m)-Lösung: Pattern an den "*" splitten, man erhält eine
    Liste von Pattern, die nur Buchstaben oder "?" enthalten. Dann sucht man den
    ersten Match des ersten Patterns (geht effizient z.B. mit KMP). Direkt dahinter
    sucht man dann den ersten Match des zweitern Patterns, usw. Am Schluss kann man
    das dann wieder zu einer Lösung zusammenfügen.



  • @O(n): dh. mein ansatz kann dem algo nicht loesen?



  • kann den algo mit folgenden ansatz loesen?
    http://en.wikipedia.org/wiki/Sequence_alignment



  • Nein, deiner scheitert schon an simplem String-Matching.
    filename: "abababc"
    wildcard: "ababc"


  • Mod

    Ist das hier korrekt? Macht mal jemand ein wenig stress testing?

    template <typename BidirectionalIterator, typename InputIterator>
    bool match_iter( BidirectionalIterator pat_first, BidirectionalIterator pat_last,
                     InputIterator match_first, InputIterator match_last )
    {
    	using namespace std;
    	// Ein paar triviale Fälle:
    	if (pat_first == pat_last)
    		return match_first == match_last;
    	if (match_first == match_last)
    		return find_if(pat_first, pat_last, [] (char c) {return c != '*';}) == pat_last;
    
    	auto pattern_slice = make_pair(pat_first, find(pat_first, pat_last, '*'));
    
    	auto find_match = [&]
    	{
    		return search( match_first, match_last, pattern_slice.first, pattern_slice.second,
    		               [] (char lhs, char rhs) {return lhs == '?' || rhs == '?' ?: lhs == rhs;} );
    	};
    
    	auto slice_pos = find_match();
    	if (slice_pos != match_first)
    		return false;
    
    	while(pattern_slice.second != pat_last)
    	{
    		match_first = match_first + (pattern_slice.second - pattern_slice.first);
    		if (match_first == match_last)
    			break;
    
    		pattern_slice = {pattern_slice.second+1, find(pattern_slice.second+1, pat_last, '*')};
    
    		slice_pos = find_match();
    		if (slice_pos == match_last)
    			return false;
    	};
    
    	return *std::prev(pat_last) == '*' || slice_pos == match_last - (pattern_slice.second - pattern_slice.first);
    }
    
    bool match( char const* str1, char const* str2 )
    {
    	return match_iter(str1, str1 + std::strlen(str1), str2, str2 + std::strlen(str2));
    }
    


  • assert(match("", "a"));
      assert(match("ac", "aab"));
    

    Warum triviale Fälle separat behandeln? Das macht den Code nur komplizierter und langsamer.


  • Mod

    O(n) schrieb:

    assert(match("", "a"));
      assert(match("ac", "aab"));
    

    Schlägt beides wie erwartet fehl.

    Warum triviale Fälle separat behandeln?

    Was meinst du?



  • Arcoth schrieb:

    O(n) schrieb:

    assert(match("", "a"));
      assert(match("ac", "aab"));
    

    Schlägt beides wie erwartet fehl.

    Sorry, sollte assert(match("ab", "aab")); heissen. Keines sollte fehlschlagen. Der Leerstring ist in jedem string enthalten.



  • O(n) schrieb:

    Arcoth schrieb:

    O(n) schrieb:

    assert(match("", "a"));
      assert(match("ac", "aab"));
    

    Schlägt beides wie erwartet fehl.

    Sorry, sollte assert(match("ab", "aab")); heissen. Keines sollte fehlschlagen. Der Leerstring ist in jedem string enthalten.

    match interpretiere ich hier abe rnicht als enthaltensein, sondern als von vorn bis hinten draufpassen.
    enthaltensein kannste dann mit

    assert(match("**", "a"));
    assert(match("*ab*", "aab"));
    

    testen.



  • @volkard: wie ist folgende wildcard zu verstehen: **



  • Algoman1 schrieb:

    @volkard: wie ist folgende wildcard zu verstehen: **

    Wenn ich schauen will, ob maske1 irgendwo in string1 enthalten ist, egal wo, dann kann ich ganz stur schauen, ob ""+maske1+"" und string1 matchen.

    So entstand aus der Maske "" die Maske "**".



  • wie ist folgende wildcard generell zu verstehen: **


  • Mod

    volkard schrieb:

    match interpretiere ich hier abe rnicht als enthaltensein, sondern als von vorn bis hinten draufpassen.
    enthaltensein kannste dann mit

    assert(match("**", "a"));
    assert(match("*ab*", "aab"));
    

    testen.

    Danke, genauso habe ich es mir gedacht. 👍

    Algoman1 schrieb:

    wie ist folgende wildcard generell zu verstehen: **

    Es ist äquivalent zu *.



  • Ich hab mir da nochmal ein bisschen Gedanken gemacht. Eine Menge Aufwand scheint zu entfallen, wenn man die Wildcard-Ausdrücke vorher in eine leichter zu verarbeitende Form bringt -- alle Sequenzen von * und ? am Stück lassen sich ja zusammendampfen; zum Beispiel ist ????* äquivalent zu ????*. Wenn man einen Wildcard-Ausdruck auf diese Weise "normalisiert" hat und sich darauf verlassen kann, dass nach einem * ein Buchstabe oder das Ende kommt, flutscht die Behandlung gleich deutlich besser. Ich denke mir das etwa so:

    #include <cassert>
    #include <cstring>
    #include <iostream>
    #include <string>
    
    std::string normalize_wildcard(std::string const &wildcard) {
      std::string result;
      bool pending_star = false;
    
      for(char c : wildcard) {
        switch(c) {
        case '?':
          result += '?';
          break;
        case '*':
          pending_star = true;
          break;
        default:
          if(pending_star) {
            result += '*';
            pending_star = false;
          }
          result += c;
        }
      }
    
      if(pending_star) {
        result += '*';
      }
    
      return result;
    }
    
    namespace impl {
      bool compare_aux(char const *glob, std::string const &str, std::size_t pos_str) {
        if(*glob == '*') {
          ++glob;
          // Erwarte normalisierten Wildcard-Ausdruck
          assert(*glob != '*' && *glob != '?');
    
          if(*glob == '\0') {
            return true;
          }
    
          char const *pattern_begin  = glob;
          std::size_t pattern_length = std::strcspn(glob, "*?");
    
          // Von hinten suchen für mehr average-case-Performanz.
          std::size_t pos_search     = std::string::npos;
    
          do {
            std::size_t pos_pattern = str.rfind(pattern_begin, pos_search, pattern_length);
    
            if(pos_pattern == std::string::npos || pos_pattern < pos_str) {
              return false;
            }
    
            if(compare_aux(glob + pattern_length, str, pos_pattern + pattern_length)) {
              return true;
            }
    
            pos_search = pos_pattern;
          } while(pos_search > pos_str);
    
          return false;
        } else if(*glob == '?') {
          return pos_str < str.size() && compare_aux(glob + 1, str, pos_str + 1);
        } else if(str.c_str()[pos_str] != *glob) {
          return false;
        } else if(pos_str < str.size()) {
          return compare_aux(glob + 1, str, pos_str + 1);
        }
    
        return true;
      }
    }
    
    bool compare(std::string const &wildcard, std::string const &filename) {
      return impl::compare_aux(normalize_wildcard(wildcard).c_str(), filename, 0);
    }
    
    int main() {
      assert(compare("g*ks", "geeks")); // Yes
      assert(compare("ge?ks*", "geeksforgeeks")); // Yes
      assert(!compare("g*k", "gee"));  // No because 'k' is not in second
      assert(!compare("*pqrs", "pqrst")); // No because 't' is not in first
      assert(compare("abc*bcd", "abcdhghgbcd")); // Yes
      assert(!compare("abc*c?d", "abcd")); // No because second must have 2 instances of 'c'
      assert(compare("*c*d", "abcd")); // Yes
      assert(compare("*?c*d", "abcd")); // Yes
    }
    

    Für Performance verlasse ich mich dann darauf, dass std::string::rfind vernünftig implementiert ist. Geprüft habe ich das nicht, aber wenn man deswegen in Performanceprobleme läuft, gibt es drölf Milliarden Bibliotheken, die man da draufwerfen könnte. Politur bleibt dem interessierten Leser als Übungsaufgabe überlassen.

    Auf Dateinamen könnte man das in der Form wahrscheinlich schon loslassen. Es lassen sich immer noch Fälle konstruieren, die ewig dauern (f*o*o*b*a*r*b*a*z*q*u*x* mit passenden Eingabedaten), aber das ist letztlich ein Problem, das man nicht vollständig los wird. Man könnte hier noch Dinge tun, aber langsam ist der Punkt erreicht, an dem ich dazu rate, bestehende Lösungen zu verwenden, anstatt eigene Dinge zusammenzuhacken. Die laufen dann meistens darauf hinaus, die Pattern vorher aufwändig in eine Form zu bringen, die hinterher Matching in bis zu linearer Zeit erlaubt (Backrefs sind ja hier nicht notwendig). Ich lass mal einen Link hier.



  • Mir fällt grad auf, dass ich mich da bei einigen Dingen verdacht habe (zu sehr an Regexes gedacht). Es ist ja bei diesem speziellen Subset egal, welchen Substring ein bestimmter Ausdruck matcht, und dann kann man sich die ganze Backtrackerei auch sparen. Asche, Haupt und so.




Anmelden zum Antworten