regex - 找出两个Glob模式(或正则表达式)的匹配项是否相交的算法

Question

我正在寻找与Redis KEYS command accepts类似的匹配的glob样式的模式。报价单:

• h?llo matches hello, hallo and hxllo
• h*llo matches hllo and heeeello
• h[ae]llo matches hello and hallo, but not hillo

但是，我不是根据文本字符串进行匹配，而是将模式与另一种模式进行匹配，并且所有运算符在两端都有意义。

例如，这些模式应在同一行中彼此匹配:

prefix*       prefix:extended*
*suffix       *:extended:suffix
left*right    left*middle*right
a*b*c         a*b*d*b*c
hello*        *ok
pre[ab]fix*   pre[bc]fix*

这些不应该匹配:

prefix*       wrong:prefix:*
*suffix       *suffix:wrong
left*right    right*middle*left
pre[ab]fix*   pre[xy]fix*
?*b*?         bcb

所以我想知道...

，如果可以的话(实现验证算法)，如果有的话？

如果不可能，那么正则表达式的哪些子集是可能的？ (即禁止*通配符？)

如果确实可行，什么是有效的算法？

需要多少时间？

编辑:已找到this other question on RegEx subset，但这与hello*和*ok匹配的单词不是彼此的子集/超集并不完全相同，但它们确实相交。

因此，从数学上讲，这可以表述为:是否可以确定性地检查一个模式匹配的单词集与另一个模式匹配的单词集相交是否导致非空集？

编辑:一位 friend @neizod绘制了此 knockout ，整洁地可视化了可能的解决方案/部分解决方案:Elimination rule

编辑:将为那些还可以提供工作代码(任何语言)和证明事实的测试用例提供额外的奖励。

编辑:添加了？* b *？ @DanielGimenez在评论中发现的测试用例。

Answer 1

现在见证这个全副武装和可操作战斗站的火力!

(我在这个答案上做得太多了，我的大脑坏了；应该有一个徽章。)

为了确定两个模式是否相交，我创建了一个递归的回溯解析器-遇到 Kleene star 时，会创建一个新堆栈，以便如果将来失败，则所有内容都会回滚，并且 star 会消耗下一个字符。

您可以查看此答案的历史记录，以确定如何得出所有结果以及为什么需要这样做，但是基本上，仅向前看一个标记就不足以确定一个交叉点，而这正是我之前所做的。

这是打破旧答案[abcd]d => *d的情况。 集合与星号之后的d相匹配，因此左侧仍将保留 token ，而右侧将是完整的。但是，这两种模式在ad，bd，cd和dd上相交，因此需要进行修复。我几乎是O(N)的答案被抛出了。

Lexer

词法化过程很简单，除了过程是转义字符并删除多余的星空之外。 token 分为集，星，野生字符(？)和字符。这与我以前的版本不同，在我以前的版本中，一个 token 是一个字符串而不是一个字符。随着越来越多的案例出现，使用字符串作为 token 更多的是障碍而不是优势。

解析器

解析器的大多数功能都很简单。给定左侧类型的开关调用一个函数，该函数是确定适当功能以将其与右侧类型进行比较的开关。比较的结果使两个开关冒泡到原始被调用方，通常是解析器的主循环。

解析星星

简单性以星级结尾。遇到这种情况时，它将接管一切。首先，它将对方的下一个 token 与对方的下一个 token 进行比较，将对方推进，直到找到匹配为止。

找到匹配项后，它将检查所有模式是否都匹配到两个模式的末尾。如果是这样，则图案相交。否则，它将从与之比较的原始 token 中移出另一方的下一个 token ，然后重复该过程。

当遇到两个任何时，则从彼此的下一个标记开始进入其自己的替代分支。

function intersects(left, right) {
    var lt, rt,
        result = new CompareResult(null, null, true);

    lt = (!left || left instanceof Token) ? left : tokenize(left);
    rt = (!right || right instanceof Token) ? right : tokenize(right);

    while (result.isGood && (lt || rt)) {
        result = tokensCompare(lt, rt);

        lt = result.leftNext;
        rt = result.rightNext;
    }

    return result;
}

function tokensCompare(lt, rt) {
    if (!lt && rt) return tokensCompare(rt, lt).swapTokens();

    switch (lt.type) {
        case TokenType.Char: return charCompare(lt, rt);
        case TokenType.Single: return singleCompare(lt, rt);
        case TokenType.Set: return setCompare(lt, rt);
        case TokenType.AnyString: return anyCompare(lt, rt);
    }
}

