使用通配符检查文件名搜索模式中的冲突

Question

我需要通过仅检查/比较表达式来比较文件系统通配符表达式以查看它们的结果是否重叠.

为了便于举例,我们正在构建一个实用程序,它可以根据文件系统通配符表达式将文件从一个(或多个位置)排序到单独的文件夹中.例如:*.txt进入文件夹a,*.doc进入文件夹b,依此类推.我们支持的通配符是*和？

我希望能够通过分析通配符表达式确定它们是否会冲突/重叠.

例如,如果我有以下表达式:

*.x.y
*.y

它们会冲突(重叠),因为第二个表达式*.y将包含*.xy结果.(例如Axy会匹配两个表达式)

我正在通过使用所有表达式构建树结构来接近这一点,认为如果表达式冲突,构建树的行为将失败.

For example:
*.x
a.b
a.c
b.d

might create a tree like 

         +-*-.-x
         |
start +--+
         |     +-b
         |     |
         +-a-.-+-c
         |
         |
         +-b-.-d

如果我尝试添加模式bx,则树将在*.x路径后成功,从而表示模式已存在.

我正朝着正确的方向前进吗？或者是否有一种已知的攻击方法？

Answer 1

要检查两个通配符模式是否可以匹配相同的文件名,您可以将此问题视为创建字符对之间的比较网格,然后检查是否存在对角线路径.下图显示了如何检查通配符模式ab?.c??以及a*bc.*是否存在可能的冲突:

当找到两个相同文字字符之间的匹配时,您将对角移动到下一个要检查的字符.(用绿色箭头表示)

当遇到文字字符和单字符外卡?时,有两种可能性:外卡与字符匹配(对角移动),或者通配符匹配空格,然后跳过它.(用紫色箭头表示)

当遇到多字符外卡*时,需要考虑三种可能性:外卡与另一个字符前的空格匹配,外卡与另一个字符匹配,或外卡匹配多个字符.(用蓝色箭头表示)

代码示例1(迭代)

下面是一个简单的javascript实现,它在对角线上迭代网格,标记可以从当前单元格到达的单元格,然后检查右下角单元格是否可达.运行代码段以查看一些示例.(更新:从左到右从上到下会很好而不是对角线)

function wildConflict(wild1, wild2) {
    var grid = [[true]], width = wild1.length, height = wild2.length;
    for (var x = 1; x <= width; x++) grid[x] = [];
    for (var y = 0; y < height; y++) {
        for (var x = 0; x < width; x++) {
            if (grid[x][y]) {
                var a = wild1.charAt(x), b = wild2.charAt(y);
                if (a == '*' || b == '*' || a == '?' || b == '?' || a == b) grid[x + 1][y + 1] = true;
                if (a == '*' || b == '*' || a == '?') grid[x + 1][y] = true;
                if (a == '*' || b == '*' || b == '?') grid[x][y + 1] = true;
            }
        }
    }
    return grid[width][height] == true;
}

var a = ["a", "a", "a*", "abc", "a*", "*.x.y", "*.x.y", "a*b*", "a*bc.*", "a?c.de"];
var b = ["a", "b", "abc", "a?", "*b", "*.y", "*.x", "a*c*", "ab?.c??", "ac.d??"];
for (var i in a) document.write("&quot;" + a[i] + "&quot; &harr; &quot;" + b[i] + "&quot; &rarr; " + wildConflict(a[i], b[i]) + "<BR>");

代码示例2(递归)

简单的递归实现具有可能多次检查一些字符对的缺点.它不需要2D数组,但递归显然也使用了内存.

请注意,当遇到多字符通配符*时,算法仅使用两种可能性进行递归:跳过一个字符,或跳过另一个字符; 当将通配符与下一个字符进行比较时,在下一步中将跳过两个字符(即,外卡匹配一个字符).

function wildConflict(wild1, wild2) {
    var w1 = wild1.split(''), w2 = wild2.split('');
    return conflict(0, 0);

    function conflict(p1, p2) {
        if (p1 == w1.length || p2 == w2.length) {
            if ((p1 == w1.length && p2 == w2.length)
            || (p1 == w1.length - 1 && (w1[p1] == '*' || w1[p1] == '?'))
            || (p2 == w2.length - 1 && (w2[p2] == '*' || w2[p2] == '?'))) {
                return true;
            }
            else return false;                            // premature end
        }
        else if (w1[p1] == '*' || w2[p2] == '*' || (w1[p1] == '?' && w2[p2] == '?')) {
            return conflict(p1 + 1, p2) || conflict(p1, p2 + 1);
        }
        else if (w1[p1] == '?') {
            return conflict(p1 + 1, p2) || conflict(p1 + 1, p2 + 1);
        }
        else if (w2[p2] == '?') {
            return conflict(p1, p2 + 1) || conflict(p1 + 1, p2 + 1);
        }
        else if (w1[p1] == w2[p2]) {
            return conflict(p1 + 1, p2 + 1);
        }
        else return false;                               // unequal literals
    }
}

var x = ["a", "a", "a*", "abc", "a*", "*.x.y", "*.x.y", "a*b*", "a*bc.*", "a?c.de"];
var y = ["a", "b", "abc", "a?", "*b", "*.y", "*.x", "a*c*", "ab?.c??", "ac.d??"];
for (var i in x) document.write("&quot;" + x[i] + "&quot; &harr; &quot;" + y[i] + "&quot; &rarr; " + wildConflict(x[i], y[i]) + "<BR>");