Часть 1: метасимволы внутри и вне символьных классов.
В этой части я хотел бы рассказать про то, как же работают движки регулярных выражений, почему некоторые люди считают, что регулярные выражения очень медленные, и почему авторы многих движков не соблюдают стандарт POSIX.
Как во многих задачах, к проблеме «найти совпадение в строке для регулярного выражения» существует множество подходов и принципов её решения. Основных принципов в данном случае 2: поиск совпадений, управляемый регулярным выражением, и поиск совпадений, управляемый строкой. Давайте подробнее рассмотрим, что означает каждый из этих принципов.
Такой тип движков регулярных выражений реализуется с помощью так называемого ДКА (Детерминированный Конечный Автомат). Основным преимуществом является огромная скорость поиска совпадений (по сравнению с другим принципом). Естественно, что данный принцип имеет кучу недостатков (иначе не было бы интересно, правда?).
Во-первых, время компиляции (имеется в виду компиляция регулярного выражения во внутренние структуры движка, а не компиляция исходного кода программы) может быть чрезвычайно велико (по сравнению с другим принципом). По сути, во время компиляции создается целая программа сравнения конкретного паттерна. Поскольку ДКА «управляется» строкой, а строку во время компиляции мы не знаем, то алгоритм создается с учетом всех возможных строк. Для сложного выражения это, очевидно, сделать не так быстро.
Во-вторых, ДКА не поддерживает очень многие удобные и нужные возможности, к которым мы привыкли в регулярных выражениям. Например, не поддерживаются сохраняющие скобки. Конечно, с тем набором, которым располагает ДКА, невозможно обойтись в более-менее реальных ситуациях. Поэтому в чистом виде ДКА сейчас не применяется почти нигде. Зато успешно применяется в так называемых «гибридных» движках, которые в простейшем случае выбирают тот движок, который наиболее подходит для какого-то конкретного регулярного выражения.
Таким образом, если вам нужно произвести поиск в огромном объеме текста и при этом ваше регулярное выражение не слишком сложное, то сложно найти что либо лучше чем ДКА.
Так как же все-таки работает ДКА? Движок называется «управляемый строкой», поскольку он именно так и работает. Конечный автомат считывает строку, в которой надо найти совпадения, и производит сравнения строки с паттерном. В каждый момент времени алгоритм «знает» какие части паттерна и строки совпадают. Когда алгоритм полностью просканирует всю строку, останется выбрать только самое длинное совпадение, находящееся ближе к началу строки и выдать его как ответ.
Для определенности примем, что у нас есть регулярное выражение
Рассмотрим как происходит поиск совпадения в механизме ДКА. Для первой строки имеет следующую последовательность:
Что будет происходить во втором случае:
Что мы можем увидеть на этих двух примерах? Алгоритму все равно есть ли у нас совпадения или нет. Он просто сканирует строку символ за символом и пытается подобрать совпадения на основе паттерна. Если у нас в конце работы будет несколько полных совпадений, то результатом будет то, что расположено ближе к левому краю строки и наиболее длинное.
Собственно, становится понятно почему алгоритм работает так быстро. За исключением некоторых случаев каждый символ строки просматривается только 1 раз. Так же становится понятно почему компиляция паттерна выполняется долго — для сложных паттернов нужно учесть много условий и зависимостей, чтобы правильно вести частичные совпадения.
На данный момент движок ДКА используется в утилите grep в составе механизма выбора движка и в языке Tcl в составе гибридного движка, наверняка используется где-нибудь еще, но я про это не знаю.
Такой тип движков регулярных выражений реализуется с помощью так называемого НКА (Недетерминированный Конечный Автомат). Основным преимуществом является поддержка большого числа функций (по сравнению с другим принципом). Естественно, что данный принцип тоже имеет кучу недостатков.
Во-первых, время работы может быть чрезвычайно велико (по сравнению с другим принципом). Вплоть до экспоненциальной асимптотики от длины входной строки. Многие популярные движки даже имеют защиту от этого, прерывая поиск.
Во-вторых, НКА очень сильно зависит от того как записано регулярное выражение. Если ДКА совершенно все равно на форму записи: время и результаты поиска будут в точности одинаковы для любых эквивалентных выражений, то для НКА это целая проблема. Одно выражение может давать экспоненциальную асимптотику, а другое практически линейную. Соответственно, во весь рост встает вопрос оптимизации паттерна. НКА на данный момент используется в большинстве движков регулярных выражений.
Ключевой особенностью классического НКА является то, что он прерывает поиск как только найдет первое полное совпадение. Т.е. результаты поиска в некоторых случаях будут сильно отличатся от ДКА. Это особенность работы алгоритма.
Так почему же авторы движков не спешат следовать POSIX? Дело в том, что в стандарте закреплена семантика поиска ДКА. Т.е. конечно не сказано буквально, что надо использовать ДКА, но про «самое левое совпадение наибольшей длины» сказано. Но НКА-то возвращает просто первое, а не наибольшей длины. И что же делать? Для того чтобы соответствовать POSIX придумали модификацию алгоритма, которую обычно называют POSIX НКА. И она работает значительно дольше чем просто НКА. Потому что для удовлетворения стандарту приходиться выполнять перебор вообще всех вариантов, которые допускает регулярное выражение. Далее я поясню почему это значительно дольше.
Откомпилированный (значение тоже что и для ДКА) НКА представляет из себя последовательный алгоритм, инструкции, основанные на паттерне. Ключевой особенностью НКА являются «возвраты». От их количества напрямую зависит скорость поиска.
Что такое возвраты лучше всего объяснить на примере. Возьмем те же самые две строки, которые использовали в примере для ДКА, и то же самое регулярное выражение.
Для первой строки:
Что будет происходить во втором случае:
Для большего понимания, расскажу, что квантификатор
На самом деле я немного слукавил, когда описывал как конкретно работает алгоритм. Дело в том, что так он будет работать, если движок применит оптимизации (очевидно, что если паттерн начинается с символа
Отличие движка POSIX НКА будет в том, что в первом случае (когда совпадение найдено) поиск тоже не был бы прекращен, а были бы выполнены все 5 поисков, как и при отсутствии совпадения, что конечно намного дольше.
Теперь, когда мы рассмотрели технику выполнения возвратов, можно догадаться откуда берется экспоненциальное время поиска. В некоторых ситуациях алгоритм попадает в ловушку, создавая огромное количество возвратов. Рассмотрим, например, выражение
Другая ситуация. Представьте текст объемом в 1 мегабайт и паттерн вида
Про техники оптимизации возвратов можно написать еще много чего. Следующую статью я как раз планирую посвятить этому.
По мотивам книги Jeffrey Friedl, Mastering Regular Expressions.
В этой части я хотел бы рассказать про то, как же работают движки регулярных выражений, почему некоторые люди считают, что регулярные выражения очень медленные, и почему авторы многих движков не соблюдают стандарт POSIX.
Как во многих задачах, к проблеме «найти совпадение в строке для регулярного выражения» существует множество подходов и принципов её решения. Основных принципов в данном случае 2: поиск совпадений, управляемый регулярным выражением, и поиск совпадений, управляемый строкой. Давайте подробнее рассмотрим, что означает каждый из этих принципов.
Поиск совпадений, управляемый строкой
Такой тип движков регулярных выражений реализуется с помощью так называемого ДКА (Детерминированный Конечный Автомат). Основным преимуществом является огромная скорость поиска совпадений (по сравнению с другим принципом). Естественно, что данный принцип имеет кучу недостатков (иначе не было бы интересно, правда?).
Во-первых, время компиляции (имеется в виду компиляция регулярного выражения во внутренние структуры движка, а не компиляция исходного кода программы) может быть чрезвычайно велико (по сравнению с другим принципом). По сути, во время компиляции создается целая программа сравнения конкретного паттерна. Поскольку ДКА «управляется» строкой, а строку во время компиляции мы не знаем, то алгоритм создается с учетом всех возможных строк. Для сложного выражения это, очевидно, сделать не так быстро.
Во-вторых, ДКА не поддерживает очень многие удобные и нужные возможности, к которым мы привыкли в регулярных выражениям. Например, не поддерживаются сохраняющие скобки. Конечно, с тем набором, которым располагает ДКА, невозможно обойтись в более-менее реальных ситуациях. Поэтому в чистом виде ДКА сейчас не применяется почти нигде. Зато успешно применяется в так называемых «гибридных» движках, которые в простейшем случае выбирают тот движок, который наиболее подходит для какого-то конкретного регулярного выражения.
Таким образом, если вам нужно произвести поиск в огромном объеме текста и при этом ваше регулярное выражение не слишком сложное, то сложно найти что либо лучше чем ДКА.
Так как же все-таки работает ДКА? Движок называется «управляемый строкой», поскольку он именно так и работает. Конечный автомат считывает строку, в которой надо найти совпадения, и производит сравнения строки с паттерном. В каждый момент времени алгоритм «знает» какие части паттерна и строки совпадают. Когда алгоритм полностью просканирует всю строку, останется выбрать только самое длинное совпадение, находящееся ближе к началу строки и выдать его как ответ.
Для определенности примем, что у нас есть регулярное выражение
^abc\w+e$ и две строки abcde и abce. Вполне очевидно, что с первой строкой выражение совпадет, а со второй нет.Рассмотрим как происходит поиск совпадения в механизме ДКА. Для первой строки имеет следующую последовательность:
- Первый символ строки «a» — совпадает по позиции с метасимволом
^. Найдено 1 частичное совпадение. - Первый символ строки «a» — совпадает по значению со вторым символом паттерна. Алгоритм продолжает вести 1 частичное совпадение.
- Второй символ строки «b» — совпадает по значению с третьим символом паттерна. Алгоритм продолжает вести 1 частичное совпадение.
- Третий символ строки «с» — совпадает по значению с четвертым символом паттерна. Алгоритм продолжает вести 1 частичное совпадение.
- Четвертый символ строки «d» — совпадает по значению с пятым метасимволом
\wпаттерна. Квантификатор требует, чтобы совпадение метасимвола встретилось хотя бы один раз. Условие выполнено. Алгоритм продолжает вести 1 частичное совпадение. - Пятый символ строки «е» — совпадает по значению с восьмым символом паттерна. Условие квантификатора для предыдущего метасимвола выполнено, мы можем засчитать символ «е» как совпадение с восьмым символом паттерна, либо как совпадение с метасимволом
\w. Алгоритм делает и то и то, и продолжает вести уже 2 частичных совпадения. Запомните этот момент, в другом принципе тут будет очень существенное отличие. - Шестой символ строки отсутствует — совпадает по позиции с метасимволом
$. Найдено 1 полное совпадение, а второе частичное не оправдывает ожиданий и отбрасывается. - Строка закончилась, возвращаем результат.
Что будет происходить во втором случае:
- Начало работы алгоритма точно такое же, сразу переходим к четвертому символу строки «е»
- Четвертый символ строки «е» — совпадает по значению с пятым метасимволом паттерна
\w. Условие квантификатора требует, чтобы существовало хотя бы одно совпадение с символом. Поэтому «е» захватывается метасимволом\w. 1 частичное совпадение. - Пятый символ строки отсутствует — совпадения с символом «е» паттерна нет. Очевидно, что строка не совпадает.
- Строка закончилась, совпадений нет, возвращаем результат.
Что мы можем увидеть на этих двух примерах? Алгоритму все равно есть ли у нас совпадения или нет. Он просто сканирует строку символ за символом и пытается подобрать совпадения на основе паттерна. Если у нас в конце работы будет несколько полных совпадений, то результатом будет то, что расположено ближе к левому краю строки и наиболее длинное.
Собственно, становится понятно почему алгоритм работает так быстро. За исключением некоторых случаев каждый символ строки просматривается только 1 раз. Так же становится понятно почему компиляция паттерна выполняется долго — для сложных паттернов нужно учесть много условий и зависимостей, чтобы правильно вести частичные совпадения.
На данный момент движок ДКА используется в утилите grep в составе механизма выбора движка и в языке Tcl в составе гибридного движка, наверняка используется где-нибудь еще, но я про это не знаю.
Поиск совпадений, управляемый регулярным выражением
Такой тип движков регулярных выражений реализуется с помощью так называемого НКА (Недетерминированный Конечный Автомат). Основным преимуществом является поддержка большого числа функций (по сравнению с другим принципом). Естественно, что данный принцип тоже имеет кучу недостатков.
Во-первых, время работы может быть чрезвычайно велико (по сравнению с другим принципом). Вплоть до экспоненциальной асимптотики от длины входной строки. Многие популярные движки даже имеют защиту от этого, прерывая поиск.
Во-вторых, НКА очень сильно зависит от того как записано регулярное выражение. Если ДКА совершенно все равно на форму записи: время и результаты поиска будут в точности одинаковы для любых эквивалентных выражений, то для НКА это целая проблема. Одно выражение может давать экспоненциальную асимптотику, а другое практически линейную. Соответственно, во весь рост встает вопрос оптимизации паттерна. НКА на данный момент используется в большинстве движков регулярных выражений.
Ключевой особенностью классического НКА является то, что он прерывает поиск как только найдет первое полное совпадение. Т.е. результаты поиска в некоторых случаях будут сильно отличатся от ДКА. Это особенность работы алгоритма.
Так почему же авторы движков не спешат следовать POSIX? Дело в том, что в стандарте закреплена семантика поиска ДКА. Т.е. конечно не сказано буквально, что надо использовать ДКА, но про «самое левое совпадение наибольшей длины» сказано. Но НКА-то возвращает просто первое, а не наибольшей длины. И что же делать? Для того чтобы соответствовать POSIX придумали модификацию алгоритма, которую обычно называют POSIX НКА. И она работает значительно дольше чем просто НКА. Потому что для удовлетворения стандарту приходиться выполнять перебор вообще всех вариантов, которые допускает регулярное выражение. Далее я поясню почему это значительно дольше.
Откомпилированный (значение тоже что и для ДКА) НКА представляет из себя последовательный алгоритм, инструкции, основанные на паттерне. Ключевой особенностью НКА являются «возвраты». От их количества напрямую зависит скорость поиска.
Что такое возвраты лучше всего объяснить на примере. Возьмем те же самые две строки, которые использовали в примере для ДКА, и то же самое регулярное выражение.
Для первой строки:
- Первый метасимвол паттерна
^— совпадает по позиции с началом строки. Стек возвратов пуст. - Второй символ паттерна «a» — совпадает по значению с первым символом строки. Стек возвратов пуст.
- Третий символ паттерна «b» — совпадает по значению со вторым символом строки. Стек возвратов пуст.
- Четвертый символ паттерна «с» — совпадает по значению с третьим символом строки. Стек возвратов пуст.
- Пятый метасимвол строки
\w— совпадает по значению с четвертым символом строки. Квантификатор требует наличия хотя бы одного символа, поэтому возврата быть не может. Стек возвратов пуст. - Пятый метасимвол строки
\w— совпадает по значению с пятым символом строки. Квантификатор требует наличия хотя бы одного символа, который уже был захвачен. В этой точке может быть возврат. Стек возвратов содержит 1 элемент.
На данном промежуточном этапе НКА нашел как совпадение всю строки «abcde», но еще не прошел паттерн до конца. Текущая позиция в строке находится за символом «е», хотя сам символ «е» из паттерна еще не совпал. Именно в этой точке начнется самое интересное. Следите за руками. - Восьмой символ паттерна «е» — не совпадает по значению с шестым символом строки (его просто нет). Совпадение не найдено. Проверяем стек возвратов — имеется одна запись. Выполняем возврат. После возврата мы находимся в позиции «перед символом е» в строке и в позиции «перед символом е» в паттерне. Стек возвратов пуст.
Когда НКА не находит совпадение, он проверяет стек возвратов. При выполнении возврата восстанавливается позиция в строке и возврат удаляется из стека. Если стек возвратов пуст, а совпадения нет, то считается, что совпадений с данной начальной позиции в строке нет.
- Восьмой символ паттерна «е» — совпадает по значению с пятым символом строки. Стек возвратов пуст.
- Девятый метасимвол паттерна
$— совпадает по позиции с концом строки. Стек возвратов пуст. - Паттерн закончился, совпадение на данный момент есть. Возвращаем его.
Что будет происходить во втором случае:
- Начало работы алгоритма точно такое же, сразу переходим к восьмому символу паттерна «e».
- Восьмой символ паттерна «е» — не совпадает по значению с пятым символом строки (его опять просто нет). Совпадение не найдено. Проверяем стек возвратов — он пуст (пуст потому что на предыдущем этапе мы не вносили ничего в стек возвратов, потому что квантификатор
+требует наличие хотя бы одного совпадения). Выполнить возврат нельзя. Строка не совпала, возвращаем результат.
Для большего понимания, расскажу, что квантификатор
+ всегда захватывает столько символов строки сколько сможет. Поэтому он называется максимальный. С этим связана частая ошибка новичков. Паттерн \(.+\) совпадет в строке «тут текст (скобочка) а тут еще текст (еще скобочка) и тут текст» с частью «(скобочка) а тут еще текст (еще скобочка)», а вовсе не со «(скобочка)». Просто потому что на этапе обработки .+ будет захвачена вся строка до конца, и как только при выполнении возвратов мы дойдем до символа «)», так сразу будет найдено полное совпадение. Немного изменим регулярное выражение: \([^)]+\) и теперь в нем нет уже проблемы, которая нам мешала. Но появилась другая (а как же без этого). Теперь в строке «тут текст (скобочка (а внутри еще одна скобочка) ну и снова текст) а тут еще текст» будет захвачено «(скобочка (а внутри еще одна скобочка)», что тоже конечно не правильно. Это произойдет потому, что на этапе захвата, мы не дойдем до второй закрывающейся скобки и сразу же вернем найденное совпадение на первой. Не буду рассматривать дальше этот пример, поскольку в общем случае проблему сбалансированных скобок нельзя решить только с помощью регулярных выражений. В .NET есть специальная конструкция, которая позволяет решить задачу проверки сбалансированности (именно проверки).На самом деле я немного слукавил, когда описывал как конкретно работает алгоритм. Дело в том, что так он будет работать, если движок применит оптимизации (очевидно, что если паттерн начинается с символа
^, то либо он совпадет в начале строки, либо вообще не совпадет). На самом деле, если отбросить оптимизации, то движок выполнит в точности такой же поиск начиная с каждого следующего символа строки, если не найдет ни одного полного совпадения на предыдущем шаге. Т.е. для второй строки будет выполнено 5 поисков подряд (начинаем перед символом «a», потом «b», «c», «e» и последний за символом «e»), и только после этого можно будет сказать, что совпадений нет. ДКА бы расправился со всеми случаями за 1 проход. А вот НКА при отсутствии совпадений понадобится 5.Отличие движка POSIX НКА будет в том, что в первом случае (когда совпадение найдено) поиск тоже не был бы прекращен, а были бы выполнены все 5 поисков, как и при отсутствии совпадения, что конечно намного дольше.
Теперь, когда мы рассмотрели технику выполнения возвратов, можно догадаться откуда берется экспоненциальное время поиска. В некоторых ситуациях алгоритм попадает в ловушку, создавая огромное количество возвратов. Рассмотрим, например, выражение
(\w+)*a. Если применить его к строке «bbb», то что произойдет? Сначала первый квантификатор + захватит всю строку и передаст управление второму квантификатору. Поскольку больше символов в строке нет, то переходим к символу «а» паттерна. Которого нет в строке, выполняем возврат на один символ, перезахватываем освободившийся символ в новую группу, проверяем «a», совпадение опять нет, возврат. Дальше смысл должен быть понятен. Алгоритм переберет все возможные разбиения строки для захвата двумя квантификаторами. Для строки «bbb» это будут варианты: «[bbb]», «[bb][b]», «[b][bb]», «[b][b][b]». Где квадратные скобки условно обозначают захваченную группу. Количество разбиений растет экспоненциально от длины строки в данном случае.Другая ситуация. Представьте текст объемом в 1 мегабайт и паттерн вида
.*a. Что произойдет при поиске? На каждом этапе будет захватываться весь мегабайт строки и выполняться последовательные возвраты пока не будет найден символ «a». А если такого символа в строке нет? Тогда будет всего-то выполнен 1000001 поиск. Который каждый раз будет захватывать всю строку от текущего символа до конца и возвращаться по ней пока не найдет символ «a» (которого нет). Для того чтобы этого избежать достаточно в данном случае было бы написать [^a]*a. Но это для данного случае. В общем случае (как в примере со скобками) этого недостаточно.Про техники оптимизации возвратов можно написать еще много чего. Следующую статью я как раз планирую посвятить этому.
По мотивам книги Jeffrey Friedl, Mastering Regular Expressions.