Регулярные выражения с поддержкой O (N) и обратных ссылок

Question

Как вы, возможно, знаете, существует два разных типа реализаций регулярных выражений: одна использует возвратный путь (pcre), а другая - конечные автоматы (re2).

Оба этих алгоритма имеют свои ограничения: в определенных случаях pcre может потребоваться экспоненциальное время для поиска соответствия, а конечные автоматы не поддерживают обратные ссылки.

Реализация Pcre поддерживает обратные ссылки, очень неэффективные в сопоставлении выражений, таких как /a?a?a?a?aaaa/ с aaaa, чем больше выражение и ввод a имеют - тем дольше это займет, а с 30+ из них это займет много если время.

Версия с конечными автоматами прекрасно справляется со всеми этими реализациями и имеет O (N) сложность ввода, но не поддерживает обратные ссылки:

пкр времени против сложных выражений - http://i.stack.imgur.com/D4gkC.png NFA обрабатывает их, но не поддерживает обратные ссылки - http://i.stack.imgur.com/t2EwI.png

Некоторая информация о поддержке обратных ссылок:

RE2 - http://code.google.com/p/re2/

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

Томпсон НФА - http://swtch.com/~rsc/regexp/regexp1.html

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

Итак, я создал свою собственную версию, которая поддерживает обратные ссылки и имеет сложность O (N). Он написан на языке Haskell и содержит около 600 строк (из них ~ 200 пустых и объявления типа ~ 200, которые можно пропустить). Он пережевывает /a?a?aa/ против aa (с 100 a) примерно за 10 секунд, и, насколько я знаю, это единственная версия, которая может соответствовать

/a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?(a?a?a?a?a?a?a?a?a?a?aaaaaaaaaa)aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\1/

против

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

в нормальное (около 10 секунд) время. Конечно, он поддерживает все другие функции, перечисленные в базовой спецификации регулярных выражений, которые я нашел где-то в Интернете.

Вопрос в том, действительно ли это "главная новость для компьютерных ученых" и что мне делать, если это так?

PS: я покажу источники примерно через неделю - я все еще хочу запустить некоторые тесты с профилировщиком и заменить несколько внутренних структур данных.

Answer 1

Я полагаю, вы в замешательстве. Все регулярные выражения могут быть представлены дискретными конечными автоматами (DFA) и (из-за этого) могут быть решены за O (n) времени. Регулярные выражения Perl (PREG) (и библиотеки регулярных выражений, предоставляемые многими языками) соответствуют языку, который больше регулярных выражений, то есть: в PREG существуют регулярные выражения.

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

Кроме того, никому не нравится тот, кто говорит: «Я могу сделать это, и это удивительно, но я не буду объяснять, как». Одной этой причины достаточно, чтобы не верить вам (игнорируя то, что вы неправильно понимаете, что такое регулярное выражение).

Answer 2

Ваш предложенный тестовый пример не совпадает.Вы не включаете достаточно a s, чтобы соответствовать обратной ссылке (только достаточно, чтобы соответствовать только до обратной ссылки).Если я добавлю еще 10 a с, чтобы они совпадали, сопоставитель регулярных выражений в glibc мгновенно сообщает об успехе

$ echo aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa | sed -re \
    '/a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?(a?a?a?a?a?a?a?a?a?a?aaaaaaaaaa)aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\1/!d'
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Answer 3

Вы можете проверить статью по этой ссылке, кажется, это уже сделал кто-то еще:

Сопоставление регулярных выражений может быть простым и быстрым (но медленно в Java, Perl, PHP, Python, Ruby, ...)

Answer 4

Функциональные языки, похоже, обладают способностью эффективно реализовывать регулярные выражения.Я уже видел очень классную версию, написанную на Common-Lisp: CL_PPCRE

Если вы можете доказать O (n), это может быть интересным результатом, но вы должны быть уверены, чточто у вас действительно линейная сложность по времени, и вы не очень эффективны.