Магия множеств регулярных выражений

Моё знакомство с регулярными выражениями началось более чем давно, ещё в то время когда я активно встречал в кодах скриптов и использовал сам для подготовки скриптов при администрировании юникс серверов.

Признаться, особой любви к ним я никогда не испытвал. Лично мне никогда не нравился подобный способ «упаковки правил», иногда их просто сложно читать. Гораздо позже размышляя над принципами анализа HTML и любых иных полуструктурированных данных, моя антипатия к регулярным выражениям сохранилась на прежнем уровне. Зачем использовать медленное и, зачастую неэффективное решение для задач которые могут быть решены другим образом? Что, в общем то, я и сейчас считаю верным — разбор полуструктурированных данных регулярными выражениями на текущем уровне развития алгоритмов и библиотек их анализа — это сущий анахронизм, ко всему ещё и неэффективный и не позволяющий набирать промежуточную статистику, равно как и многие другие возможности.

Но есть и задачи где без регулярных выражений если не невозможно,  но, скажем, отнюдь не просто. Конечно их можно заменить собственными и существующими правилами анализа текста, примеров множество, но собственные правила — это заведомое ограничение на пользователей или операторов вынужденных с этими правилами работать.

Например, всё та же задача сверхбыстрой проверки текста по тысячам и десяткам тысяч регулярных выражений для меня понятна по факту, поскольку я знаю много областей где она более чем актуальна, но другие могут и не знать.

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

При этом существует задача принятия решения или упрощение его принятия с использованием ряда правил и построения дерева решений в конечном итоге.

Особенность в том что анализ строк может происходить как частными алгоритмами, комбинациями правил для каждого рассматриваемого случая, но если есть возможность использования базовых правил общих для большинства случаев, то почему не воспользоваться именно ими?

Регулярные выражения — это и есть такой пример. За счёт того что регулярными выражениями можно описать даже достаточно сложные случаи, они могут использоваться для общий механизм по классификации текстов и принятия решения.

Что вообще такое регулярное выражение? Это набор правил закодированный особым образом дабы сохранить человекочитаемость с одной стороны, а с другой обеспечить необходимую гибкость.

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

Но меня более интересуют не регулярные выражения в общем случае, а случаи когда они применяются массово и, или несколько из них необходимо прогнать по множествам строк, или же поток строк по множеству регулярных выражений.

Далее несколько примеров массового использования регулярных выражений:
1. Антиспам

2. Фильтрация рекламы
3. Фильтры на прокси серверах
4. Системы IDS
5. Системы корпоративного мониторинга потоков информации (мини большой брат)
6. Классификация текстов

плюс ещё огромное множество применений, начиная от поиска (Google Code Search) и заканчивая подсветкой исходного кода.

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

И практически полностью отсутствуют исследования, правила и методики оценок производительности систем фильтров и классификации регулярными выражениями в зависимости от их числа, качества

Вообще мне известно всего две публичные работы на эту тему:

1. RE-Tree: An Efficient Index Structure for Regular Expressions — исследование из Bell Labs для построение индекса выражений путём сведения их к DFA (по русски — конечный предсказуемый автомат). Что жаль так продолжения этих материалов мне найти не удалось, то ли исследования свернули, то перевели в коммерческое русло.

2. esmre — библиотека по оптимизации сравнений текста по индексу регулярных выражений основанная на алгоритме Ахо-Карасика. По небольшому наблюдению за ней, библиотека выискивает куски текста для зацепки и на их основе фильтрует регулярные выражения при поиске текста.

Плюс есть ещё более ранние публикации по преобразовании регулярных выражений в DFA, но они лишь часть решения, если вообще решение именно в этой области.

Плюс ещё ряд публикаций по аппаратной оптимизации исполнения регулярных выражений с помощью плат сопроцессоров и графических процессоров, но сильно они ситуацию не меняют, лишь помогают для некоторых решений вроде аппаратных IDS систем.

Но прорыва нет, сколько я не видел систем — все идут, либо путём оптимизации выражений, либо решают эту задачу написанию собственных правил анализа строк.

В итоге как разрешить эту задачу для меня лично большой вопрос поскольку тема, как оказалось, с огромным числом лакун, но есть ряд идей из смежных областей:

1. При формировании правил ещё на стадии их подготовки создание их в псевдо-языке и компиляция регулярных выражений уже из них. В этом случае DFA и конечность правил мы обеспечиваем ещё до необходимости анализа выражения.

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

3. Использование и развитие алгоритма Ахо-Карасика и реорганизация правил в сторону оптимизации под его использование. Алгоритму нужны куски текста для зацепки соответственно регулярные выражения должны их содержать.

