c++ - 全局模式匹配的递归解决方案

Question

我目前正在研究 UNIX 风格的 glob 模式匹配的实现。一般来说， fnmatch 库是此功能的一个很好的引用实现。

看着一些the implementations ，以及阅读有关此的各种博客/教程，似乎该算法通常是递归实现的。

通常，任何需要“回溯”或需要返回到较早状态的算法都非常适合递归解决方案。这包括诸如树遍历或解析嵌套结构之类的事情。

但是我无法理解为什么特别是 glob 模式匹配经常以递归方式实现。我的想法是有时需要回溯，例如，如果我们有一个字符串 aabaabxbaab , 和一个图案 a*baab , * 后面的字符将匹配第一个“baab”子串，如 aa(baab)xbaab ，然后无法匹配字符串的其余部分。所以算法需要回溯以便字符匹配计数器重新开始，我们可以匹配第二次出现的 baab ，如:aabaabx(baab) .

好的，但是当我们可能需要多个嵌套级别的回溯时，通常会使用递归，我不认为在这种情况下这是必要的。当模式上的迭代器和输入字符串上的迭代器无法匹配时，似乎我们一次只需要回溯一个级别。此时，模式上的迭代器需要移回最后一个“保存点”，它可能是字符串的开头，或者是最后一个 *成功匹配的东西。这不需要堆栈 - 只需一个保存点。

我能想到的唯一复杂情况是出现“重叠”匹配。例如，如果我们有输入字符串 aabaabaab , 和图案 a*baab ，我们将无法匹配，因为最后 baab 中的“b”可以是第一场比赛或第二场比赛的一部分。但是，如果最后一个模式迭代器保存点与模式末尾之间的距离大于输入迭代器位置与输入字符串末尾之间的距离，那么这似乎可以通过简单地回溯输入迭代器来解决。

所以，就我所见，迭代实现这个 glob 匹配算法应该不是什么大问题(假设一个非常简单的 glob 匹配器，它只使用 * 字符来表示“匹配零个或多个字符”。此外，匹配策略将是贪婪的。)

所以，我认为我对此肯定是错的，因为其他人都是递归地这样做 - 所以我一定错过了一些东西。只是我看不到我在这里遗漏了什么。所以我在 C++ 中实现了一个简单的 glob 匹配器(只支持 * 运算符)，看看我是否能找出我遗漏了什么。这是一个非常直接、简单的迭代解决方案，它只使用一个内部循环来进行通配符匹配。它还记录了* 的索引。成对 vector 中的字符匹配:

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

然后我写了一系列测试，看看我是否能找到一些需要多级回溯(因此递归或堆栈)的模式或输入字符串，但我似乎无法想出任何东西。

这是我的测试功能:

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

我的实际测试:

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

所以这输出:

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

出现在输出中 "MATCH: " 之后的括号显示每个 * 匹配/消耗的子字符串特点。所以，这似乎工作正常，我似乎无法理解为什么有必要在这里回溯多个级别 - 至少如果我们限制我们的模式只允许 *字符，我们假设贪婪匹配。

所以我认为我对此肯定是错误的，并且可能忽略了一些简单的事情 - 有人可以帮我看看为什么这个算法可能需要多级回溯(因此需要递归或堆栈)？

Answer 1

我没有检查你的实现的所有细节，但你可以在没有递归回溯的情况下进行匹配。

通过构建一个简单的有限状态机，您实际上可以在完全不回溯的情况下进行全局匹配。您可以将 glob 转换为正则表达式并以正常方式构建 DFA，或者您可以使用与 Aho-Corasick 机器非常相似的东西；如果你稍微调整一下你的算法，你会得到同样的结果。 (关键是您实际上不需要备份输入扫描；您只需要找出正确的扫描状态，这可以预先计算。)

经典的 fnmatch 实现没有针对速度进行优化；它们基于模式和目标字符串很短的假设。这种假设通常是合理的，但如果您允许不受信任的模式，您就会面临 DoS 攻击。并且基于该假设，类似于您提出的算法，不需要预先计算，在绝大多数用例中可能比任何需要预先计算状态转换表同时避免病理模式指数爆炸的算法更快。