Алгоритм, чтобы выяснить, пересекаются ли совпадения двух шаблонов Glob (или регулярных выражений)

Ответ 1

Теперь засвидетельствовать огневую мощь этой полностью ВООРУЖЕННОЙ и ОПЕРАТИВНОЙ боевой станции!

(Я слишком много работал над этим ответом, и мой мозг сломался, для этого должен быть значок).

Чтобы определить, пересекаются ли два шаблона, я создал рекурсивный анализатор обратного отслеживания - когда встречается звезд Kleene, создается новый стек, так что если он не удастся в будущем, все откатится назад и звезда потребляет следующий символ.

Вы можете просмотреть историю этого ответа, чтобы определить, как это было достигнуто, и почему это было необходимо, но в основном этого было недостаточно, чтобы определить пересечение, заглянув вперед только в один токен, что я и делал раньше.

В этом случае был разбит старый ответ [abcd]d = > *d. набор соответствует d после звезды, поэтому на левой стороне все еще останутся токены, а правая сторона будет завершена. Тем не менее, эти два шаблона пересекаются на ad, bd, cd и dd, поэтому их необходимо исправлять. Мой почти O (N) ответ был выброшен.

Лексер

Процесс лексики является тривиальным, за исключением того, что обрабатываются escape-символы и удаляет избыточные звезды. Токены разбиты на наборы, звезд, диких символов (?) и символ. Это отличается от предыдущих версий, когда один токен был строкой символов вместо одного символа. По мере появления большего количества случаев наличие строк в качестве токенов было скорее препятствием, чем преимуществом.

Parser

Большинство функций парсера довольно тривиальны. Переключатель, заданный с левого типа, вызывает функцию, которая представляет собой переключатель, который определяет соответствующую функцию для сравнения с правым типом. Результат сравнения приводит к смещению двух переключателей к исходному вызываемому абоненту, обычно к основному циклу анализатора.

Разбор звезд

Простота заканчивается на звезда. Когда это встречается, оно берет на себя все. Сначала он сравнивает свою сторону рядом с другой стороной, продвигая другую сторону, пока не найдет совпадение.

Как только совпадение найдено, оно проверяет, все ли все до конца обоих шаблонов. Если это так, то шаблоны пересекаются. В противном случае он продвигает другую сторону рядом с оригиналом, который был сопоставлен и повторяет процесс.

Когда встречаются две 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 (N ²).

Поддержание работоспособности и удобочитаемости

Я целенаправленно разрывал любые ветки в собственных функциях с единственным переключателем. Обычно я использовал именованные константы, когда достаточно одной символьной строки. Выполнение этого делало код более длинным и более подробным, но я думаю, что это облегчает его выполнение.

Испытания

Вы можете просмотреть все тесты в Fiddle. Вы можете просмотреть комментарии на выходе Fiddle, чтобы узнать их цели. Каждый тип токена был протестирован против каждого типа токена, но я не сделал того, который пытался провести все возможные сравнения в одном тесте. Я также придумал несколько случайных жестких, таких как ниже.

abc[def]?fghi?*nop*[tuv]uv[wxy]?yz = > a?[cde]defg*?ilmn[opq]*tu*[xyz]*

Я добавил интерфейс jsFiddle, если кто-то хочет проверить это самостоятельно. Журналирование прерывается, как только я добавил рекурсию.

Я не думаю, что я пробовал достаточно отрицательных тестов, особенно с последней версией, которую я создал.

Оптимизация

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

Проверки в начале, чтобы уменьшить сравнение, могут увеличить время обработки для некоторых распространенных сценариев. Например, если один шаблон начинается с звезды, а один заканчивается на один, мы уже знаем, что они пересекаются. Я также могу проверить все символы от начала и конца шаблонов и удалить их, если они совпадают с обоими шаблонами. Таким образом, они исключаются из любой будущей рекурсии.

Выражение признательности

Сначала я использовал тесты @m.buettner, чтобы проверить свой код, прежде чем я придумал свой собственный. Также я прошел через его код, чтобы помочь мне лучше понять проблему.

Ответ 2

