使用通配符检查文件名搜索模式中的冲突
里克·霍德（Rick Hodder）
我需要通过仅检查/比较表达式来比较文件系统通配符表达式，以查看其结果是否重叠。
举例来说，我们正在构建一个实用程序，该实用程序可以根据文件系统通配符表达式将一个（或多个位置）中的文件排序到一个单独的文件夹中。例如：* .txt进入文件夹a，*。doc进入文件夹b，依此类推。我们将支持的通配符为*和？
我希望能够仅通过分析通配符表达式来确定它们是否会冲突/重叠。
例如，如果我有以下表达式：
* .xy * .Y
它们会发生冲突（重叠），因为第二个表达式* .y将包含* .xy结果。（例如，Axy将匹配两个表达式）
我正在通过使用所有表达式来构建树结构来解决这个问题，认为如果表达式冲突，构建树的行为将失败。
例如：
*。X
b
交流电
d
可能会像
+-* -.- x
|
开始+-+
| + -b
| |
+ -a -.- +-c
|
|
+ -b -.- d
如果我尝试添加模式bx，则树将沿* .x路径成功运行，因此可以说该模式已经存在。
我朝着正确的方向前进吗？还是有一种已知的算法可以对此进行攻击？
m69``干躁不受欢迎''
要检查两个通配符模式是否可以匹配相同的文件名，可以将这个问题视为在成对的字符之间创建比较网格，然后检查是否存在对角线路径。下图显示了通配符模式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(""" + a[i] + "" ↔ "" + b[i] + "" → " + 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(""" + x[i] + "" ↔ "" + y[i] + "" → " + wildConflict(x[i], y[i]) + "<BR>");本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
Powershell-使用通配符搜索文件名
- 2
如何使用字典中的“键”作为匹配文件名中的通配符模式？
- 3
用数字搜索文件名中的模式
- 4
重击，在文件名中搜索模式并进行比较
- 5
使用零填充文件名中的索引并接受通配符
- 6
使用python中的模式或正则表达式匹配检查文件名
- 7
在所有服务器共享中搜索通配符文件名
- 8
文件名中的Subversion冲突
- 9
使用PowerShell在文件名中搜索字符串
- 10
检查文件夹中的任何文件是否包含模式，然后返回文件名
- 11
复制文件名中带有方括号[]的文件，并使用*通配符
- 12
如何使用文件名中的通配符从chown递归中排除文件？
- 13
处理文件名中带有通配符的文件
- 14
处理文件名中带有通配符的文件
- 15
与通配符的文件名比较
- 16
在AppCode中搜索文件名
- 17
仅在目录的指定文件名中递归搜索模式/文本？
- 18
Ansible剧本中的JAR文件名可以使用通配符吗？
- 19
如何使用ack搜索文件名
- 20
从文件名中删除模式
- 21
模式与R中的文件名匹配
- 22
变量中带有通配符的文件名
- 23
如何在Bash中获取文件名的通配符部分
- 24
Perl通配符匹配“ ls”输出中的文件名
- 25
在 tcl 中复制文件名（带通配符）
- 26
从PyCharm搜索中排除带有模式的文件名
- 27
如何使用带有“长文件名”的通配符*？
- 28
Ms Access 使用通配符或循环获取文件名
- 29
如何检查文件名是否符合模式？
我来说两句