0 added
0 removed
Original
2026-01-01
Modified
2026-03-10
1
<p>Теги: машина регулярных выражений, python, регулярка, backtracking, возвращение назад в строке при поиске, алгоритм thompson nfa, non-deterministic finite automata, недетерменированный конечный автомат, кен томпсон, grep, awk, библиотека re2</p>
1
<p>Теги: машина регулярных выражений, python, регулярка, backtracking, возвращение назад в строке при поиске, алгоритм thompson nfa, non-deterministic finite automata, недетерменированный конечный автомат, кен томпсон, grep, awk, библиотека re2</p>
2
<p>Как известно каждому программисту, если собираешься решить свои проблемы регулярками, то у тебя просто станет на одну проблему больше. Но иногда выхода нет и приходится<em>"расчехлить"</em>свою машину регулярных выражений.</p>
2
<p>Как известно каждому программисту, если собираешься решить свои проблемы регулярками, то у тебя просто станет на одну проблему больше. Но иногда выхода нет и приходится<em>"расчехлить"</em>свою машину регулярных выражений.</p>
3
<p>Собственно алгоритм, который лежит в её основе схож у многих популярных языков: Python, Perl, Java, Ruby и т.д. И с ним есть проблема: он может жутко<em>"тупить"</em>на некоторых видах регулярок. В частности, это регулярные выражения, где используется backtracking, т.е. возвращение назад в строке при поиске.</p>
3
<p>Собственно алгоритм, который лежит в её основе схож у многих популярных языков: Python, Perl, Java, Ruby и т.д. И с ним есть проблема: он может жутко<em>"тупить"</em>на некоторых видах регулярок. В частности, это регулярные выражения, где используется backtracking, т.е. возвращение назад в строке при поиске.</p>
4
<h2>Например, "a?b?c"</h2>
4
<h2>Например, "a?b?c"</h2>
5
<p>Чтобы сматчить такое, сначала будет опробовано “аbc”, потом “bc”, “ac”, “c”. Иными словами, сначала испытывается вариант с наличием символа. Если его нет, то надо возвращаться и начинать поиск опять, перечитывать строку.</p>
5
<p>Чтобы сматчить такое, сначала будет опробовано “аbc”, потом “bc”, “ac”, “c”. Иными словами, сначала испытывается вариант с наличием символа. Если его нет, то надо возвращаться и начинать поиск опять, перечитывать строку.</p>
6
<p>Таким образом, для регулярки вида<strong>"a?"<em>N + "a"</em>N</strong>сложность алгоритма O(2^N). Регулярка действительно непростая, и это легко проверить на примере:</p>
6
<p>Таким образом, для регулярки вида<strong>"a?"<em>N + "a"</em>N</strong>сложность алгоритма O(2^N). Регулярка действительно непростая, и это легко проверить на примере:</p>
7
$ time python2.7 -c 'import re;re.match("a?"*25 + "a"*25, "a"*25)'` real 0m3.368s` user 0m3.327s` sys 0m0.025s`<h2>Как же быть?</h2>
7
$ time python2.7 -c 'import re;re.match("a?"*25 + "a"*25, "a"*25)'` real 0m3.368s` user 0m3.327s` sys 0m0.025s`<h2>Как же быть?</h2>
8
<p>Не отказываться же теперь от backtracking’а? Выход есть! Нужно сменить машину регулярных выражений на использующую алгоритм<strong>Thompson NFA</strong>(non-deterministic finite automata или недетерменированный конечный автомат).</p>
8
<p>Не отказываться же теперь от backtracking’а? Выход есть! Нужно сменить машину регулярных выражений на использующую алгоритм<strong>Thompson NFA</strong>(non-deterministic finite automata или недетерменированный конечный автомат).</p>
9
<p>Его разработал тот самый Кен Томпсон ещё в середине 60-х. Он используется в таких утилитах, как grep и awk. Попробовать его в Python можно с помощью библиотеки re2: это обвязка вокруг C++ реализации от Google.</p>
9
<p>Его разработал тот самый Кен Томпсон ещё в середине 60-х. Он используется в таких утилитах, как grep и awk. Попробовать его в Python можно с помощью библиотеки re2: это обвязка вокруг C++ реализации от Google.</p>
10
$ time python2.7 -c 'import re2;re2.match("a?"*25 + "a"*25, "a"*25)' real 0m0.064s user 0m0.023s sys 0m0.022s<p><em>Остались вопросы? Напишите в комментариях!</em></p>
10
$ time python2.7 -c 'import re2;re2.match("a?"*25 + "a"*25, "a"*25)' real 0m0.064s user 0m0.023s sys 0m0.022s<p><em>Остались вопросы? Напишите в комментариях!</em></p>
11
11