С вашим очень ограниченным языком шаблонов ссылка pastebin в вашем вопросе и комментарии jpmc26 в значительной степени полностью доступны: главный вопрос заключается в том, соответствует ли буквальный левый и правый конец ваших строк ввода. Если это так, и оба содержат хотя бы один *, строки соответствуют (потому что вы всегда можете сопоставить другой текст промежуточного литерала с этой звездой). Существует один частный случай: если только один из них пуст (после удаления префикса и суффикса), они все равно могут совпадать, если другой полностью состоит из * s.

Конечно, при проверке соответствия концов строки вам нужно учитывать односимвольный шаблон ? и классы символов. Односимвольный шаблон легко: он не может потерпеть неудачу, потому что он всегда будет соответствовать любому другому персонажу. Если это класс символов, а другой - просто символ, вам нужно проверить, находится ли этот символ в классе. Если это оба класса, вам нужно проверить пересечение классов (это простое пересечение).

Вот все это в JavaScript (ознакомьтесь с комментариями кода, чтобы увидеть, как описанный выше алгоритм сопоставляется с кодом):

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 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 после проверки начала, но я подумал, что это просто затмило бы вещи). И есть, вероятно, множество других бит, которые могут быть значительно улучшены, но я думаю, что логика все в порядке.

Еще несколько замечаний: в реализации предполагается, что шаблоны хорошо отформатированы (нет непревзойденных открывающих или закрывающих скобок). Кроме того, я взял код пересечения массива из этого ответа, потому что он компактный - вы, безусловно, могли бы повысить эффективность этого при необходимости.

Независимо от этих деталей реализации, я думаю, что я тоже могу ответить на ваш вопрос о сложности: внешний цикл проходит одновременно по обеим строкам, персонажу за раз. Так что линейная сложность. Все внутри цикла может быть выполнено в постоянное время, за исключением тестов класса символов. Если один символ является классом символов, а другой - нет, вам нужно линейное время (с размером класса, являющимся параметром), чтобы проверить, находится ли этот символ в классе. Но это не делает его квадратичным, потому что каждый символ в классе означает одну меньшую итерацию внешнего цикла. Так что все еще линейно. Самая дорогостоящая вещь - это, следовательно, пересечение двух классов символов. Это может быть более сложным, чем линейное время, но самое худшее, что он может получить, это O(N log N): в конце концов, вы можете просто отсортировать оба класса символов, а затем найти пересечение в линейном времени. Я думаю, что вы даже можете получить общую линейную сложность по времени, путем хэширования символов в классе символов к их кодовой точке Unicode (.charCodeAt(0) в JS) или некоторого другого номера - и найти пересечение в хешированном наборе возможно в линейное время. Итак, если вы действительно этого хотите, я думаю, вы сможете перейти к O(N).

А что такое N? Верхний предел представляет собой сумму длины обоих шаблонов, но в большинстве случаев она будет фактически меньше (в зависимости от длины префиксов и суффиксов обоих паттернов).

Пожалуйста, указывайте мне на любые кромки, которые не хватает моему алгоритму. Я также рад предлагаемым улучшениям, если они улучшают или, по крайней мере, не уменьшают ясность кода.

Вот живая демонстрация на JSBin (благодаря чакриту для вставки его там).

EDIT: Как отметил Дэниел, есть концептуальный краевой вариант, который мой алгоритм упускает. Если (до или после устранения начала и конца) одна строка не содержит *, а другая, есть случаи, когда две все еще сталкиваются. К сожалению, сейчас у меня нет времени корректировать фрагмент кода для решения этой проблемы, но я могу описать, как его разрешить.

После устранения обоих концов строк, если обе строки либо пусты, либо обе содержат не менее *, они всегда будут совпадать (пройдите через возможные * -распределения после полного устранения, чтобы увидеть это). Единственный случай, который не является тривиальным, состоит в том, что одна строка содержит *, а другая - нет (пусто или нет). Теперь нам нужно снова пройти обе строки слева направо. Позвольте мне вызвать строку, содержащую * A и ту, которая не содержит * 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 в B для размещения последнего d в A.

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

PS: Конечно, моя реализация также не учитывает экранирование метасимволов и может захлебнуться в * внутри классов символов.

Ответ 3

