Индексный поиск по регулярным выражениям

Марина Степанова (Акционерное общество «Главный научный инновационный внедренческий центр» (АО «ГНИВЦ») современная IT-компания и ведущий технологический партнёр государственных структур и лидеров российского бизнеса в области комплексной автоматизации сложных бизнес-процессов.)

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

Существует два основных подхода к выполнению поиска по регулярным выражениям с помощью индекса: "FREE indexing engine" [1], основанный на выделении из регулярного выражения непрерывных фрагментов текста, и метод, разработанный для Google Code Search [2], осуществляющий рекурсивный анализ составных частей регулярного выражения, с целью выявления его атрибутов. В целом же оба этих подхода используют инвертированные индексы на основе k-грам (подстрок исходной строки длиной k) и различаются методом извлечения k-грам из исходного выражения для последующего сканирования.

Данный доклад представляет новый метод извлечений k-грам из регулярного выражения, основанный не на анализе исходного регулярного выражения, а на преобразовании соответствующего конечного автомата. Предлагаемый подход позволяет осуществить более полное извлечение k-грам из регулярного выражения, что подтверждается примерами. Разработан патч к модулю pg_trgm СУБД PostgreSQL [3], реализующий данный подход.

Ссылки:

1. Junghoo Cho, Sridhar Rajagopalan "A Fast Regular Expression Indexing Engine" http://oak.cs.ucla.edu/~cho/papers/cho-regex.pdf
2. How Google Code Search Worked http://swtch.com/~rsc/regexp/regexp4.html
3. Патч к модулю pg_trgm СУБД PostgreSQL http://archives.postgresql.org/message-id/CAPpHfduD6EGNise5codBz0KcdDahp7--MhFz_JDD_FRPC7-i=A@mail.gmail.com

Целевая аудитория

Доклад может быть интересен тем, кто использует регулярные выражения в своей работе и интересуется тем, как они работают и что интересного можно с ними сделать. Также я бы посоветовал его тем, кто интересуется развитием СУБД PostgreSQL и её планируемыми новинками, которых нет в других СУБД. Доклад будет включать достаточно вводной информации, чтобы его можно было понять без специальных знаний.