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

nxowjjhe  于 2023-06-25  发布在  其他
关注(0)|答案(6)|浏览(97)

我正在寻找匹配的glob-style模式,类似于Redis KEYS command accepts。报价:

  • h?llo匹配hello、hallo和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哪个子集是可能的?(即不允许 * 通配符?)
  • 如果确实可能,那么什么是有效算法?
  • 所需的时间复杂度是多少?
    **编辑:**在RegEx子集上发现了另一个问题,但这与hello**ok匹配的单词不完全相同,它们不是彼此的子集/超集,但它们确实相交。

所以我想从数学上讲,这可能是这样表达的;是否可以确定性地检查一个模式匹配的一组单词与另一个模式匹配的一组单词相交,导致非空集合?

**编辑:**一位朋友@neizod绘制了这个消除表,巧妙地可视化了可能的/部分解决方案:Elimination rule
**编辑:**将为那些还可以提供工作代码(任何语言)和测试用例的人增加额外的奖金。
**编辑:**添加了?B?@DanielGimenez在评论中发现的测试用例。

w8ntj3qf

w8ntj3qf1#

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

  • (我在这个答案上下了太多功夫,脑子都坏了;应该有一个徽章。)*

为了确定两个模式是否相交,我创建了一个递归回溯解析器--当遇到***Kleene star***时,会创建一个新的堆栈,这样如果将来失败,所有内容都会回滚,并且***star***会消耗下一个字符。
你可以查看这个答案的历史,以确定这一切是如何得出的,以及为什么它是必要的,但基本上,它是不够的,以确定一个交叉点,向前看只有一个令牌,这是我之前所做的。
这就是打破旧答案[abcd]d => *d的情况。***set***匹配***星星***之后的d,因此左侧仍有令牌剩余,而右侧则是完整的。然而,这两个图案在adbdcddd上相交,因此需要固定。我的 almost O(N)答案被抛出了。

Lexer

词法分析过程很简单,除了处理转义字符和删除多余的星号。令牌被分解为*、、***野生字符(?)和***字符。这与我以前的版本不同,在以前的版本中,一个令牌是一个字符串,而不是一个字符。随着越来越多的案例出现,将字符串作为令牌是一种阻碍而不是优势。

解析器

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

解析星星

简单性以***星星***结束。当它遇到它接管一切。首先,它将自己一方的下一个令牌与另一方的令牌进行比较,推进另一方,直到找到匹配。
一旦找到匹配,它就会检查是否所有内容都匹配到两个模式的末尾。如果是这样,那么模式就相交了。否则,它将另一方的下一个令牌从与之进行比较的原始令牌前进,并重复该过程。
当遇到两个***anys***时,则从彼此的下一个令牌开始进入各自的替代分支。

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输出中的注解以了解它们的用途。每种标记类型都针对每种标记类型进行了测试,但我还没有在一个测试中尝试所有可能的比较。我也想出了一些随机的坚韧的,像下面的一个。
abc[def]?fghi?*nop*[tuv]uv[wxy]?yz => a?[cde]defg*?ilmn[opq]*tu*[xyz]*
我在**jsFiddle**上添加了一个接口,如果有人想自己测试一下。一旦我添加了递归,日志记录就被破坏了。
我认为我没有尝试足够的负面测试,尤其是我创建的最后一个版本。

优化

目前的解决方案是蛮力的,但足以处理任何情况。我想在某个时候回到这一点,通过一些简单的优化来改善时间复杂度。
在开始时进行检查以减少比较可能会增加某些常见情况的处理时间。例如,如果一个模式以***星***开始,一个以1结束,那么我们已经知道它们将相交。我也可以检查所有的字符从开始和结束的模式,并删除他们,如果匹配的两个模式。这样,它们就被排除在任何未来的递归之外。

致谢

我最初使用**@m.buettner的**tests来测试我的代码,然后我想出自己的代码。我还浏览了他的代码,以帮助我更好地理解这个问题。

rxztt3cl

rxztt3cl2#