function anyCompare(tAny, tOther) {
    if (!tOther) return new CompareResult(tAny.next, null);

    var result = CompareResult.BadResult;

    while (tOther && !result.isGood) {
        while (tOther && !result.isGood) {
            switch (tOther.type) {
                case TokenType.Char: result = charCompare(tOther, tAny.next).swapTokens(); break;
                case TokenType.Single: result = singleCompare(tOther, tAny.next).swapTokens(); break;
                case TokenType.Set: result = setCompare(tOther, tAny.next).swapTokens(); break;
                case TokenType.AnyString:
                    // the anyCompare from the intersects will take over the processing.
                    result = intersects(tAny, tOther.next);
                    if (result.isGood) return result;
                    return intersects(tOther, tAny.next).swapTokens();
            }

            if (!result.isGood) tOther = tOther.next;
        }

        if (result.isGood) {
            // we've found a starting point, but now we want to make sure this will always work.
            result = intersects(result.leftNext, result.rightNext);
            if (!result.isGood) tOther = tOther.next;
        }
    }

    // If we never got a good result that means we've eaten everything.
    if (!result.isGood) result = new CompareResult(tAny.next, null, true);

    return result;
}

function charCompare(tChar, tOther) {
    if (!tOther) return CompareResult.BadResult;

    switch (tOther.type) {
        case TokenType.Char: return charCharCompare(tChar, tOther); 
        case TokenType.Single: return new CompareResult(tChar.next, tOther.next);
        case TokenType.Set: return setCharCompare(tOther, tChar).swapTokens(); 
        case TokenType.AnyString: return anyCompare(tOther, tChar).swapTokens();
    }
}

function singleCompare(tSingle, tOther) {
    if (!tOther) return CompareResult.BadResult;

    switch (tOther.type) {
        case TokenType.Char: return new CompareResult(tSingle.next, tOther.next);
        case TokenType.Single: return new CompareResult(tSingle.next, tOther.next);
        case TokenType.Set: return new CompareResult(tSingle.next, tOther.next);
        case TokenType.AnyString: return anyCompare(tOther, tSingle).swapTokens();
    }
}
function setCompare(tSet, tOther) {
    if (!tOther) return CompareResult.BadResult;

    switch (tOther.type) {
        case TokenType.Char: return setCharCompare(tSet, tOther);
        case TokenType.Single: return new CompareResult(tSet.next, tOther.next);
        case TokenType.Set: return setSetCompare(tSet, tOther);
        case TokenType.AnyString: return anyCompare(tOther, tSet).swapTokens();
    }
}

function anySingleCompare(tAny, tSingle) {
    var nextResult = (tAny.next) ? singleCompare(tSingle, tAny.next).swapTokens() :
        new CompareResult(tAny, tSingle.next);
    return (nextResult.isGood) ? nextResult: new CompareResult(tAny, tSingle.next);
}

function anyCharCompare(tAny, tChar) {
    var nextResult = (tAny.next) ? charCompare(tChar, tAny.next).swapTokens() :
        new CompareResult(tAny, tChar.next);

    return (nextResult.isGood) ? nextResult : new CompareResult(tAny, tChar.next);
}

function charCharCompare(litA, litB) {
    return (litA.val === litB.val) ?
        new CompareResult(litA.next, litB.next) : CompareResult.BadResult;
}

function setCharCompare(tSet, tChar) {
    return (tSet.val.indexOf(tChar.val) > -1) ?
        new CompareResult(tSet.next, tChar.next) : CompareResult.BadResult;
}

function setSetCompare(tSetA, tSetB) {
    var setA = tSetA.val,
        setB = tSetB.val;

    for (var i = 0, il = setA.length; i < il; i++) {
        if (setB.indexOf(setA.charAt(i)) > -1) return new CompareResult(tSetA.next, tSetB.next);
    }
    return CompareResult.BadResult;
}

jsFiddle

时间复杂度

其中包含单词“递归回溯”的任何值至少为O(N2)。

可维护性和可读性

我故意用单个开关将所有分支分解成自己的功能。当一个字符串就足够时，我通常使用命名常量。这样做使代码更长，更冗长，但我认为它使遵循起来更容易。

测验

您可以在 fiddle 中查看所有测试。您可以在Fiddle输出中查看注释以收集其目的。每种 token 类型都针对每种 token 类型进行了测试，但是我还没有做过一次在单个测试中尝试所有可能比较的方法。我还想出了一些随机的艰难难题，例如下面的难题。
abc[def]?fghi?*nop*[tuv]uv[wxy]?yz => a?[cde]defg*?ilmn[opq]*tu*[xyz]*
如果有人想自己测试一下，我在 jsFiddle 上添加了一个接口(interface)。一旦添加递归，日志记录就会中断。

我认为我没有进行足够的负面测试，尤其是在我创建的最后一个版本中。

优化

当前，解决方案是蛮力的，但是足以应付任何情况。我想回到这一点，通过一些简单的优化来改善时间复杂度。

开始时进行检查以减少比较，对于某些常见情况可能会增加处理时间。例如，如果一个模式以星形开头，而一个以结束，则我们已经知道它们将相交。我还可以从模式的开头和结尾检查所有字符，如果两个模式都匹配，则将其删除。这样，它们便不会再出现在将来的递归中。

致谢

我最初使用 @ m.buettner的测试来测试我的代码，然后再提出自己的代码。我也浏览了他的代码，以帮助我更好地理解问题。