1. Обзор
В этом кратком руководстве мы покажем, как работает механизм сопоставления шаблонов. Мы также представим различные способы оптимизации регулярных выражений в Java.
Для ознакомления с использованием регулярных выражений , пожалуйста, обратитесь к этой статье здесь .
2. Механизм Сопоставления Шаблонов
Пакет java.util.regex использует тип механизма сопоставления шаблонов, называемый Недетерминированным конечным автоматом (NFA). Это считается недетерминированным , потому что при попытке сопоставить регулярное выражение в данной строке каждый символ во входных данных может быть несколько раз проверен на соответствие различным частям регулярного выражения.
В фоновом режиме упомянутый выше движок использует backtracking . Этот общий алгоритм пытается исчерпать все возможности, пока не объявит о неудаче. Рассмотрим следующий пример, чтобы лучше понять NFA :
"tra(vel|ce|de)m"
При вводе String ” travel “двигатель сначала будет искать” tra ” и сразу же найдет его.
После этого я попытаюсь сопоставить ” ну “, начиная с четвертого символа. Это будет совпадать, поэтому он пойдет вперед и попытается соответствовать ” m “.
Это не будет совпадать, и по этой причине он вернется к четвертому символу и будет искать ” ce “. Опять же, это не будет совпадать, поэтому он снова вернется на четвертую позицию и попытается использовать ” de “. Эта строка также не будет совпадать, и поэтому она вернется ко второму символу во входной строке и попытается найти другой ” tra “.
При последнем сбое алгоритм вернет сбой.
В простом последнем примере движку пришлось несколько раз возвращаться назад, пытаясь сопоставить входную строку | с регулярным выражением. Из-за этого важно свести к минимуму количество отступлений, которые он делает.
3. Способы оптимизации регулярных выражений
3.1. Избегайте Перекомпиляции
Регулярные выражения в Java компилируются во внутреннюю структуру данных. Эта компиляция является трудоемким процессом.
Каждый раз, когда мы вызываем метод String.matches(String regex) , указанное регулярное выражение перекомпилируется:
if (input.matches(regexPattern)) {
// do something
}Как мы видим, каждый раз, когда вычисляется условие, компилируется выражение регулярного выражения.
Для оптимизации можно сначала скомпилировать шаблон, а затем создать Сопоставитель , чтобы найти совпадения в значении:
Pattern pattern = Pattern.compile(regexPattern);
for(String value : values) {
Matcher matcher = pattern.matcher(value);
if (matcher.matches()) {
// do something
}
}Альтернативой приведенной выше оптимизации является использование того же Соответствует экземпляру с его reset() методом:
Pattern pattern = Pattern.compile(regexPattern);
Matcher matcher = pattern.matcher("");
for(String value : values) {
matcher.reset(value);
if (matcher.matches()) {
// do something
}
}В связи с тем, что Спички не является потокобезопасным, мы должны быть осторожны с использованием этого варианта. Это может быть опасно в многопоточных сценариях.
Подводя итог, в любой ситуации, когда мы уверены, что в любой момент времени есть только один пользователь Matcher , можно повторно использовать его с помощью reset . В остальном, повторное использование предварительно скомпилированного достаточно.
3.2. Работа с чередованием
Как мы только что проверили в последнем разделе, неадекватное использование чередований может нанести вред производительности. Важно разместить варианты, которые с большей вероятностью произойдут впереди, чтобы их можно было быстрее сопоставить.
Кроме того, мы должны извлечь общие закономерности между ними. Это не одно и то же, чтобы поставить:
(travel | trade | trace)
Чем:
tra(vel | de | ce)
Последнее быстрее, потому что NFA попытается соответствовать ” tra ” и не будет пробовать ни одну из альтернатив, если не найдет ее.
3.3. Захват групп
Каждый раз, когда мы захватываем группы, мы несем небольшой штраф.
Если нам не нужно захватывать текст внутри группы, мы должны рассмотреть возможность использования групп без захвата. Вместо ” (M) “, пожалуйста, используйте ” (?:M) “.
4. Заключение
В этой краткой статье мы кратко рассмотрели, как работает NFA . Затем мы приступили к изучению того, как оптимизировать производительность наших регулярных выражений путем предварительной компиляции ваших шаблонов и повторного использования Matcher .
Наконец, мы указали на несколько соображений, которые следует учитывать при работе с чередованием и группами.
Как обычно, полный исходный код можно найти на GitHub .