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

Всем известно, что регулярные выражения — мощный инструмент обработки текстовых данных. При работе с большими наборами строк становится актуальной задача быстрого поиска по регулярному выражению в этом наборе. Осуществление такого поиска с помощью индекса — сложная задача. Существует два основных подхода к выполнению поиска по регулярным выражениям с помощью индекса: "FREE indexing engine" [1], основанный на выделении из регулярного выражения непрерывных фрагментов текста, и метод, разработанный для Google Code Search [2], осуществляющий рекурсивный анализ составных частей регулярного выражения, с целью выявления его атрибутов. В целом же оба этих подхода используют инвертированные индексы на основе k-грам (подстрок исходной строки длиной k) и различаются методом извлечения k-грам из исходного выражения для последующего сканирования. Данный доклад представляет новый метод извлечений k-грам из регулярного выражения, основанный не на анализе исходного регулярного выражения, а на преобразовании соответствующего конечного автомата. Предлагаемый подход позволяет осуществить более полное извлечение k-грам из регулярного выражения, что подтверждается примерами. Разработан патч к модулю pg_trgm СУБД PostgreSQL [3], реализующий данный подход. Ссылки: Junghoo Cho, Sridhar Rajagopalan "A Fast Regular Expression Indexing Engine" http://oak.cs.ucla.edu/~cho/papers/cho-regex.pdf How Google Code Search Worked http://swtch.com/~rsc/regexp/regexp4.html Патч к модулю pg_trgm СУБД PostgreSQL http://archives.postgresql.org/message-id/CAPpHfduD6EGNise5codBz0KcdDahp7--MhFz_JDD_FRPC7-i=A@mail.gmail.com Целевая аудитория Доклад может быть интересен тем, кто использует регулярные выражения в своей работе и интересуется тем, как они работают и что интересного можно с ними сделать. Также я бы посоветовал его тем, кто интересуется развитием СУБД PostgreSQL и её планируемыми новинками, которых нет в других СУБД. Доклад будет включать достаточно вводной информации, чтобы его можно было понять без специальных знаний.