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

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

Признаться, особой любви к ним я никогда не испытвал. Лично мне никогда не нравился подобный способ «упаковки правил», иногда их просто сложно читать. Гораздо позже размышляя над принципами анализа 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

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