使用通配符检查文件名搜索模式中的冲突
我需要通过仅检查/比较表达式来比较文件系统通配符表达式以查看它们的结果是否重叠。
例如，我们正在构建一个实用程序，它可以根据文件系统通配符表达式将文件从一个（或多个位置）排序到单独的文件夹中。 例如：* .txt进入文件夹a，* .doc进入文件夹b，依此类推。 我们支持的通配符是*和？
我希望能够通过分析通配符表达式确定它们是否会发生冲突/重叠。
例如，如果我有以下表达式：
*某个.XY * .Y
它们会冲突（重叠），因为第二个表达式* .y将包含* .xy结果。 （例如Axy会匹配两个表达式）
我正在通过使用所有表达式构建树结构来接近这一点，认为如果表达式冲突，构建树的行为将失败。
例如：
*。X
AB
AC
BD
可能会创建一个树
+ - * -.- X
|
开始+ - +
| + -b
| |
+ -a -.- + - Ç
|
|
+ -b -.- d
如果我尝试添加模式bx，则树将在* .x路径后成功，从而表示该模式已存在。
我正朝着正确的方向前进吗？ 或者是否有一种已知的攻击方法？
要检查两个通配符模式是否可以匹配相同的文件名，您可以将此问题视为创建字符对之间的比较网格，然后检查是否存在对角线路径。 下图显示了通配符模式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*", "*.xy", "*.xy", "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]) + "
");
将每个通配符表达式转换为与其匹配的有限自动机。
计算有限自动机的交集。
使用动态编程来查看交叉点是否匹配。
如果您不认识这些概念，请参阅几年前尝试解释它的数字排除算法 。 （此时用于计算与正则表达式集合匹配的内容，但原则相同。）
我想你可以把模式变成正则表达式，然后看看它们是否相互匹配？ 这里的解决方案是基于MSDN上的Directory.GetFiles的规则 – 我觉得SOMETHING有错，但我不确定是什么。
这是一个基本的实现
private bool Equivalent(string patternOne, string patternTwo) { // convert both patterns to regexes based on rules for Directory.GetFiles var expressionOne = FilePatternToRegex(patternOne); var expressionTwo = FilePatternToRegex(patternTwo); // if either regex matches the opposite pattern, we've got a conflict return expressionTwo.IsMatch(patternOne) || expressionOne.IsMatch(patternTwo); } Regex FilePatternToRegex(string pattern) { // separate extension and filename var extension = Path.GetExtension(pattern); var filename = Path.GetFileNameWithoutExtension(pattern); // escape filename filename = EscapeFilePattern(filename); // 3 character extensions are a special case -- should be greedy eg xls matches xlsx // extension.Length == 4 bc its dot AND 3 characters if (extension.Length == 4 && !extension.Contains("*") && !extension.Contains("?")) { extension = extension + ".*"; } else { // all other extension lengths just get escaped like normal regexes extension = EscapeFilePattern(extension); } // our final pattern should also only match at the string start/end var finalPattern = "\\A" + filename + extension + "\\z"; return new Regex(finalPattern); } string EscapeFilePattern(string pattern) { // escape star and question mark bc they are filepattern significant pattern = pattern.Replace("*", "%S%").Replace("?", "%Q%"); // escape all other special regex characters pattern = Regex.Escape(pattern); // turn star and question mark into their regex equivalents pattern = pattern.Replace("%S%", ".+").Replace("%Q%", "."); return pattern; }
编辑 ：根据评论中的进一步讨论，这是打破。 使用代码示例certificate它已被破坏：
var dir = new DirectoryInfo(Environment.CurrentDirectory).CreateSubdirectory(Guid.NewGuid().ToString()); var path = Path.Combine(dir.FullName, "abc"); File.WriteAllText(path, "*"); // verify both patterns match our file Assert.AreEqual(path, dir.GetFiles("a*c*")[0].FullName); Assert.AreEqual(path, dir.GetFiles("a*b*")[0].FullName); // current regex based solution thinks they are NOT equivalent // when they are Assert.IsFalse(Equivalent("a*c*", "a*b*"));