«1. Обзор

В этом кратком руководстве мы покажем, как работает механизм сопоставления с образцом. Мы также представим различные способы оптимизации регулярных выражений в Java.

Для ознакомления с использованием регулярных выражений обратитесь к этой статье здесь.

2. Механизм сопоставления с образцом

Пакет java.util.regex использует механизм сопоставления с образцом, называемый недетерминированным конечным автоматом (NFA). Он считается недетерминированным, потому что при попытке сопоставить регулярное выражение с заданной строкой каждый символ во входных данных может несколько раз сверяться с разными частями регулярного выражения.

В фоновом режиме упомянутый выше движок использует поиск с возвратом. Этот общий алгоритм пытается исчерпать все возможности, пока не объявит об отказе. Рассмотрим следующий пример, чтобы лучше понять NFA: 

"tra(vel|ce|de)m"

Со входной строкой «travel» движок сначала будет искать «tra» и немедленно найдет его.

После этого он попытается сопоставить «vel», начиная с четвертого символа. Это совпадет, поэтому он пойдет вперед и попытается сопоставить «m».

Это не совпадет, и по этой причине он вернется к четвертому символу и будет искать «ce». Опять же, это не совпадет, поэтому он снова вернется на четвертую позицию и попытается использовать «de». Эта строка также не будет совпадать, поэтому она вернется ко второму символу входной строки и попытается найти другую «тра».

При последней ошибке алгоритм вернет ошибку.

В последнем простом примере движку пришлось несколько раз возвращаться назад, пытаясь сопоставить входную строку с регулярным выражением. Из-за этого важно свести к минимуму количество возвратов, которые он делает.

3. Способы оптимизации регулярных выражений

3.1. Избегайте перекомпиляции

Регулярные выражения в Java компилируются во внутреннюю структуру данных. Эта компиляция является трудоемким процессом.

Каждый раз, когда мы вызываем метод String.matches(String regex), указанное регулярное выражение перекомпилируется: 

if (input.matches(regexPattern)) {
    // do something
}

Как мы видим, каждый раз при оценке условия компилируется регулярное выражение.

Для оптимизации можно сначала скомпилировать шаблон, а затем создать Matcher для поиска совпадений в значении: 

Pattern pattern = Pattern.compile(regexPattern);
for(String value : values) {
    Matcher matcher = pattern.matcher(value);
    if (matcher.matches()) {
        // do something
    }
}

Альтернативой описанной выше оптимизации является использование того же экземпляра Matcher с его методом reset() : 

Pattern pattern = Pattern.compile(regexPattern);
Matcher matcher = pattern.matcher("");
for(String value : values) {
    matcher.reset(value);
    if (matcher.matches()) {
      // do something
    }
}

Из-за того, что Matcher не является потокобезопасным, мы должны быть осторожны с использованием этого варианта. Вероятно, это может быть опасно в многопоточных сценариях.

Подводя итог, в каждой ситуации, когда мы уверены, что в любой момент времени есть только один пользователь Matcher, можно повторно использовать его с помощью сброса. В остальном повторного использования предварительно скомпилированного достаточно.

3.2. Работа с чередованием

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

Кроме того, мы должны выделить между ними общие закономерности. Это не то же самое, что поставить: 

(travel | trade | trace)

Чем: 

tra(vel | de | ce)

Последнее быстрее, потому что NFA попытается сопоставить «tra» и не будет пробовать какие-либо альтернативы, если это не так. не найти.

3.3. Захват групп

Каждый раз, когда мы захватываем группы, мы подвергаемся небольшому штрафу.

Если нам не нужно захватывать текст внутри группы, мы должны рассмотреть возможность использования групп без захвата. Вместо «(М)» используйте «(?:М)».

4. Заключение

В этой быстрой статье мы кратко рассмотрели, как работает NFA. Затем мы приступили к изучению того, как оптимизировать производительность наших регулярных выражений путем предварительной компиляции наших шаблонов и повторного использования Matcher.

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

Как обычно, полный исходный код можно найти на GitHub.