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

Курсы

Программирование
Microservice Architecture
-5%
React.js Developer
-4%
C++ Developer. Professional
-5%
Scala-разработчик
-8%
Backend-разработчик на PHP
-9%
Алгоритмы и структуры данных
-9%
Python Developer. Basic
-12%
Golang Developer. Professional
-5%
HTML/CSS
-11%
C# ASP.NET Core разработчик
-5%
Kotlin Backend Developer
-8%
iOS Developer. Professional
-8%
Java Developer. Professional Web-разработчик на Python MS SQL Server Developer Android Developer. Basic Разработчик программных роботов (RPA) на базе UiPath и PIX Highload Architect Reverse-Engineering. Professional Vue.js разработчик Node.js Developer Интенсив «Оптимизация в Java» Супер-практикум по использованию и настройке GIT Symfony Framework Java Developer. Basic Unity Game Developer. Professional Супер-интенсив Azure
Инфраструктура
Microservice Architecture
-5%
Экспресс-курс «IaC Ansible»
-10%
Administrator Linux.Basic
-10%
Мониторинг и логирование: Zabbix, Prometheus, ELK
-10%
Экспресс-курс «CI/CD или Непрерывная поставка с Docker и Kubernetes»
-30%
Administrator Linux. Professional
-6%
Экcпресс-курс «ELK»
-10%
Экспресс-курс по управлению миграциями (DBVC)
-10%
Базы данных Network engineer Разработчик программных роботов (RPA) на базе UiPath и PIX Highload Architect Разработчик голосовых ассистентов и чат-ботов VOIP инженер Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Супер-интенсив "Tarantool"
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

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

PythonDeep14.05_Site.png

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

Собственно алгоритм, который лежит в её основе схож у многих популярных языков: 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

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

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться