小编典典

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

algorithm

我正在查看类似Redis KEYS命令接受的匹配的glob样式的模式。报价:

  • h?llo与hello,hello和hxllo匹配
  • h * llo匹配hllo和heeeello
  • h [ae] llo匹配hello和hallo,但不匹配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

所以我想知道…

  • 是否有可能(实施验证算法),如果有的话?
  • 如果不可能,那么正则表达式的哪些子集是可能的?(即不允许*通配符?)
  • 如果确实有可能,什么是有效的算法?
  • 需要多少时间?

编辑:在RegEx子集上发现了另一个问题,但这与单词hello*and *okmatch并非彼此的子集/超集完全相同,但它们确实相交。

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


编辑:
一位朋友@neizod草拟了这张消除表,它巧妙地形象化了潜在的/部分解决方案:消除规则


编辑: 将为那些还可以提供工作代码(以任何语言)和证明它的测试用例的人增加额外的赏金。


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


阅读 216

收藏
2020-07-28

共1个答案

小编典典

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

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

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

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

这是打破旧答案[abcd]d=>的情况*d。该 集合
star
d之后的匹配,因此左侧将仍然保留令牌,而右侧将是完整的。然而,这些图案的两个相交上,,和,因此需要加以固定。我 几乎是
O(N)的答案被抛出了。 __ad``bd``cd``dd __

Lexer

词法化过程很简单,除了过程是转义字符并删除多余的 星星 。令牌分为 集合 星号 通配符(?)
character
。这与我以前的版本不同,在我以前的版本中,一个标记是一个字符串而不是一个字符。随着越来越多的案例出现,使用字符串作为令牌更多的是障碍而不是优势。

解析器

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

解析星星

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

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

当遇到两个 任意 一个时,则从彼此的下一个令牌开始进入其自己的替代分支。

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(N 2)。

可维护性和可读性

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

测验

您可以在小提琴中查看所有测试。您可以在Fiddle输出中查看注释,以了解其目的。每种令牌类型都针对每种令牌类型进行了测试,但是我还没有做过一次测试中所有可能比较的尝试。我还想出了一些随机的艰难难题,例如下面的难题。

abc[def]?fghi?*nop*[tuv]uv[wxy]?yz => a?[cde]defg*?ilmn[opq]*tu*[xyz]*

如果有人想自己测试一下,我在 jsFiddle
上添加了一个接口。一旦添加递归,日志记录就会中断。

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

优化

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

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

致谢

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

2020-07-28