Регулярные выражения: три операции, автомат и возвраты, которые не кончаются

Если ты разложишь выражение на три базовые операции, построишь по нему НКА и объяснишь, почему один движок отвечает за линейное время, а другой может зависнуть, - листай до «Теперь сам».

Как думаешь, сколько можно проверять строку из тридцати букв

Шаблон (a+)+b означает: одна или несколько групп, в каждой одна или несколько букв a, а в конце буква b. Строка - тридцать букв a и ни одной b. Совпадения нет, и человеку это видно сразу.

Попробуй угадать до чтения, сколько времени уйдёт у стандартного модуля регулярных выражений Python: микросекунды, миллисекунды, секунды? Вызов - re.fullmatch("(a+)+b", "a" * 30). На двадцати четырёх буквах он думает около секунды, и каждая следующая буква удваивает время; тридцать букв - это уже минута. Причина не в Python и не в шаблоне как таковом, а в способе поиска, и у регулярных выражений есть другой способ, которому всё равно.

На что это похоже

Конструктор из трёх видов деталей. Тройник - «иди сюда или туда». Соединитель - «сначала это, потом то». Петля - «повтори сколько угодно раз, можно ни разу». Из них собирается схема путей любой сложности, а строка подходит под схему, если по ней можно пройти от входа до выхода, называя буквы на рельсах.

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

Механизм: от выражения к автомату

Регулярное выражение над алфавитом определяется так:

символ алфавита       подходит одна эта буква
ε                     подходит пустая строка
R | S   выбор         подходит строка, подходящая под R или под S
R S     сцепление     подходит строка, которую можно разрезать
                      на часть под R и часть под S
R*      повтор        подходит сцепление любого числа строк под R,
                      включая ни одной
∅                     не подходит ни одна строка

Порядок действий: сначала повтор, потом сцепление, потом выбор; скобки меняют его, как в арифметике. ab*c - это a, сколько угодно b и c, а не повтор ab; a|bc - это a или bc.

Привычные обозначения выражаются через эти три: R+ - это R R*; R? - это R | ε; [abc] - это a | b | c; R{3} - это R R R.

Из выражения в НКА. Автомат одной буквы - два состояния, начало и конец, и переход между ними по этой букве. У каждого куска выражения автомат с одним началом и одним концом, и для каждой операции есть способ склеить автоматы её частей ε-переходами:

R | S   новое начало с ε-переходами в начала R и S;
        концы R и S ведут ε-переходами в общий конец
R S     конец R соединён ε-переходом с началом S
R*      новое начало и новый конец;
        из нового начала ε-переходы в начало R и сразу в новый конец
        (ни разу); из конца R ε-переходы обратно в начало R (ещё раз)
        и в новый конец

Каждая операция добавляет не больше двух состояний, поэтому у выражения из m символов и операций получается НКА примерно с 2m состояниями. Это построение Томпсона.

Соберём автомат для ab*. Состояния пронумерованы по мере появления:

буква a     1 →a→ 2
буква b     3 →b→ 4
b*          новое начало 5 и новый конец 6:
            5 →ε→ 3,  5 →ε→ 6,  4 →ε→ 3,  4 →ε→ 6
a b*        конец a соединён с началом b*:   2 →ε→ 5

Начало всего автомата - 1, конец - 6. Строка abb проходит так: 1 →a→ 2 →ε→ 5 →ε→ 3 →b→ 4 →ε→ 3 →b→ 4 →ε→ 6. Строка a короче: 1 →a→ 2 →ε→ 5 →ε→ 6. Шесть состояний на выражение из двух букв и двух операций - в пределах обещанных 2m.

Из автомата в выражение тоже можно. Автомат рисуют графом: состояния - вершины, переходы - рёбра с буквами. На рёбрах разрешают писать не символы, а выражения, и состояния убирают по одному. Когда убирают состояние q, каждый путь «из p в q, потом из q в r» заменяют ребром из p в r с выражением «вход в q, петля на q сколько угодно раз, выход из q». Чтобы концов не было несколько, перед удалением добавляют новое начало и один общий конец: ε-рёбра ведут из нового начала в старое и из каждого принимающего состояния в общий конец. Когда остаются только эти двое, выражение на ребре между ними и есть ответ. Пример - автомат «чётное число единиц» с состояниями «чётно» (начальное и принимающее) и «нечётно». Убираем «нечётно»: путь из «чётно» туда и обратно - это 1 0* 1, вместе с петлёй по нулю получается ребро 0 | 1 0* 1, а всё выражение - (0 | 1 0* 1)*. Поэтому языки, описываемые регулярными выражениями, - в точности регулярные языки из первого урока: три способа записи, один класс.

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

