Проверка столкновения в шаблонах поиска файлов с помощью подстановочных знаков

Ответ 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

Поверните каждое выражение подстановки в конечный автомат, который соответствует ему.

Вычислить пересечение конечных автоматов.

Используйте динамическое программирование, чтобы увидеть, может ли пересечение соответствовать.

Если вы не узнаете эти понятия, см. Алгоритм исключения чисел, чтобы попытаться объяснить это несколько лет назад. (В этот момент для подсчета вещей, которые соответствуют набору регулярных выражений, но принципы идентичны.)

Ответ 3

Я думаю, вы могли бы превратить шаблоны в регулярные выражения, а затем посмотреть, соответствуют ли они друг другу? Решение здесь основано на правилах для Directory.GetFiles на MSDN - я чувствую, что там 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;
    }

РЕДАКТИРОВАТЬ: на основании дальнейшего обсуждения в комментариях это нарушено. Доказательство с использованием кода, который он сломал:

        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*"));