Get ready to run back: ещё одна проблема регулярных выражений

Как известно каждому программисту, если собираешься решить свои проблемы регулярками, то у тебя просто станет на одну проблему больше. Но иногда выхода нет и приходится «расчехлить» свою машину регулярных выражений.

Собственно алгоритм, который лежит в её основе схож у многих популярных языков: Python, Perl, Java, Ruby и т.д. И с ним есть проблема: он может жутко «тупить» на некоторых видах регулярок. В частности, это регулярные выражения, где используется backtracking, т.е. возвращение назад в строке при поиске.

Например, "a?b?c"

Чтобы сматчить такое, сначала будет опробовано “аbc”, потом “bc”, “ac”, “c”. Иными словами, сначала испытывается вариант с наличием символа. Если его нет, то надо возвращаться и начинать поиск опять, перечитывать строку.

Таким образом, для регулярки вида "a?"N + "a"N сложность алгоритма O(2^N). Регулярка действительно непростая, и это легко проверить на примере:

$ time python2.7 -c 'import re;re.match("a?"*25 + "a"*25, "a"*25)'`

real    0m3.368s`
user    0m3.327s`
sys 0m0.025s`

Как же быть?

Не отказываться же теперь от backtracking’а? Выход есть! Нужно сменить машину регулярных выражений на использующую алгоритм Thompson NFA (non-deterministic finite automata или недетерменированный конечный автомат).

Его разработал тот самый Кен Томпсон ещё в середине 60-х. Он используется в таких утилитах, как grep и awk. Попробовать его в Python можно с помощью библиотеки re2: это обвязка вокруг C++ реализации от Google.

$ time python2.7 -c 'import re2;re2.match("a?"*25 + "a"*25, "a"*25)'

real    0m0.064s
user    0m0.023s
sys 0m0.022s

Остались вопросы? Напишите в комментариях!