Алгоритмы. Регулярные выражений. Пример графика индекса

Как пример, промежуточных результатов,  для построения RE-индексов под катом график и краткое описание индекса.

Пример на графике это результаты распределения выражений в 3-х уровневом иерархическом индексе с использованием 3 групп метрик — двух по 5 метрик и одной из 2-х метрик.

Суммарно в индексе 53384 записи, каждой из которых соответствует не менее одного регулярного выражения. Суммарный объём индекса без оптимизаций, примерно, в 10 раз превышает объём хранения регулярных выражений.

График 1. Распределение записей индекса по числу связанных с ними выражений

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

Всё с оговорками что это matching индекс. Универсальное решение кроется в управляемой иерархии индексов адаптируемой под коллекцию выражений. Где-то будут эффективнее метрики, а где-то алгоритм Ахо-Карасика. Например, в задачах по анализу поисковых логов или распознавания микроблоков в Скиуре — метрики подходят лучше, а вот в задаче классификации объектов по кускам текста (в том числе и тематической классификации) — алгоритм Ахо-Карасика подходит лучше, так как там используются зацепки по статическому тексту, а большая часть регулярных выражений для классификации используют статические блоки.

Сложнее всего в случае IDS. Там далеко не всегда есть возможность ограничить размер блока для сравнения и очень часто используют наиболее «неприятные операторы» — «*», «.» и «?». Впрочем и тут постепенно можно прийти к правильному.