Сложность замены регулярных выражений
https://stackoverflow.com/questions/21669
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Ответа на этот вопрос я нигде не получил.Какова сложность выполнения сопоставления и замены Regex?
Редактировать:Я работаю на питоне.Но хотелось бы узнать в целом о наиболее популярных языках/инструментах (java, perl, sed).
Решение
С чисто теоретической позиции:
Реализация, с которой я знаком, заключается в создании детерминированного конечного автомата для распознавания регулярного выражения.Это делается за O(2^m), где m — размер регулярного выражения, с использованием стандартного алгоритма.Как только это будет построено, прохождение через него строки будет линейным по длине строки — O(n), где n — длина строки.Замена совпадения, найденного в строке, должна иметь постоянное время.
Итак, в целом, я полагаю, O(2^m + n).
Другие советы
Другая теоретическая информация, представляющая возможный интерес.
Для ясности предположим, что стандартное определение регулярного выражения
http://en.wikipedia.org/wiki/Regular_language
из формальной теории языка.Практически это означает, что единственным строительным материалом являются символы алфавита, операторы конкатенации, чередования и закрытия Kleene, а также единицы и нулевые константы (которые появляются по теоретике группы).Как правило, хорошая идея не перегружать этот термин, несмотря на повседневную практику в языках сценариев, что приводит к неоднозначности.
Существует конструкция 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-полной задачей.
Чтобы соответствовать регулярным выражениям с обратными выражениями, мы могли бы использовать обратную связь (мало чем отличается от двигателя Regex Perl), чтобы отслеживать возможные подчинки входного текста T, которые могут быть назначены переменным в R.Есть только подвесы O (| t |^2), которые могут быть назначены любой одной переменной в r.Если в r есть n переменных, то есть O (| t |^2n) возможные задания.После того, как назначение подстроров к переменным исправлено, проблема сводится к простому согласованию регулярного выражения.Следовательно, наихудшая сложность для соответствия регулярным выражениям с обратными выражениями-O (| t |^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...:)
Зависит от того, что вы определяете с помощью регулярного выражения.Если вы разрешите операторы конкатенации, альтернативы и звезды Клини, время действительно может быть O(m*n+m), где m размер регулярного выражения и n длина строки.Вы делаете это, создавая NFA (который является линейным по m), а затем моделировать его, поддерживая набор состояний, в которых вы находитесь, и обновляя его (в O(m)) для каждой введенной буквы.
Вещи, которые затрудняют анализ регулярных выражений:
- круглые скобки и обратные ссылки:захват по-прежнему возможен с вышеупомянутым алгоритмом, хотя его сложность увеличится, поэтому это может быть неосуществимо.Обратные ссылки повышают распознаваемость регулярного выражения, и их сложность очень велика.
- позитивный прогноз:— это просто другое название пересечения, что повышает сложность вышеупомянутого алгоритма до
O(m^2+n) - негативный прогноз:катастрофа для постройки автомата(
O(2^m), возможно, PSPACE-полный).Но все равно можно будет справиться с динамическим алгоритмом примерно так:O(n^2*m)
Обратите внимание, что при конкретной реализации дела могут стать лучше или хуже.Как правило, простые функции должны быть достаточно быстрыми и однозначными (например.не как a*a*) регулярные выражения лучше.
Чтобы углубиться в ответ на вопрос, для построения автомата O(2^m) является наихудшим случаем, хотя на самом деле это зависит от формы регулярного выражения (для очень простого выражения, которое соответствует слову, оно находится в O( м), используя, например, Алгоритм Кнута-Морриса-Пратта).
Зависит от реализации.Какой язык/библиотека/класс?Может быть лучший вариант, но он будет сильно зависеть от количества функций в реализации.
Вы можете обменять пространство на скорость, построив недетерминированный конечный автомат вместо DFA.Это можно пройти за линейное время.Конечно, в худшем случае для этого может потребоваться пространство O(2^m).Я ожидаю, что компромисс того стоит.
Если вам нужны сопоставление и замена, это подразумевает группировку и обратные ссылки.
Вот пример Perl, где группировка и обратные ссылки могут использоваться для решения полной задачи NP: http://perl.plover.com/NPC/NPC-3SAT.html
Это (в сочетании с некоторыми другими теоретическими моментами) означает, что использование регулярных выражений для сопоставления и замены является NP-полным.
Обратите внимание, что это отличается от формального определения регулярного выражения, в котором нет понятия группировки, и соответствует полиномиальному времени, как описано в других ответах.
