Сен 29
Регулярные выражения – материалы
Спасибо, всем кто накидал ссылок и материалов по теме, в данной записи я опишу собранное.
Вот некоторые публикации:
- Wu, Manber «A Fast Algorithm For Multi-Pattern Searching» – описание алгоритма и его реализации в виде Agrep с построением NFA на базе регулярных выражений.
- Публикации Gonzalo Navaro и nrgrep – развитие алгоритма построения NFA на базе регулярных выражений, плюс учёт минимальной размерности строк подпадающих под шаблон.
- Parsing Techniques by Grune and Jacobs – описание алгоритма Томпсона на который ссылаются авторы выше.
Самые интересные – это публикации Navaro. Читая его я подтвердился в своих зарождающихся предположениях насчёт учёта минимальной длины строк подпадающей под данное регулярное выражение.
Но что не менее важно так это то как такие решения создаются. Например, минимальный размер подходящий под выражение строки – это метрика, характеристика данного выражения. Наличие символов начала и конца выражения ^ и $ – это также метрики влияющие на то какие строки могут через данные выражения проходить.
Обеспечив предварительную классификацию выражений можно обеспечить разбиение их в коллекции с последующей фильтрацией по данным метрикам на основе которых могут строиться индексы.
Это очень похоже на то что я описывал с построением индексов для исправления опечаток, но случай с регулярными выражениями значительно сложнее.
Ещё одна интересная тема – это оценка предсказуемости поступающих данных и выработка метрик оценки этой предсказуемости.
В любом можно говорить что решение у этой задачи есть, пусть даже и не самое простое.
