Сложность подстановки регулярных выражений

Question

Я нигде не получил ответа на это. Какова сложность выполнения совпадений и подстановок в Regex?

Редактировать: я работаю в Python. Но хотелось бы узнать в целом о наиболее популярных языках / инструментах (java, perl, sed).

Answer 1

С чисто теоретической позиции:

Реализация, с которой я знаком, состояла бы в создании детерминированного конечного автомата для распознавания регулярного выражения. Это делается в O (2 ^ m), где m является размером регулярного выражения, используя стандартный алгоритм. Как только это будет построено, проход строки через нее будет линейным по длине строки - O (n), где n - длина строки. Замена найденного в строке совпадения должна иметь постоянное время.

Итак, я полагаю, O (2 ^ m + n).

Answer 2

Другая теоретическая информация, представляющая интерес.

Для ясности предположим стандартное определение регулярного выражения

http://en.wikipedia.org/wiki/Regular_language

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

Существует конструкция NFA, которая решает проблему соответствия для регулярного Выражение r и входной текст t в O (| r | | t |) времени и O (| r |) пространстве, где | - | это функция длины. Этот алгоритм был дополнительно улучшен Майерсом

http://doi.acm.org/10.1145/128749.128755

к временной и пространственной сложности O (| r | | t | / log | t |) с помощью автоматных списков узлов и парадигмы четырех русских. Эта парадигма, кажется, названа в честь четырех русских парней, которые написали новаторскую статью, которая не онлайн. Тем не менее, парадигма иллюстрируется в этой вычислительной биологии конспект лекции

http://lyle.smu.edu/~saad/courses/cse8354/lectures/lecture5.pdf

Я нахожу забавным назвать парадигму числом и национальность авторов вместо фамилий.

Проблема соответствия для регулярных выражений с добавленными обратными ссылками NP-полная, подтвержденная Aho

http://portal.acm.org/citation.cfm?id=114877

путем сокращения от задачи покрытия вершин, которая является классической NP-полной задачей.

Чтобы детерминистически сопоставить регулярные выражения с обратными ссылками, мы могли бы использовать возврат (не в отличие от двигателя регулярного выражения Perl), чтобы отслеживать возможные подслова входного текста t, которые могут быть назначены переменным в р. Есть только O (| t | ^ 2) подслов, которые могут быть назначены на любую переменную в г. Если в r есть n переменных, то возможны O (| t | ^ 2n) задания. После того, как назначение подстрок переменным зафиксировано, проблема сводится к простому совпадению регулярного выражения. Следовательно сложность наихудшего случая для сопоставления регулярных выражений с обратными ссылками O (| т | ^ 2n)

.

Обратите внимание, что регулярные выражения с обратными ссылками еще не Полнофункциональное регулярное выражение.

Взять, к примеру, символ "все равно", кроме любого другого операторы. Есть несколько полиномиальных алгоритмов, решающих, является ли набор Шаблоны соответствуют входному тексту. Например, Кучеров и Русинович

http://dx.doi.org/10.1007/3-540-60044-2_46

определить шаблон как слово w_1 @ w_2 @ ... @ w_n, где каждый w_i - это слово (не регулярное выражение), а "@" - это символ переменной длины "не волнует", не содержащийся ни в w_i. Они выводят алгоритм O ((| t | + | P |) log | P |) для сопоставления набора шаблонов P с входным текстом t, где | t | длина текста, а | P | длина всех слов в P.

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

Увы, я не сказал ни слова о Python ...:)

Answer 3

Зависит от того, что вы определяете с помощью регулярных выражений. Если вы разрешите операторы конкатенации, alternative и Kleene-star, на самом деле время может быть O(m*n+m), где m - это размер регулярного выражения, а n - длина строки. Вы делаете это путем создания NFA (который является линейным в m), а затем моделируете его, поддерживая набор состояний, в котором вы находитесь, и обновляя его (в O(m)) для каждой буквы ввода.

Вещи, которые затрудняют синтаксический анализ регулярных выражений:

• круглые скобки и обратные ссылки: с вышеупомянутым алгоритмом захват все еще в порядке, хотя сложность может быть выше, поэтому он может быть неосуществимым. Обратные ссылки повышают силу распознавания регулярного выражения, и его сложность вполне достаточна
• положительный прогноз: это просто еще одно название для пересечения, которое повышает сложность вышеупомянутого алгоритма до O(m^2+n)
• негативный прогноз: катастрофа для построения автомата (O(2^m), возможно, PSPACE-полная). Но все еще должно быть возможно справиться с динамическим алгоритмом во что-то вроде O(n^2*m)

Обратите внимание, что с конкретной реализацией все может стать лучше или хуже. Как правило, простые функции должны быть достаточно быстрыми, а однозначные (например, не такие, как a*a*) регулярные выражения лучше.

Answer 4

Чтобы вникнуть в ответ компании, для построения автомата O (2 ^ m) - наихудший случай, хотя он действительно зависит от формы регулярного выражения (для очень простого, соответствующего слову, это в O (m), используя, например, алгоритм Кнута-Морриса-Пратта ).

Answer 5

Зависит от реализации. Какой язык / библиотека / класс? Это может быть лучший случай, но он будет очень специфичным для количества функций в реализации.

Answer 6

Если вы после сопоставления и замены, это подразумевает группирование и обратные ссылки.

Вот пример perl, где группировка и обратные ссылки могут использоваться для решения полной проблемы NP: http://perl.plover.com/NPC/NPC-3SAT.html

Это (в сочетании с несколькими другими теоретическими особенностями) означает, что использование регулярных выражений для сопоставления и подстановки является NP-полным.

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

Answer 7

Вы можете обменять пространство на скорость, построив недетерминированный конечный автомат вместо DFA. Это можно пройти за линейное время. Конечно, в худшем случае для этого может потребоваться O (2 ^ m) места. Я ожидаю, что компромисс будет того стоить.