Ещё о регулярных выражениях и их анализе

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

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

Для анализа должно быть достаточно развёртывания регулярных выражений как дерева в соответствии с их написанием и последовательное построение «шаблонов шаблонов», которые, как окажется, будут состоять из вполне измеримых «микроблоков правил». Причём каждый из этих микроблоков будет обладать собственным набором метрик. Итоговое дерево выражения будет состоять из ветвей непосредственно правил подвергнутых группировке и кластеризации и рассчитанных ветвей метрик для каждого. При этом несмотря на то что хранение этих метрик может оказаться накладным процессом, тем не менее эти объёмы будут несравнимо меньше чем объёмы «распакованных» NFA.

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

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

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