Сложность замены Regex

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

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

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

В целом, я полагаю, O (2 ^ m + n).

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

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

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

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

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

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

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

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

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-полная, что доказал Ахо

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

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

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

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

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

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

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

В библиотеке Python re, даже если регулярное выражение скомпилировано, сложность в некоторых случаях может быть экспоненциальной (по длине строки), поскольку она не построена на DFA. Некоторые ссылки здесь, здесь или здесь.