Алгоритмы. Регулярные выражения. Оценка сложности

Под катом продолжение рассуждение на тему анализа регулярных выражений.

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

Так в выражениях используемых в Скиуре фильтр только по двум метрикам даёт отсев примерно 80% всех выражений и ускорение в проверке ими от 2.5 до 4 раз. Причём там есть что оптимизировать на уровне реализации, но в любом случае оценки от 2.5 до 4 будут вполне корректны. Почему не в 5 раз? Потому как сами движки регулярных выражений, на самом деле, некоторые проверки в себя включают, но там они заведомо медленнее так как необходимо знать детали реализации и где именно в них проверки закладываются чтобы понять их эффективность. Добавлю что в данном случае метрики выражениям прописывались вручную, так как разработка алгоритма их извлечения это само по себе непростая задача.

Но даже это ускорение в 2.5 — 4 раза — это очень мало. Чрезвычайно мало поскольку, к примеру, при 10 000 регулярных выражениях ускорение в 4 раза будет 2500 выражений что невероятно много и дорого для потоковой обработки и для каких-то более менее осмысленных сравнений необходимо уметь сокращать выборку до 0.5-1%. К слову об опечатках — там это достигается, но достигается за счёт того что правила фильтрации построены не на отсеве всех неподходящих, а на поиске подходящих с возможностью рассечения вариантов очередной метрикой на каждом из уровней и построением дерева решений.

И некоторые усреднённые цифры с оговоркой частного случая как выражений так и входного потока:

* при проверке 2-мя метриками полностью отсеивается до 77% всех входных данных;

* для 24.9% входных данных отсеивается до 80% всех выражений;

* для 0.01 отсеивается около 30% регулярных выражений.

Итого при проверке веб страницы из которой извлечено 2103 строки коллекцией из 171 одного регулярного выражения производится не более чем 9115 проверок при 359613 возможных. Иначе говоря фильтр позволяет сократить перебор значений в 40 раз. Но, вернувшись назад к значению в ускрение в 2.5-4 раза, можно быть уверенными что дело не только в количестве сравнений, но и в их стоимости и видно что фильтры отсеивают, в основном, «дешёвые сравнения», а «дорогие» наоборот оставляют. Это ещё одна причина для сбора статистики сравнений и мониторинге производительности сравнения.

Если перейти от задач которые интересны мне как-то классификация с помощью РВ к задачам практического толка как то фильтрация контента или правила IDS, то там ещё сложнее поскольку там не проверка участка на соответствие правилу, а поиск.

Но то что универсальное решение существует — я уверен.