Rekursive Lösungen für Glob-Muster-Matching

Question

Ich untersuche derzeit Implementierungen von UNIX-Stil-Glob-Pattern-Matching. Im Allgemeinen ist die Bibliothek fnmatch eine gute Referenzimplementierung für diese Funktionalität.

Blick auf einige der the implementations, sowie das Lesen verschiedener Blogs/Tutorials zu diesem Thema, scheint es, dass dieser Algorithmus in der Regel rekursiv implementiert wird.

Im Allgemeinen eignet sich jede Art von Algorithmus, der "Rückverfolgung" erfordert oder zu einem früheren Zustand zurückkehren muss, für eine rekursive Lösung. Dazu gehören Dinge wie das Traversieren von Bäumen oder das Parsen verschachtelter Strukturen.

Aber ich habe Probleme zu verstehen, warum Glob Pattern-Matching insbesondere rekursiv so oft implementiert wird. Ich bekomme die Idee, die manchmal zurück Tracking notwendig sein wird, zum Beispiel, wenn wir einen String aabaabxbaab haben, und ein Muster a*baab, die Zeichen nach dem * wird die erste „baab“ String übereinstimmt, wie aa(baab)xbaab und dann scheitern übereinstimmen der Rest der Zeichenfolge. Also muss der Algorithmus Backtrack, so dass der Zeichenübereinstimmungszähler neu beginnt, und wir können das zweite Auftreten von baab, wie zum Beispiel: aabaabx(baab).

Okay, aber im Allgemeinen Rekursion wird verwendet, wenn wir mehrere verschachtelte Ebenen von Backtracking benötigen, und ich sehe nicht, wie das in diesem Fall notwendig wäre. Es scheint, als müssten wir immer nur eine Ebene nach der anderen zurückverfolgen, wenn der Iterator über dem Muster und der Iterator über die Eingabezeichenfolge nicht übereinstimmen. An diesem Punkt müsste der Iterator über das Muster zum letzten "Sicherungspunkt" zurückgehen, der entweder der Anfang der Zeichenfolge oder der letzte * ist, der erfolgreich auf etwas zutrifft. Dies erfordert keinen Stack - nur einen einzigen Speicherpunkt.

Die einzige Komplikation, an die ich denken kann, ist im Falle einer "überlappenden" Übereinstimmung. Wenn wir beispielsweise die Eingabezeichenfolge aabaabaab und das Muster a*baab hätten, würden wir nicht übereinstimmen, da das "b" in der letzten baab Teil der ersten oder der zweiten Übereinstimmung sein könnte. Aber es scheint, dass dies gelöst werden könnte, indem einfach der Eingangsiterator zurückverfolgt wird, wenn der Abstand zwischen dem letzten Musteriterator-Sicherungspunkt und dem Ende des Musters größer ist als der Abstand zwischen der Eingabe-Iteratorposition und dem Ende der Eingabezeichenkette.

