Аннотация доклада.

Регулярные выражения — мощный и широко применяемый инструмент обработки текстовых данных. При поиске по регулярному выражению в большом наборе строк, становится актуальным вопрос о применении индекса. В то же время использование индексов для поиска по регулярному выражению – нетривиальная задача. Существует два основных подхода к выполнению поиска по регулярным выражениям с помощью индекса: «FREE indexing engine», основанный на выделении из регулярного выражения непрерывных фрагментов текста, а также метод, разработанный для Google Code Search, осуществляющий рекурсивный анализ составных частей регулярного выражения, с целью выявления его атрибутов. В целом оба этих подхода используют обратные индексы на основе k-грам (подстрок исходной строки длины k) и различаются методом извлечения k-грам из регулярного выражения для последующего поиска по индексу. Данный доклад представляет новый метод извлечений k-грам из регулярного выражения, основанный не на анализе исходного регулярного выражения, а на преобразовании соответствующего конечного автомата. Предлагаемый подход позволяет осуществить более полное извлечение k-грам из регулярного выражения, что подтверждается примерами. Данный подход был реализован в модуле pg_trgm СУБД PostgreSQL 9.3.