用于glob模式匹配的递归解决方案

Question

我目前正在研究UNIX风格的glob模式匹配的实现.通常,fnmatch库是此功能的良好参考实现.

看一些实现,以及阅读关于此的各种博客/教程,似乎这个算法通常是递归实现的.

通常,任何需要"反向跟踪"或需要返回到早期状态的算法都很适合递归解决方案.这包括树遍历或解析嵌套结构等内容.

但是我很难理解为什么特别是通常以递归方式实现glob模式匹配.我认为有时需要回溯跟踪,例如,如果我们有一个字符串aabaabxbaab和一个模式a*baab,那么*将匹配第一个"baab"子字符串之后的字符aa(baab)xbaab,然后就不能匹配字符串的其余部分.因此算法需要回溯以便字符匹配计数器重新开始,我们可以匹配第二次出现baab,如:aabaabx(baab).

好的,但是当我们可能需要多个嵌套级别的回溯时,通常使用递归,我不知道在这种情况下如何需要这样做.看起来我们只需要一次回溯一个级别,当模式上的迭代器和输入字符串上的迭代器不匹配时.此时,模式上的迭代器需要移回到最后一个"保存点",它可以是字符串的开头,也可以是*成功匹配的最后一个.这不需要堆栈 - 只需一个保存点.

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

因此,就我所见,迭代地实现这种全局匹配算法应该不是太大的问题(假设一个非常简单的glob匹配器,它只使用该*字符来表示"匹配零个或多个字符").此外,匹配策略将是贪婪的.)

所以,我认为我对此肯定是错的,因为其他人都是递归地做到这一点 - 所以我必须遗漏一些东西.只是我看不到我在这里失踪的东西.所以我在C++中实现了一个简单的glob匹配器(只支持*运算符),看看我是否能找出我所缺少的东西.这是一个非常简单,简单的迭代解决方案,它只使用内部循环来进行通配符匹配.它还记录*字符在对向量中匹配的索引:

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 攻击。基于这一假设，与您提出的算法类似的不需要预先计算的算法在绝大多数用例中可能比任何需要预先计算状态转换表的算法更快，同时避免病态模式的指数爆炸。