Техническое: про регулярные выражения и Яндекс PIRE

Что-то давно я не писал про технологии и алгоритмы.

А тем временем, на днях, представители Яндекса выложили в открытый доступ ряд open source проектов — http://clubs.ya.ru/company/replies.xml?item_no=30753

Самый интересный из которых, на мой взгляд — это PIRE, https://github.com/dprokoptsev/pire Perl Incompatible Regular Expressions Library.

Весьма интересная штука для тех кто когда либо прогонял через шаблоны большие объёмы текста/файлов/сетевого трафика и прочего файлового счастья.

Как я понимаю авторы обещают производительность до 400MB в секунду на «common hardware», конечно, с кучей ограничений по тому что в регулярных выражениях может быть, но тем не менее — это быстро. Жаль там нет враппера для Питона, я бы попробовал на своих данных, благо их у меня накопилось много и есть с чем сравнивать. Пока поверю авторам на слово и исхожу из того что это так и есть, благо подход описанный у них в документации вполне понятен и должен работать.

Однако, жаль что подобных открытых разработок небыло хотя бы пары лет назад. Когда я разрабатывал Скиур — http://www.skyur.ru (это такой сервис по преобразованию веб-страниц в RSS), то решал задачи для которых как раз были необходимы такие инструменты  поскольку частью алгоритма является большое число тогда ещё регулярных выражений. В совокупности чуть менее 200, точно не скажу поскольку происходит их сборка из некого базового набора.

Но не имея таких инструментов я пошёл другим путём с решением «в лоб», также оказавшего эффективным.

1. Все регулярные выражения были заменены на конечные автоматы

2. Собственно автоматы проанализированы и разбиты на повторяющиеся блоки.

3. Окончательная сборка шаблонов производится из группы базовых автоматов с добавлением к ним дополнительных блоков по набору правил.

4. На основе базовых шаблонов вручную формируется набор базовых правил заменяющих индекс. Фактически это замена для того же esmre для регулярных выражений. Которую, конечно, можно в дальнейшем автоматизировать.

То есть, фактически, это путь эффективен только в случае:

a.  Управляемости входного потока выражений.

б. Возможности разделения регулярные выражения на простые блоки и высокой повторяемости этих блоков.

Лично я нашёл что PyParsing — http://pyparsing.wikispaces.com при соблюдении описанных выше действий обеспечивает ускорение сравнения по сравнению с регулярными выражениями в разы. Собственно он и является весьма удобным конструктором.

Впрочем был бы PIRE или его аналог, пришлось бы гораздо проще. Впрочем и сейчас немало задач для которых такой инструмент необходим. Начиная от контроля сетевого трафика, задач из области поиска доказательств на компьютерах пользователей, классификационных задач, разбора различных полуструктурированных данных и так далее.

About This Author

Яндекс.Метрика