AloneCoder Nov 10 2015 at 15:14

Поиск с помощью регулярных выражений может быть простым и быстрым

21 min

48K

VK corporate blogPerl*Algorithms*Regular expressions*

Translation

+73

Comments 14

excoder Nov 10 2015 at 15:22

А где же ссылка на re2? Это ведь как раз про неё. Она особенно быстра, если знать, как её оттюнить внутри. Статья 2007 года, но думаю качественные характеристики не потеряли своей актуальности.

divanikus Nov 10 2015 at 15:50

Различия реализаций регулярок на ДКА и НКА еще в той самой книжке Фридла были рассмотрены. Насколько я помню, со скоростью приходят некоторые ограничения.

mtyurin Nov 10 2015 at 15:52

http://www.depesz.com/2013/04/10/waiting-for-9-3-support-indexing-of-regular-expression-searches-in-contribpg_trgm/

sebres Nov 11 2015 at 02:03

Кстати да, а если учесть что pg (как и tcl) юзает традиционный NFA regex engine, то все просто замечательно с ним.
А чего там кстати люди ждут — обыкновенный calc index (aka «index on expression») по функции regexp_matches не поможет? (всю простыню по ссылке выше времени нет осилить)

seriyPS Nov 11 2015 at 14:36

По ссылке используется GIN индекс для поиска по произвольному регулярному выражению. Индекс делаешь один раз на колонку, а потом можешь по нему любыми регулярками искать.

yar3333 Nov 10 2015 at 19:08

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

excoder Nov 10 2015 at 20:23

Можно потом этот автомат преобразовать: удалить лямбда-переходы (или построить сразу автомат Глушкова), минимизировать его. У автора в re2, насколько я помню, делается так: определяется доля автомата, начиная с которой строится НКА, соединяющий несколько ДКА. Регулируя это, можно управлять trade-off «размер автомата» vs «эффективность».

RolexStrider Nov 10 2015 at 23:22

Выходит что PCRE с его мудреным оптимизатором и JIT прям в машинный код под кучу архитектур — чуть ли не самый тормоз?

encyclopedist Nov 10 2015 at 23:39

Не все возможности PCRE можно реализовать в описанном в статье подходе.

Regis Dec 3 2015 at 13:35

Там может стоило бы сделать, чтобы конкретная реализация выбиралась динамически в зависимости от реального содержимого регулярки?

encyclopedist Dec 3 2015 at 13:49

Да, и автор как раз призывает использовать такой подход:

Но даже в этом случае есть смысл использовать для большинства РВ алгоритм Thompson NFA, применяя бэктрекинг лишь в случае необходимости. Лучше всего прибегать к бэктрекингу только для размещения обратных ссылок.

dtestyk Nov 11 2015 at 07:19

Можно вопрос, а как обстоят дела со скоростью у движков javascript по сравнению с остальными?

bolk Nov 11 2015 at 08:11

Вот кстати, быстрые регулярки, которые НФА Томпсона тоже используют: github.com/BeRo1985/flre

naething Nov 11 2015 at 08:31

Перевод некачественный, пришлось читать оригинал. Например, в самом начале статьи:

В первом случае поиск занимает A?ⁿAⁿ времени, во втором — Aⁿ.

В оригинале:

Time to match a?ⁿaⁿ against aⁿ

то есть, «Время на поиск выражения a?ⁿaⁿ в строке aⁿ». То есть, оба графика показывают результаты одного и того же эксперимента, проведенного для двух разных алгоритмов. По-моему, переводчик вообще не понял, о чем речь :)