Rozwiązania rekursywne do dopasowywania wzorców globalnych

Question

Obecnie studiuję implementacje dopasowywania wzorców globalnych w stylu UNIX. Ogólnie rzecz biorąc, biblioteka fnmatch jest dobrą implementacją odniesienia dla tej funkcji.

Patrząc na niektóre z the implementations, a także czytając różne blogi/tutoriale na ten temat, wydaje się, że ten algorytm jest zwykle realizowany rekursywnie.

Ogólnie rzecz biorąc, dowolny algorytm, który wymaga "śledzenia wstecznego" lub wymaga powrotu do wcześniejszego stanu, dobrze nadaje się do rozwiązania rekurencyjnego. Obejmuje to takie operacje, jak przewijanie drzewa lub analizowanie struktur zagnieżdżonych.

Ale mam problem ze zrozumieniem, dlaczego w ogóle dopasowywanie wzorców globalnych jest tak często wdrażane rekursywnie. Wpadłem na pomysł, że czasami konieczne będzie śledzenie wstecz, na przykład jeśli mamy ciąg znaków aabaabxbaab i wzorzec a*baab, znaki po numerze * będą pasować do pierwszego podciągu "baab", np. aa(baab)xbaab, a następnie , aby zakończyć się niepowodzeniem reszta struny. Tak więc algorytm będzie musiał cofnąć, aby licznik dopasowań znaków zaczął się od nowa i możemy dopasować drugie wystąpienie baab, takie jak: aabaabx(baab).

Okay, ale ogólnie rekursja jest używana, gdy możemy wymagać wielu zagnieżdżonych poziomów cofania, i nie widzę, jak byłoby to konieczne w tym przypadku. Wygląda na to, że musielibyśmy tylko cofnąć się o jeden poziom za każdym razem, gdy iterator nad wzorzec i iteratorem nad ciągiem wejściowym nie pasuje do siebie. W tym momencie iterator nad wzorcem musiałby powrócić do ostatniego "punktu zapisu", który byłby albo początkiem łańcucha, albo ostatnim *, który pomyślnie dopasował coś. To nie wymaga stosu - tylko jeden punkt zapisu.

Jedyną komplikacją, jaką mogę wymyślić, jest przypadek "pokrywającego się" meczu. Na przykład, jeśli mamy ciąg wejściowy aabaabaab i wzorzec a*baab, nie uda nam się dopasować, ponieważ "b" w ostatnim baab może być częścią pierwszego dopasowania lub drugiego dopasowania. Ale wydaje się, że można to rozwiązać, po prostu przechodząc wstecz do iteratora wejściowego, jeśli odległość między ostatnim punktem zapisu iteratora wzorca a końcem wzorca jest większa niż odległość między pozycją iteratora wejściowego a końcem ciągu wejściowego.

Tak więc, o ile widzę, nie powinno być zbyt wielkim problemem, aby iteracyjnie zaimplementować algorytm dopasowywania globalnego (zakładając bardzo prosty glob matcher, który używa tylko znaku *, aby określić "dopasowanie zero" . lub więcej znaków”Ponadto, strategia dopasowywania będzie chciwy)

więc zakładam, że jestem zdecydowanie źle o tym, ponieważ wszyscy inni to rekurencyjnie. - więc musi być brakuje czegoś. Po prostu nie widzę, czego tu brakuje. Więc zaimplementowałem prosty glob matcher w C++ (który obsługuje tylko operatora *), aby sprawdzić, czy mogę dowiedzieć się, czego mi brakuje. Jest to niezwykle proste, proste rozwiązanie iteracyjne, które po prostu wykorzystuje wewnętrzną pętlę do dopasowania wieloznacznego.Zapisuje się tutaj również indeksy który dopasowuje znak * w wektorze par:

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

Potem napisał serię testów w celu sprawdzenia, czy udało mi się znaleźć jakiś ciąg wzoru lub wejściowego, które wymagają wielu poziomów wycofywania (i w związku z tym rekursja lub stos), ale nie mogę niczego wymyślić.

Oto moja funkcja testu:

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

A moje rzeczywiste testy:

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"); 

Więc wyjść:

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 

Nawiasy, które pojawiają się na wyjściu po "MATCH: " koncert podciągi, które zostały dopasowane/zużyte przez każdy z nich postać. Wygląda więc na to, że działa dobrze i nie mogę się zorientować, dlaczego konieczne jest tutaj backtrack wielu poziomów - przynajmniej jeśli ograniczymy nasz wzór, aby pozwolić tylko na znaki *, i zakładamy chciwe dopasowanie.

Zakładam więc, że zdecydowanie się mylę i prawdopodobnie przeoczę coś prostego - czy ktoś może mi pomóc zrozumieć, dlaczego ten algorytm może wymagać wielu poziomów cofania (a więc rekursji lub stosu)?

Answer 1

Nie sprawdziłem wszystkich szczegółów dotyczących twojej implementacji, ale z pewnością prawdą jest, że możesz to zrobić bez rekursywnego cofania.

Rzeczywiście można dopasować globalnie bez backtrackingu, budując prostą maszynę o skończonym stanie. Możesz przetłumaczyć glob w wyrażeniu regularnym i zbudować DFA w normalny sposób, lub możesz użyć czegoś bardzo podobnego do maszyny Aho-Corasick; jeśli trochę zmodyfikowałeś swój algorytm, osiągnąłbyś ten sam rezultat. (Kluczem jest to, że w rzeczywistości nie trzeba wykonywać kopii zapasowej skanowania wejściowego, wystarczy określić prawidłowy stan skanowania, który można wstępnie wykryć.)

Klasyczne implementacje fnmatch nie są zoptymalizowane pod kątem szybkości; opierają się na założeniu, że wzorce i ciągi celów są krótkie. Założenie to jest zwykle uzasadnione, ale jeśli dopuszczasz niezaufane wzorce, otwierasz się na atak DoS. I w oparciu o to założenie, algorytm podobny do tego, który prezentujesz, który nie wymaga wstępnego obliczenia, jest prawdopodobnie szybszy w większości przypadków użycia niż jakikolwiek algorytm, który wymaga wstępnych obliczeń tabel stanów, unikając eksponencjalnego wybuchu z patologicznymi wzorami.