Перебор с возвратами идёт по одному пути и возвращается при неудаче. Его цена - число путей, а оно может быть огромным: у выражения (a+)+ строку из n букв a можно разбить на группы 2ⁿ⁻¹ способами, и если после них не нашлось b, перебор проверит каждое разбиение.

Слежение за множеством состояний - алгоритм прошлого урока: на каждый символ текста пересчитать множество возможных состояний. Цена - n · m, и она не зависит от того, совпала строка или нет.

Правило

Регулярное выражение строится из символов, ε и ∅ операциями выбора, сцепления и повтора; остальные обозначения - сокращения. Для выражения длины m - считая после раскрытия сокращений: a{1000} это тысяча букв, а не семь знаков, - существует НКА с O(m) состояниями, а по любому автомату строится выражение (оно может выйти намного длиннее автомата), поэтому выражения описывают ровно регулярные языки. Поиск слежением за множеством состояний стоит O(n · m). Поиск с возвратами в худшем случае экспоненциален по длине строки. Обратные ссылки вида \1 - «здесь повторяется то, что совпало с первой скобкой» - позволяют записать и нерегулярный язык, поэтому автомат по шаблону с ними построить удаётся не всегда.

Разбор: один шаблон, два поиска

Мини-язык: буква или буква со звёздочкой. Функция sovpadaet проверяет, подходит ли вся строка под шаблон, перебором с возвратами. Вызов sovpadaet(obrazec, i, stroka, j) отвечает на вопрос, подходит ли остаток строки с позиции j под остаток шаблона с позиции i: для x* она пробует ноль букв, потом одну, потом две и для каждого варианта проверяет остаток шаблона. Счётчик в schet считает её вызовы. Функция mnozhestvami ведёт множество позиций шаблона, в которых сейчас может находиться разбор; zamknut добавляет позиции, достижимые без чтения символа - пропуском x*.

schet = [0]

def sovpadaet(obrazec, i, stroka, j):
    schet[0] = schet[0] + 1
    if i == len(obrazec):
        return j == len(stroka)
    if i + 1 < len(obrazec) and obrazec[i + 1] == "*":
        if sovpadaet(obrazec, i + 2, stroka, j):
            return True
        while j < len(stroka) and stroka[j] == obrazec[i]:
            j = j + 1
            if sovpadaet(obrazec, i + 2, stroka, j):
                return True
        return False
    if j < len(stroka) and stroka[j] == obrazec[i]:
        return sovpadaet(obrazec, i + 1, stroka, j + 1)
    return False

def mnozhestvami(obrazec, stroka):
    proverok = 0
    aktivnye = zamknut(obrazec, {0})
    for simvol in stroka:
        sleduyushchie = set()
        for i in aktivnye:
            proverok = proverok + 1
            if i < len(obrazec) and obrazec[i] == simvol:
                if i + 1 < len(obrazec) and obrazec[i + 1] == "*":
                    sleduyushchie.add(i)
                else:
                    sleduyushchie.add(i + 1)
        aktivnye = zamknut(obrazec, sleduyushchie)
    return [len(obrazec) in aktivnye, proverok]

def zamknut(obrazec, mnozhestvo):
    gotovo = set()
    stek = list(mnozhestvo)
    while len(stek) > 0:
        i = stek.pop()
        if i in gotovo:
            continue
        gotovo.add(i)
        if i + 1 < len(obrazec) and obrazec[i + 1] == "*":
            stek.append(i + 2)
    return gotovo

obrazec = "a*a*a*a*a*b"
for n in [4, 8, 12, 16]:
    stroka = "a" * n
    schet[0] = 0
    otvet = sovpadaet(obrazec, 0, stroka, 0)
    vtoroj = mnozhestvami(obrazec, stroka)
    print(n, otvet, schet[0], vtoroj[0], vtoroj[1])
proverki = [sovpadaet("a*b", 0, "aaab", 0),
            mnozhestvami("a*b", "aaab")[0]]
proverki = proverki + [mnozhestvami("ab*c", "abbbc")[0],
                       mnozhestvami("ab*c", "abbb")[0]]
print(proverki[0], proverki[1], proverki[2], proverki[3])

4 False 252 False 24
8 False 2002 False 48
12 False 8568 False 72
16 False 26334 False 96
True True True False

