Всем известно, что регулярные выражения — мощный инструмент обработки текстовых данных. При работе с большими наборами строк становится актуальной задача быстрого поиска по регулярному выражению в этом наборе. Осуществление такого поиска с помощью индекса — сложная задача.
Существует два основных подхода к выполнению поиска по регулярным выражениям с помощью индекса: "FREE indexing engine" [1], основанный на выделении из регулярного выражения непрерывных фрагментов текста, и метод, разработанный для Google Code Search [2], осуществляющий рекурсивный анализ составных частей регулярного выражения, с целью выявления его атрибутов. В целом же оба этих подхода используют инвертированные индексы на основе k-грам (подстрок исходной строки длиной k) и различаются методом извлечения k-грам из исходного выражения для последующего сканирования.
Данный доклад представляет новый метод извлечений k-грам из регулярного выражения, основанный не на анализе исходного регулярного выражения, а на преобразовании соответствующего конечного автомата. Предлагаемый подход позволяет осуществить более полное извлечение k-грам из регулярного выражения, что подтверждается примерами. Разработан патч к модулю pg_trgm СУБД PostgreSQL [3], реализующий данный подход.
Ссылки:
Целевая аудитория
Доклад может быть интересен тем, кто использует регулярные выражения в своей работе и интересуется тем, как они работают и что интересного можно с ними сделать. Также я бы посоветовал его тем, кто интересуется развитием СУБД PostgreSQL и её планируемыми новинками, которых нет в других СУБД. Доклад будет включать достаточно вводной информации, чтобы его можно было понять без специальных знаний.