Эти специальные шаблоны значительно менее эффективны, чем полные регулярные выражения, но я укажу, что можно делать то, что вы хотите, даже с помощью обычных регулярных выражений. Это должны быть "истинные" регулярные выражения, т.е. Те, которые используют только звезду Клейна, чередование (операцию |) и конкатенацию с любым фиксированным алфавитом плюс пустую строку и пустой набор. Конечно, вы можете использовать любой синтаксический сахар на этих операциях: один или более (+), необязательный (?). Наборы символов - это особый вид чередования [a-c] == a | b | c.

Алгоритм прост в принципе: преобразовать каждое регулярное выражение в DFA с помощью стандартных конструкций: Thompson с последующим набором параметров. Затем используйте конструкцию кросс-произведения, чтобы вычислить пересечение DFA двух оригиналов. Наконец, проверьте это пересечение DFA, чтобы определить, принимает ли он хотя бы одну строку. Это только dfs из состояния начала, чтобы узнать, можно ли достичь состояния принятия.

Если вы не знакомы с этими алгоритмами, легко найти ссылки в Интернете.

Если хотя бы одна строка принимается пересечением DFA, между исходными регулярными выражениями существует совпадение, а путь, открытый dfs, дает строку, которая удовлетворяет обоим. Иначе нет соответствия.

Ответ 4

Хороший вопрос!

Основная сложность заключается в обработке классов символов ([...]). Мой подход заключается в замене каждого из них на регулярное выражение, которое ищет либо один из указанных символов (или ?), либо другой класс символов, который включает по крайней мере один из указанных символов. Итак, для [xyz] это будет: ([xyz?]|\[[^\]]*[xyz].*?\]) - см. Ниже:

Затем для "префиксов" (все до первого *) поместите ^ в начале или для "суффиксов" (все после последнего *), поместите $ в конец.

Дополнительная информация: -

• Также необходимо заменить все экземпляры ? на (\[.*?\]|[^\\]]), чтобы он соответствовал либо классу символов, либо одиночному символу (исключая квадратную скобку открытия).
• Также необходимо заменить каждый отдельный символ, который не находится в классе символов, а не ?, чтобы он соответствовал одному символу, ? или классу символов, который включает символ. Например. a станет ([a?]|\[[^\]]*a.*?\]). (Немного длинный, но оказался необходимым - см. Комментарии ниже).
• Тестирование должно выполняться в обоих направлениях: Тест префикС# 1 преобразован в регулярное выражение с префиксом # 2, затем префикС# 2 преобразован в регулярное выражение с префиксом # 1. Если они совпадают, префиксы можно сказать "пересекаться".
• Повторите шаг (3.) для суффиксов: для положительного результата оба префикса и суффиксы должны пересекаться.

EDIT: В дополнение к вышесказанному, есть специальный случай, когда один из шаблонов содержит хотя бы один *, а другой - нет. В этом случае весь шаблон с * должен быть преобразован в регулярное выражение: * должен совпадать с чем-либо, но с условием, что он включает только целые классы символов. Это можно сделать, заменив все экземпляры * на (\[.*?\]|[^\\]]).

Чтобы избежать такого ответа, я не буду публиковать полный код, но здесь есть рабочая демонстрация с модульными тестами: http://jsfiddle.net/mb3Hn/4/

РЕДАКТИРОВАТЬ # 2 - Известная неполнота: В текущей форме демо не поддерживает экранированные символы (например, \[). Не большое оправдание, но я заметил только это в конце дня - они не упоминаются в вопросе, только ссылка . Для их обработки потребуется немного дополнительной сложности регулярных выражений, например. для проверки отсутствия символа обратной косой черты непосредственно перед [. Это должно быть довольно безболезненно с отрицательный lookbehind, но, к сожалению, Javascript его не поддерживает. Есть обходные пути, такие как обращение к строкам и регулярному выражению с негативным взглядом, но я не заинтересован в том, чтобы сделать код менее понятным с этой дополнительной сложностью и не уверен, насколько важно это для OP, поэтому он оставит его как "упражнение для читатель". В ретроспективе, возможно, должен был выбрать язык с более полной поддержкой регулярных выражений!

Ответ 5

Определение того, соответствует ли регулярное выражение подмножеству другого регулярного выражения с помощью 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