C++ быстрые регулярные выражения

#cpp #регулярные_выражения #boost

нужно прогнать по тексту 2000 строк 200 регулярных выражений на совпадение.
какой движок дает наибольшую скорость ?

как оптимизировать настройку регулярных выражений С++ ?
    

Ответы

Ответ 1

Нужно различать скорость в среднем и скорость в худшем случаях. Большинство современных
движков регулярных выражений основаны на переборе с возвратом, поэтому в патологических
случаях они работают за экспоненциальное время, и одно простое регулярное выражение
на одной строке в какую-то сотню символов не завершится при вашей жизни. Но, хочу заметить,
что такие патологические случаи в реальной жизни маловероятны. С другой стороны, если
у вас нет контроля над входными данными (то есть они, например, поступают извне, от
конечного пользователя), злоумышленник вполне может сделать такой случай реальностью.

Есть другой класс движков, ныне мало распространенных в библиотеках языков программирования,
которые основаны на эмуляции конечных автоматов. Наиболее современная из относительно
распространенных сейчас -- re2 от Russ Cox. Более того, есть отличная статья от него
же, которая раскрывает суть проблемы реализации движков регулярных выражений с помощью
перебора с возвратом. Но опять же, на ваших данных эта библиотека может работать хуже,
чем обычные движки, тут скорее вопрос, контролируете ли вы эти данные или нет. Ну и
стоит учесть, что в re2 не реализованы обратные ссылки (их добавление делает язык,
описываемый "регулярными выражениями", не регулярным, поэтому эмуляцией конечных автоматов
тут не обойтись).

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