Also, soweit ich sehe, sollte es nicht zu viel ein Problem sein, diesen Glob-Matching-Algorithmus iterativ zu implementieren (unter der Annahme eines sehr einfachen Glob Matcher, der nur das * Zeichen verwendet, um "Null übereinstimmen . oder mehr Zeichen“auch wäre die passende Strategie gierig)

also, ich nehme an, ich über diese definitiv falsch bin, weil alle anderen diese rekursiv tut -. so muss ich etwas fehlt werden. Es ist nur so, dass ich nicht sehen kann, was ich hier vermisse. Also habe ich einen einfachen Glob Matcher in C++ implementiert (der nur den Operator * unterstützt), um zu sehen, ob ich herausfinden könnte, was ich vermisse. Dies ist eine äußerst einfache, einfache iterative Lösung, die nur eine innere Schleife verwendet, um den Wildcard-Abgleich durchzuführen.Es erfasst auch die Indizes, die die * Zeichen in einem Vektor von Paaren entspricht:

bool match_pattern(const std::string& pattern, const std::string& input, 
    std::vector<std::pair<std::size_t, std::size_t>>& matches) 
{ 
    const char wildcard = '*'; 

    auto pat = std::begin(pattern); 
    auto pat_end = std::end(pattern); 

    auto it = std::begin(input); 
    auto end = std::end(input); 

    while (it != end && pat != pat_end) 
    { 
     const char c = *pat; 
     if (*it == c) 
     { 
      ++it; 
      ++pat; 
     } 
     else if (c == wildcard) 
     { 
      matches.push_back(std::make_pair(std::distance(std::begin(input), it), 0)); 
      ++pat; 
      if (pat == pat_end) 
      { 
       matches.back().second = input.size(); 
       return true; 
      } 

      auto save = pat; 
      std::size_t matched_chars = 0; 

      while (it != end && pat != pat_end) 
      { 
       if (*it == *pat) 
       { 
        ++it; 
        ++pat; 
        ++matched_chars; 

        if (pat == pat_end && it != end) 
        { 
         pat = save; 
         matched_chars = 0; 

         // Check for an overlap and back up the input iterator if necessary 
         // 
         std::size_t d1 = std::distance(it, end); 
         std::size_t d2 = std::distance(pat, pat_end); 
         if (d2 > d1) it -= (d2 - d1); 
        } 
       } 
       else if (*pat == wildcard) 
       { 
        break; 
       } 
       else 
       { 
        if (pat == save) ++it; 
        pat = save; 
        matched_chars = 0; 
       } 
      } 

      matches.back().second = std::distance(std::begin(input), it) - matched_chars; 
     } 
     else break; 
    } 

    return it == end && pat == pat_end; 
} 

Dann habe ich eine Reihe von Tests geschrieben, um zu sehen, ob ich etwas Muster oder Eingabestring finden könnte, die mehrere Ebenen der Rückzieher erfordern würde (und also Rekursion oder ein Stack), aber ich kann mir nichts einfallen lassen.

Hier ist meine Testfunktion:

void test(const std::string& input, const std::string& pattern) 
{ 
    std::vector<std::pair<std::size_t, std::size_t>> matches; 
    bool result = match_pattern(pattern, input, matches); 
    auto match_iter = matches.begin(); 

    std::cout << "INPUT: " << input << std::endl; 
    std::cout << "PATTERN: " << pattern << std::endl; 
    std::cout << "INDICES: "; 
    for (auto& p : matches) 
    { 
     std::cout << "(" << p.first << "," << p.second << ") "; 
    } 
    std::cout << std::endl; 

    if (result) 
    { 
     std::cout << "MATCH: "; 

     for (std::size_t idx = 0; idx < input.size(); ++idx) 
     { 
      if (match_iter != matches.end()) 
      { 
       if (idx == match_iter->first) std::cout << '('; 
       else if (idx == match_iter->second) 
       { 
        std::cout << ')'; 
        ++match_iter; 
       } 
      } 

      std::cout << input[idx]; 
     } 

     if (!matches.empty() && matches.back().second == input.size()) std::cout << ")"; 

     std::cout << std::endl; 
    } 
    else 
    { 
     std::cout << "NO MATCH!" << std::endl; 
    } 

    std::cout << std::endl; 
} 

Und meine eigentlichen Tests:

test("aabaabaab", "a*b*ab"); 
test("aabaabaab", "a*"); 
test("aabaabaab", "aa*"); 
test("aabaabaab", "aaba*"); 
test("/foo/bar/baz/xlig/fig/blig", "/foo/*/blig"); 
test("/foo/bar/baz/blig/fig/blig", "/foo/*/blig"); 
test("abcdd", "*d"); 
test("abcdd", "*d*"); 
test("aabaabqqbaab", "a*baab"); 
test("aabaabaab", "a*baab"); 

diese Ausgänge So:

INPUT: aabaabaab 
PATTERN: a*b*ab 
INDICES: (1,2) (3,7) 
MATCH: a(a)b(aaba)ab 

INPUT: aabaabaab 
PATTERN: a* 
INDICES: (1,9) 
MATCH: a(abaabaab) 

INPUT: aabaabaab 
PATTERN: aa* 
INDICES: (2,9) 
MATCH: aa(baabaab) 

INPUT: aabaabaab 
PATTERN: aaba* 
INDICES: (4,9) 
MATCH: aaba(abaab) 

INPUT: /foo/bar/baz/xlig/fig/blig 
PATTERN: /foo/*/blig 
INDICES: (5,21) 
MATCH: /foo/(bar/baz/xlig/fig)/blig 

INPUT: /foo/bar/baz/blig/fig/blig 
PATTERN: /foo/*/blig 
INDICES: (5,21) 
MATCH: /foo/(bar/baz/blig/fig)/blig 

INPUT: abcdd 
PATTERN: *d 
INDICES: (0,4) 
MATCH: (abcd)d 

INPUT: abcdd 
PATTERN: *d* 
INDICES: (0,3) (4,5) 
MATCH: (abc)d(d) 

INPUT: aabaabqqbaab 
PATTERN: a*baab 
INDICES: (1,8) 
MATCH: a(abaabqq)baab 

INPUT: aabaabaab 
PATTERN: a*baab 
INDICES: (1,5) 
MATCH: a(abaa)baab 

Die Klammern, die nach "MATCH: " zeigen in der Ausgabe erscheinen die Teilstrings, die von jedem * abgeglichen wurden Charakter. Also scheint das gut zu funktionieren, und ich kann nicht verstehen, warum es notwendig wäre, hier mehrere Ebenen zurück zu verfolgen - zumindest wenn wir unser Muster so begrenzen, dass nur * Zeichen erlaubt sind, und wir gehen von gieriger Übereinstimmung aus.

Also nehme ich an, dass ich definitiv falsch liege und wahrscheinlich etwas einfaches übersehe - kann mir jemand helfen, zu sehen, warum dieser Algorithmus mehrere Backtracking-Levels (und somit Rekursion oder einen Stack) benötigt?

Answer 1

Ich habe nicht alle Details Ihrer Implementierung überprüft, aber es ist sicherlich wahr, dass Sie die Übereinstimmung ohne rekursives Zurückverfolgen tun können.

Sie können Glob-Matching auch ohne Backtracking durchführen, indem Sie eine einfache endliche Maschine erstellen. Sie könnten den Glob in einen regulären Ausdruck übersetzen und ein DFA auf die übliche Weise erstellen, oder Sie könnten etwas verwenden, das dem Aho-Corasick-Gerät sehr ähnlich ist; Wenn Sie Ihren Algorithmus ein wenig optimiert haben, würden Sie das gleiche Ergebnis erzielen. (Der Schlüssel ist, dass Sie den Eingabescan nicht wirklich sichern müssen; Sie müssen nur den korrekten Scan-Status herausfinden, der vorausberechnet werden kann.)

Die klassischen fnmatch-Implementierungen sind nicht auf Geschwindigkeit optimiert; Sie basieren auf der Annahme, dass Muster und Zielzeichenfolgen kurz sind. Diese Annahme ist normalerweise vernünftig, aber wenn Sie nicht vertrauenswürdige Muster zulassen, öffnen Sie sich selbst für einen DoS-Angriff. Und basierend auf dieser Annahme ist ein Algorithmus ähnlich dem, den Sie präsentieren, der keine Vorberechnung erfordert, wahrscheinlich in der überwiegenden Mehrheit der Anwendungsfälle schneller als jeder Algorithmus, der eine Vorberechnung von Zustandsübergangstabellen erfordert, während der exponentielle Anstieg mit pathologischen Mustern vermieden wird.