Столбцы: длина строки, ответ и число вызовов у перебора, ответ и число проверок у множеств. Ответы совпадают - совпадения нет. Перебор сделал 252 вызова на четырёх буквах и 26 334 на шестнадцати. Это многочлен пятой степени от длины, по степени на каждую звёздочку; на таких коротких строках старшая степень ещё не набрала силу, и удвоение длины с 8 до 16 дало рост в 13 раз, а не в 32. Множества сделали 24 и 96 проверок: шесть на символ при любой длине, по одной на каждый элемент шаблона - пять a* и b. Последняя строка вывода - сверка на строках попроще: a*b на aaab обоими способами, ab*c на abbbc и на abbb.

Перебор тратит работу на то, чтобы всеми способами распределить буквы a между пятью звёздочками, хотя от распределения ничего не зависит: буквы b нет ни в одном варианте. Множество состояний хранит только то, до какого места шаблона можно было дойти, и разные распределения, ведущие в одно место, в нём сливаются.

Разбор: вложенные повторы и то, что автомату не по силам

В мини-языке нет скобок, и рост остаётся степенным. Со скобками появляется настоящая экспонента. Шаблон (a+)+b на строке из n букв a: внешний повтор делит буквы на группы, и разбиений 2ⁿ⁻¹ - между каждыми двумя соседними буквами граница группы либо есть, либо нет. Перебор с возвратами проверит их все. Двадцать букв - полмиллиона разбиений, тридцать - полмиллиарда.

Движок на множествах состояний строит для (a+)+b автомат из нескольких состояний и проходит строку за один проход. Зачем тогда вообще нужны возвраты?

Затем, что привычные «регулярные выражения» давно умеют больше регулярного. Обратная ссылка \1 требует, чтобы в этом месте повторился текст, совпавший с первой скобкой: (a*)b\1 принимает aabaa и отвергает aaba. Язык «сколько-то букв a, потом b, потом столько же букв a» конечный автомат не распознаёт - для этого нужно помнить неограниченное число, и следующий урок это докажет. Этот шаблон автоматом не выразить, а перебор с возвратами справляется с ним естественно. Плата - худший случай: поиск по шаблонам с обратными ссылками относится к задачам, для которых быстрого алгоритма не известно вовсе.

Отсюда граница между двумя семействами движков. Одни - в Python, Java, JavaScript, Perl - работают возвратами и поддерживают обратные ссылки и просмотр вперёд - проверку «дальше идёт такой-то текст» без его чтения. Другие - RE2, пакет regexp в Go, библиотека regex для Rust - работают автоматами, гарантируют линейное время и обратных ссылок не поддерживают принципиально.

Что ломается без этого

Шаблон от пользователя или строка от пользователя. Если движок с возвратами, а в шаблоне есть повтор внутри повтора или два соседних повтора одного и того же, то подобранная строка останавливает сервис. Атака называется ReDoS. В 2019 году одно такое правило в фильтре запросов на несколько десятков минут вывело из строя крупную сеть доставки содержимого: выражение загрузило процессоры всех серверов.

«Строка короткая, значит быстро». Экспонента начинается на десятках символов. Проверка поля формы длиной в тридцать букв может длиться минуту.

Проверка только на строках, которые подходят. Беда случается на строках, которые почти подходят: до последнего символа всё совпадает, а потом совпадение срывается, и перебор начинает возвращаться.

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

Зачем это в работе

Выбор движка. Если шаблоны или данные приходят извне, берут движок с линейной гарантией или ограничивают время поиска. В Python стандартный модуль работает возвратами; с версии 3.11 в нём есть «жадные без возврата» повторы (a++) и атомарные группы ((?>...)): пройдя такой кусок шаблона, движок не возвращается перебирать его заново. Ими возвраты можно запретить вручную.

Чтение чужих шаблонов. Опасные места узнаются по форме: повтор внутри повтора ((a+)+), выбор с перекрывающимися вариантами под повтором ((a|aa)*), два соседних повтора, которые могут съесть одни и те же символы (\s*\s*, .*.*; \s - любой пробельный символ, точка - любой символ). Это ровно те места, где у автомата много путей в одно и то же состояние.

Инструменты поиска по тексту и разбор журналов построены на автоматах именно ради предсказуемости: один проход по гигабайтам текста при любом шаблоне.

Теперь сам

1. Запиши a+ и a? через выбор, сцепление и повтор.
2. Какие из шаблонов описывают регулярный язык: a|b, (ab)*, a{3}, (a*)b\1?
3. Запиши выражение для языка «строка из нулей и единиц, в которой третий символ с конца - единица».
4. Шаблон длины 20, текст длины миллион. Оцени число проверок у поиска множествами.
5. Сколькими способами шаблон (a+)+ может разбить на группы строку из пяти букв a?