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

Ответ 1

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

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

Итак, в общем, я полагаю, что O (2 ^ m + n).

Ответ 2

Другая теоретическая информация о возможном интересе.

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

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

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

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

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

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

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

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

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

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

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

Чтобы согласовать регулярные выражения с обратными запросами детерминистически, мы могли бы использовать backtracking (в отличие от движка regex 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...:)

Ответ 3

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

Вещи, делающие регулярное выражение регулярным выражением сложным:

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

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

Ответ 7

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

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

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

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