使用您非常精简的模式语言,您的问题和jpmc 26的注解中的pastebin链接几乎都在那里:主要的问题是,输入字符串的左、右结尾是否匹配。如果它们包含,并且都包含至少一个*,则字符串匹配(因为您总是可以将其他字符串中间的文字文本与该星星匹配)。有一个特殊情况:如果其中只有一个是空的(在删除前缀和后缀之后),如果另一个完全由* s组成,它们仍然可以匹配。
当然,在检查字符串的结尾是否匹配时,还需要考虑单字符通配符?和字符类。单字符通配符很简单:它不会失败,因为它总是匹配其他字符。如果它是一个字符类,而另一个只是一个字符,则需要检查该字符是否在该类中。如果它们都是类,则需要检查类的交集(简单的集合交集)。
下面是JavaScript中的所有内容(查看代码注解,看看上面概述的算法是如何Map到代码的):

var trueInput = [
    { left: 'prefix*', right: 'prefix:extended*' },
    { left: '*suffix', right: '*:extended:suffix' },
    { left: 'left*right', right: 'left*middle*right' },
    { left: 'a*b*c', right: 'a*b*d*b*c' },
    { left: 'hello*', right: '*ok' },
    { left: '*', right: '*'},
    { left: '*', right: '**'},
    { left: '*', right: ''},
    { left: '', right: ''},
    { left: 'abc', right: 'a*c'},
    { left: 'a*c', right: 'a*c'},
    { left: 'a[bc]d', right: 'acd'},
    { left: 'a[bc]d', right: 'a[ce]d'},
    { left: 'a?d', right: 'acd'},
    { left: 'a[bc]d*wyz', right: 'abd*w[xy]z'},
];

var falseInput = [
    { left: 'prefix*', right: 'wrong:prefix:*' },
    { left: '*suffix', right: '*suffix:wrong' },
    { left: 'left*right', right: 'right*middle*left' },
    { left: 'abc', right: 'abcde'},
    { left: 'abcde', right: 'abc'},
    { left: 'a[bc]d', right: 'aed'},
    { left: 'a[bc]d', right: 'a[fe]d'},
    { left: 'a?e', right: 'acd'},
    { left: 'a[bc]d*wyz', right: 'abc*w[ab]z'},
];

// Expects either a single-character string (for literal strings
// and single-character wildcards) or an array (for character
// classes).
var characterIntersect = function(a,b) {
    // If one is a wildcard, there is an intersection.
    if (a === '?' || b === '?')
        return true;

    // If both are characters, they must be the same.
    if (typeof a === 'string' && typeof b === 'string')
        return a === b;

    // If one is a character class, we check that the other
    // is contained in the class.
    if (a instanceof Array && typeof b === 'string')
        return (a.indexOf(b) > -1);
    if (b instanceof Array && typeof a === 'string')
        return (b.indexOf(a) > -1);

    // Now both have to be arrays, so we need to check whether
    // they intersect.
    return a.filter(function(character) {
        return (b.indexOf(character) > -1);
    }).length > 0;
};

var patternIntersect = function(a,b) {
    // Turn the strings into character arrays because they are
    // easier to deal with.
    a = a.split("");
    b = b.split("");

    // Check the beginnings of the string (up until the first *
    // in either of them).
    while (a.length && b.length && a[0] !== '*' && b[0] !== '*')
    {
        // Remove the first character from each. If it's a [,
        // extract an array of all characters in the class.
        aChar = a.shift();
        if (aChar == '[')
        {
            aChar = a.splice(0, a.indexOf(']'));
            a.shift(); // remove the ]
        }
        bChar = b.shift();
        if (bChar == '[')
        {
            bChar = b.splice(0, b.indexOf(']'));
            b.shift(); // remove the ]
        }

        // Check if the two characters or classes overlap.
        if (!characterIntersect(aChar, bChar))
            return false;
    }

    // Same thing, but for the end of the string.
    while (a.length && b.length && a[a.length-1] !== '*' && b[b.length-1] !== '*')
    {
        aChar = a.pop();
        if (aChar == ']')
        {
            aChar = a.splice(a.indexOf('[')+1, Number.MAX_VALUE);
            a.pop(); // remove the [
        }
        bChar = b.pop();
        if (bChar == ']')
        {
            bChar = b.splice(b.indexOf('[')+1, Number.MAX_VALUE);
            b.pop(); // remove the [
        }

        if (!characterIntersect(aChar, bChar))
            return false;
    }

    // If one string is empty, the other has to be empty, too, or
    // consist only of stars.
    if (!a.length && /[^*]/.test(b.join('')) ||
        !b.length && /[^*]/.test(b.join('')))
        return false;

    // The only case not covered above is that both strings contain
    // a * in which case they certainly overlap.
    return true;
};