4. Неполная распаковка правил. Аналогично правилу 2, но с тем ограничением что подвергать анализу лишь наиболее простые правила, а более сложные фильтровать и предлагать для реорганизации операторам. В этом случае требуется фильтр и индекс базовых метрик правил.

Наконец а собственно почему меня этот вопрос волнует? В том же Скиуре используется более 160 регулярных выражений и, хотя там и используется ряд хитрых оптимизационных трюков и не сами регулярные выражения, а их сборка по определённым правилам, включая предварительную классификацию и расчёт метрик.

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

About This Author

  • Михаил Едошин

    Почему вы считаете, что регулярные выражения медленные? Это же конечный автомат, во всяком случае, в том простом виде, в котором они существовали изначально, а КА переходит в следующее состояние как только съедает очередной символ и не возвращается назад, так что его сложность O(n) — для алгоритма анализа строки меньше, вроде бы, некуда. Кроме того, если я ничего не путаю, ведь вроде бы есть стандартный метод объединения конечных автоматов, т. е. произвольное количество выражений всегда можно объединить в одно, которому тоже потребуется просмотреть строку только раз. (Сейчас гляну в книжке. ) Ну да, вроде бы не ошибаюсь: можно построить NFA из нескольких DFA, после чего механически преобразовать этот NFA с m состояний в DFA, количество состояний которого теоретически ограничено 2^m, но практически обычно больше только раз в десять.

  • http://ivan.begtin.name ivbeg

    Регулярные выражения — это всё же не DFA, DFA могут быть построены на их основе это да. Специфика в том что подавляющее большинство библиотек по работе с регулярными выражениями скрывают цепочку правил из «распакованного» выражения от конечного пользователя. В итоге да, можно преобразовать регулярное выражение в DFA, но для этого потребуется вначале написать свой парсер регулярных выражений.

    Может быть всё и действительно так просто как Вы описываете, но почему-то до сих пор никто этого не сделал.

    Другая и отдельная тема — это одно дело базовое понимание разложение DFA и NFA, и другое когда доходит до предметной области, а в нашем случае это разбор строк правилами. Например, алгоритм Ахо-Карасика, насколько я знаю, про DFA / NFA ничего не знает, но работает.

  • Михаил Едошин

    Парсер не писал, но простой парсер без выкрутасов, наверное, не очень сложно. Может, кто и делал уже, только найти трудно. (Кстати, поискал только что и вот тут: http://swtch.com/~rsc/regexp/regexp1.html, в принципе, тот же подход, только человек сразу NFA строит, а потом из него DFA делает.) И, наверное, если нужна именно индексация, то все равно эффективнее свой парсер, чтобы он срабатывал в момент совпадения шаблона и обновлял индекс. Кстати, для этого может быть можно использовать генератор парсеров, ведь регулярные выражения — это Type-3-грамматики. Единственное, что там, перегенерация + перекомпиляция после добавления новых правила.

    Ахо-Карасик — это Aho and Corasick bibliographic search algorithm [1975]? Если да, то он как раз основан на использовании DFA для поиска образца в строке, и, насколько я понимаю из описания, там как раз изготовляется NFA, потом из него DFA.

    Вы не читали Parsing Techniques by Grune and Jacobs? (ftp://ftp.cs.vu.nl/pub/dick/PTAPG_1st_Edition/BookBody.pdf) Там пятая глава, по-моему, очень по теме. Только что глянул, алгоритм Томпсона, что по первой ссылке, тоже упоминается; впрочем, неудивительно, он 1968 года все-таки.

  • http://ivan.begtin.name ivbeg

    Про Aho and Corasick Вы правы, это я упустил при его чтении.
    Описание алгоритма Томпсона мне не попадалось, спасибо за ссылку.
    Если Вам интересно, то ещё этой темой занимался Gonzalo Navaro http://www.dcc.uchile.cl/~gnavarro/ и у него есть как публикации, так и реализация (nrgrep) по этой теме.

  • Михаил Едошин

    Я, конечно, может быть, задачу не до конца понимаю, но вот смотрите, что делает обыкновенный наш привычный Lex:

    Lex source is a table of regular expressions and corresponding program fragments. The table is translated to a program which reads an input stream, copying it to an output stream and partitioning the input into strings which match the given expressions. As each such string is recognized the corresponding program fragment is executed. The recognition of the expressions is performed by a deterministic finite automaton generated by Lex. The program fragments written by the user are executed in the order in which the corresponding regular expressions occur in the input stream.

    Т. е. хоть тысячу написать регулярных выражений, Lex их все умнет в один автомат, и потом будет только раз просматривать источник и вызывать нужную подпрограмму на каждом совпадении.

Яндекс.Метрика