My<cod/>.net
Сложность замены Regex
Ответа на этот вопрос я нигде не получил. Какова сложность выполнения Regex-го совпадения и замены?
Edit: я работаю в python. Но хотелось бы знать в целом о самых популярных языках / инструментах (java, perl, sed).
С чисто теоретической точки зрения:
Реализация, с которой я знаком, состояла бы в построении детерминированного конечного автомата для распознавания regex. Это делается в O (2^m), m-размер regex, используя стандартный алгоритм. Как только это будет построено, запуск строки через него будет линейным по длине строки - O(n), n-длина строки. Замена на совпадение, найденное в строке, должна быть постоянной по времени.
Так что в целом, я полагаю, O (2^m + n).
Другая теоретическая информация, представляющая возможный интерес.
Для ясности предположим стандартное определение для регулярного выражения
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-полной задачей.
Чтобы сопоставить регулярные выражения с обратными связями детерминистически мы могли бы используйте backtracking (не похожий на двигатель Perl regex) для того чтобы держать след возможные подслова входного текста t, которые могут быть назначены переменным в r. Есть только O (|t|^2) подслова, которые могут быть назначены любой переменной в 47-м году. Если в r есть n переменных, то возможно O(|t|^2n) назначения. Как только назначение подстрок переменным фиксировано, то проблема сводится к простому совпадению регулярных выражений. Поэтому то наихудшая сложность для сопоставления регулярных выражений с обратными ссылками заключается в следующем O(|t / ^2n).
Однако обратите внимание, что регулярные выражения с обратными ссылками еще не созданы полнофункциональный regexen.
Возьмем, например, символ "don't care" отдельно от любого другого операторы. Существует несколько полиномиальных алгоритмов, решающих, является ли набор шаблоны соответствуют входному тексту. Например, Кучеров и Русинович
http://dx.doi.org/10.1007/3-540-60044-2_46
определите шаблон как слово w_1@w_2@...@w_n, где каждое w_i-это слово (не регулярное выражение), а " @ " - символ переменной длины "don't care", не содержащийся ни в одном из w_i. они выводят алгоритм O((|t| + |P|) log |P|) для сопоставления набора шаблонов P с входным текстом t, где |t| - длина текста, а |P| - длина всех слов в P.
Было бы интересно узнать, как эти меры сложности сочетаются и что является ли мера сложности задачи согласования для регулярных выражений с backreferences, "don't care" и другие интересные особенности практического применения регулярное выражение.
Увы, я ни словом не обмолвился о Python... :)
Зависит от того, что вы определяете под regex. Если вы разрешите операторы конкатенации, альтернативы и Клейн-стар, то время действительно может быть O(m*n+m), где m -размер regex и n -длина строки. Вы делаете это, построив NFA (то есть линейный в m), а затем имитируя его, поддерживая набор состояний, в которых вы находитесь, и обновляя его (в O(m) ) для каждой буквы ввода.
Вещи, которые затрудняют разбор regex:
- скобки и обратные ссылки: захват все еще OK с вышеупомянутым алгоритмом, хотя он будет иметь более высокую сложность, так что это может быть невозможно. Обратные связи повышают способность распознавания regex, и его сложность хорошо
- позитивный взгляд вперед: это просто еще одно название для пересечения, которое повышает сложность вышеупомянутого алгоритма до
O(m^2+n) - негативный взгляд вперед: катастрофа для построения автомата (
O(2^m), возможно PSPACE-полный). Но все же должна быть возможность справиться с динамическим алгоритмом в чем-то вродеO(n^2*m)
Обратите внимание, что при конкретной реализации все может стать лучше или хуже. Как правило, простые функции должны быть достаточно быстрыми и однозначными (например. не так, как a*a* ) regexes лучше.
Чтобы углубиться в ответ предприятия, для построения автомата O(2^m) является наихудшим случаем, хотя это действительно зависит от формы регулярного выражения (для очень простого, которое соответствует слову, оно находится в O(m), используя, например, алгоритм Knuth-Morris-Pratt ).
Если вы ищете сопоставление и подстановку, это подразумевает группировку и обратные ссылки.
Вот пример perl, где группировка и обратные связи могут быть использованы для решения полной задачи NP: http://perl.plover.com/NPC/NPC-3SAT.html
Это (в сочетании с несколькими другими теоретическими лакомыми кусочками) означает, что использование регулярных выражений для сопоставления и подстановки является NP-полным.
Обратите внимание, что это отличается от формального определения регулярного выражения, которое не имеет понятия группировки, и соответствует полиномиальному времени, как описано в других ответах.