console.log('Should be all true:');
console.log(trueInput.map(function(pair) {
    return patternIntersect(pair.left, pair.right);
}));

console.log('Should be all false:');
console.log(falseInput.map(function(pair) {
    return patternIntersect(pair.left, pair.right);
}));

这不是最整洁的实现,但它工作正常,并且(希望)仍然非常可读。检查开头和结尾会有相当多的代码重复(这可以在检查开头后用一个简单的reverse来减轻-但我认为这只会使事情变得模糊)。可能还有很多其他的部分可以得到很大的改进,但我认为逻辑已经到位了。
再补充几句:该实现假设模式格式良好(没有不匹配的左括号或右括号)。此外,我从this answer中获取了数组交集代码,因为它很紧凑--如果有必要,当然可以提高效率。
不管这些实现细节如何,我想我也可以回答你的复杂性问题:外部循环同时遍历两个字符串,一次遍历一个字符。这就是线性复杂性。除了字符类测试之外,循环中的所有事情都可以在恒定时间内完成。如果一个字符是字符类而另一个不是,则需要线性时间(类的大小是参数)来检查字符是否在类中。但这并不意味着它是二次的,因为类中的每个字符意味着外部循环的迭代次数减少了一次。所以这仍然是线性的。因此,最昂贵的事情是两个字符类的交集。这可能比线性时间更复杂,但最糟糕的情况是O(N log N):毕竟,你可以只对两个字符类进行排序,然后在线性时间内找到一个交集。我认为你甚至可以通过将字符类中的字符散列到它们的Unicode代码点(JS中的.charCodeAt(0))或其他一些数字来获得整体线性时间复杂度-在散列集中找到交集是可能的。所以,如果你真的想,我认为你应该能够得到O(N)
什么是N?上限是两种模式的长度之和,但在大多数情况下,它实际上会更小(取决于两种模式的前缀和后缀的长度)。
请指出我的算法遗漏的任何边缘情况。我也很高兴建议的改进,如果他们改善或至少不降低代码的清晰度。
Here is a live demo on JSBin(感谢chakrit将其粘贴在那里)。

**编辑:**正如丹尼尔指出的,我的算法错过了一个概念上的边缘情况。如果(在消除开头和结尾之前或之后)一个字符串不包含*,而另一个字符串包含*,则在某些情况下,这两个字符串仍然冲突。不幸的是,我现在没有时间调整代码片段来适应这个问题,但我可以概述如何解决它。

在消除字符串的两端之后,如果两个字符串都是空的或者都至少包含*,它们将始终匹配(在完全消除之后查看可能的*-分布)。唯一不平凡的情况是一个字符串仍然包含*,但另一个不包含(无论是否为空)。我们现在需要做的是再次从左到右遍历两个字符串。让我将包含*的字符串称为A,将不包含x1m13 n1 B。
我们从左到右遍历A,跳过所有的*(只注意?、字符类和文字字符)。对于每个相关的标记,我们从左到右检查它是否可以在B中匹配(在第一次出现时停止),并将B光标前进到该位置。如果我们在A中找到一个标记,而这个标记在B中再也找不到了,那么它们就不匹配。如果我们设法为A中的每个标记找到匹配,它们确实匹配。这样,我们仍然使用线性时间,因为没有涉及回溯。这里有两个例子。这两个应该匹配:

A: *a*[bc]*?*d* --- B: db?bdfdc
    ^                    ^
A: *a*[bc]*?*d* --- B: db?bdfdc
      ^                   ^
A: *a*[bc]*?*d* --- B: db?bdfdc
           ^               ^
A: *a*[bc]*?*d* --- B: db?bdfdc
             ^               ^

这两个不应该匹配:

A: *a*[bc]*?*d* --- B: dbabdfc
    ^                    ^
A: *a*[bc]*?*d* --- B: dbabdfc
      ^                   ^
A: *a*[bc]*?*d* --- B: dbabdfc
           ^               ^
A: *a*[bc]*?*d* --- B: dbabdfc
             !

它失败了,因为?不可能在第二个d之前匹配,之后B中没有更多的d来容纳A中的最后一个d
如果我花时间将字符串正确地解析为令牌对象,那么将其添加到我当前的实现中可能很容易。但是现在,我不得不再次经历解析这些字符类的麻烦。我希望这份书面大纲的补充是足够的帮助。
PS:当然,我的实现也没有考虑转义元字符,并且可能会在字符类中被*卡住。

rnmwe5a2

rnmwe5a23#

这些特殊模式的功能远不如完整的正则表达式强大,但我会指出,即使使用一般的正则表达式,也可以做你想做的事情。这些必须是“真”正则表达式,即那些只使用Kleene星星,交替(the|操作),以及与任何固定字母加上空字符串和空集的串联。当然,你也可以在这些操作中使用任何语法糖:一个或多个(+)、可选(?)。字符集只是一种特殊的交替[a-c] == a| B| c.第一次会议
该算法原理简单:使用标准构造将每个正则表达式转换为DFA:汤普森紧随其后。然后使用叉积构造来计算两个原件的交集DFA。最后,检查这个交集DFA,以确定它是否至少接受一个字符串。这只是从开始状态开始的dfs,以查看是否可以达到接受状态。
如果你不熟悉这些算法,很容易找到互联网参考。
如果交集DFA接受了至少一个字符串,则原始正则表达式之间存在匹配,并且dfs发现的路径给出了满足两者的字符串。否则没有匹配。

7fyelxc5

7fyelxc54#

问得好!
这里主要的复杂性是处理字符类([...])。我的方法是用一个正则表达式来替换每一个,该正则表达式查找 * either * 指定字符中的一个(或?)* 或 * 至少包含一个指定字符的另一个字符类。所以对于[xyz],这将是:([xyz?]|\[[^\]]*[xyz].*?\])-见下文:

然后对于“前缀”(第一个*之前的所有内容),将^放在开头,或者对于“后缀”(最后一个*之后的所有内容),将$放在结尾。
更多详情:-
1.还需要将?的所有示例替换为(\[.*?\]|[^\\]]),以使其匹配字符类或单个字符(不包括左方括号)。
1.还需要替换不在字符类中且不是?的每个字符,以使其匹配相同的字符?或包含该字符的字符类。例如,a将变为([a?]|\[[^\]]*a.*?\])。(有点罗嗦,但事实证明是必要的-见下面的评论)。
1.测试应按以下方式进行:针对前缀#2测试 * 前缀#1转换为regex*,然后针对前缀#1测试 * 前缀#2转换为regex*。如果任一匹配,则前缀可以被称为“相交”。
1.对后缀重复步骤(3.):对于正结果,* 前缀和后缀必须相交。

**EDIT:**除了上述情况外,还有一种特殊情况,即其中一个模式至少包含一个*,但另一个模式不包含。在这种情况下,带有*的整个模式应该转换为正则表达式:*应该匹配任何东西,但附带条件是它只包括 * 整个 * 字符类。这可以通过将*的所有示例替换为(\[.*?\]|[^\\]])来完成。

为了避免这个答案变得冗长,我不会发布完整的代码,但这里有一个单元测试的工作演示:http://jsfiddle.net/mb3Hn/4/

**编辑#2 -已知的不完整性:**在当前形式下,演示不适合转义字符(例如:\[)。这不是一个很好的借口,但我只是在当天晚些时候才注意到这些-他们没有在问题中提到,只有link。为了处理它们,需要增加一点正则表达式的复杂性,例如:检查[之前是否存在反斜杠。使用negative lookbehind这应该是相当轻松的,但不幸的是JavaScript不支持它。有一些变通方法,比如用负前瞻来反转字符串和正则表达式,但我不热衷于用这种额外的复杂性来降低代码的可读性,也不确定它对OP有多重要,所以将其作为“读者的练习”。回想起来,也许应该选择一种具有更全面的正则表达式支持的语言!

mbskvtky

mbskvtky5#

使用greenery确定一个正则表达式是否匹配另一个正则表达式的子集:
首先,pip3 install https://github.com/ferno/greenery/archive/master.zip
然后:

from greenery.lego import parse as p
a_z = p("[a-z]")
b_x = p("[b-x]")
assert a_z | b_x == a_z
m_n = p("m|n")
zero_nine = p("[0-9]")
assert not m_n | zero_nine == m_n
of1yzvn4

of1yzvn46#

我写了这个Go项目:glob-intersection,主要感谢这里的讨论,早在2017年。
它是正则表达式风格的globs,所以必须使用.*而不是*,但是@chakrit在他们的原始帖子中给出的所有示例都应该可以工作。

相关问题