Posted by Eyal Schneider on May 21, 2009
Пакет java.util.regex добавлен в Java в версии 1.4. Это очень мощный инструмент, и нужно стать мастером, чтобы использовать его правильно. Даже когда
регулярное выражение верно, оно может работать очень медленно если написано неразумно.
Продолжайте чтение если хотите разобраться в причине проблем или листайте страницу до конца, где найдете 10 полезных рекомендаций по повышению производительности регулярных выражений в Java.
Неужели так медленно?
Предположим, что мы хотим выбрать только строки содержащие последовательность символов "a" и "b". Верное решение может быть таким:
(a*b*)*
Однако, если вы запустите выражение, например, со строкой “aaaaaaaaaaaaaaaaaaaaaaaaaaaaax” , то пройдет несколько минут до завершения и рапорта об отсутствии совпадений!
Конечно, лучшей регуляркой в данном случае будет:
(a|b)*
Это затрачивает меньше миллисекунды на моей машине при той же строке. Очевидно, что здесь существует проблема с производительностью.
Почему так происходит?
Как и большинство движков регекспов, Java использует НКА (Недетерминированные Конечные Автоматы) подход. Движок сканирует компоненты регулярки один за другим и продвигается по входной строке соответствующим образом. И он может вернуться обратно к началу, чтобы найти соответствующие альтернативы если зайдет в "тупик". Альтернативные результаты получаются при использовании регулярных структур таких как квантификаторы (*, +, ?) и чередования (например a|b|c|d). Такая техника исследования называется возврат (backtracking).
В ужасном примере выше движок на самом деле будет просматривать ВСЕ разложения серии символа "a" на меньшие серии пока не поймет, что совпадений нет. Этот пример показывает как алгоритм возврата может привести к экспоненциальной оценке времени (в зависимости от длины входной строки). Это так же показывает важное свойство НКА: всегда будут худшие случаи которые почти соответствуют шаблону. Если соответствие найдено поиск останавливается.
Другой основной подход для использования в регулярках это ДКА (Детерминированный Конечный Автомат). В этом подходе регулярное выражение фактически строит автомат, который используется для прохождения по входным строкам символ за символом без возврата. Это дает линейное время на весь вход, независимо от сложности регулярного выражения. Вместо последовательного исследования строки в поисках совпадений (как в НКА), ДКА симулирует параллельное сканирование.
Так почему же Java (и .NET, Perl, Python, Ruby, PHP и др.) используют НКА а не ДКА у которого намного лучшее поведение? Причина в том, что у НКА есть ряд существенных преимуществ:
- Компилируется быстрее и требует намного меньшее количество памяти
- Позволяет использовать некоторые полезные функции (подробнее смотрите в Sun’s tutorial):
- Захват группы и обратные ссылки
- Позиционная проверка
- Расширенные квантификаторы (Жадный и Ленивый)
Важно отметить, что популярные термины НКА и ДКА при использовании в контексте регулярок являются неточными. Теоретически, эти две модели имеют одинаковую мощность вычислений. Это значит, что нельзя написать такое регулярное выражение в одной модели автоматов, которое было бы невозможно выразить в другой. На практике существует необходимость в большем количестве возможностей так, что два типа реализации разошлись в семантике. НКА движки дают больше гибкости делая их превосходящими перед ДКА в вычислительной мощности.
Благодаря скорости ДКА и уникальным особенностям НКА есть еще 2 "сборных" способа реализации регулярных выражений. Некоторые реализации используют оба типа (например GNU egrep, который выбирает конкретный движок во время выполнения), а некоторым удалось реализовать действительно гибридную версию (например регекспы в Tcl) со всеми преимуществами.
Советы
Следующие несколько советов о том как избежать проблем с эффективностью регулярок в Java. Многие из них направлены на снижение возвратов.
1) Предварительная компиляция
Банально, но стоит упомянуть. Если вы используете регексп не один раз не забудьте скомпилировать его заранее:
// компиляция
p = Pattern.compile(regex, flags);
…
// использование
Matcher a = p.matcher(input);
2) Ленивые квантификаторы против Жадных квантификаторов
По умолчанию квантификаторы (* + ?) жадные. Это значит они начинают сопоставление с наиболее длинной возможной последовательностью и затем постепенно возвращаются если необходимо. В случае если вы заранее знаете, что совпадения будут как правило, короткие, вы должны использовать ленивые квантификаторы. Они начинают с наименьшего совпадения и двигаются дальше если надо.
Предположим мы хотим найти только строки соответствующие последовательности "hello". Регулярка .*hello.* сделает все правильно, но если мы знаем, что "hello" обычно появляется ближе к началу текста, тогда .*?hello.* в среднем будет работать быстрее.
3) Используйте сверхжадные квантификаторы где возможно
В отличие от ленивых квантификаторов, которые влияют на производительность, но не влияют на регулярное поведение, сверхжадные квантификаторы могут действительно изменить смысл регулярного выражения.
Когда используется *+ вместо *, то первое совпадение будет жадны (то есть наибольшее возможное так, будто это просто *), но не будет отката в случае неудачи , даже если это вызовет несоответствие всего поиска. Когда это может быть полезно?
Предположим нам нужно найти текст в кавычках. Регулярка \"[^\"]*\" отработает нормально. Тем не менее она будет делать ненужный отступ в негативных случаях (например. “bla bla bla). Используя \"[^\"]*+\" устранит откаты не меняя смысл выражения.
Независимая группировка (Independent grouping) позволяет добиться того же эффекта, и дает еще больше контроля (см. Sun’s tutorial ).
4) Избегайте захвата группы
Любое выражение в скобках по-умолчанию считается группой. Это имеет небольшое влияние на производительность. Делайте ваши группы "незахватываемыми" когда возможно, начиная их с (?: вместо (.
5) Разумное использование чередования
Когда используется чередование (например Paul|Jane|Chris), порядок в котором движок пытается сопоставить варианты такой же как и в порядке перечисления в котором они появляются. Вы можете воспользоваться этой особенностью и расположить наиболее распространенные варианты ближе к началу. Это улучшит среднее время положительных срабатываний.
6) Избегайте многозначности
Пишите регекспы таким образом, чтобы свести к минимуму количество различных соответствий в входной строке. Для примера: регулярка (a*b*)* данная в начале статьи, позволяет интерпретировать строку "aabb" слишком многими способами:
(a2b2)
(a1)(a1)(b1)(b1)
(a2)(b2)
(a1)(a1b2)
etc…
Регексп (a|b)* с другой стороны положительно интерпретирует только уникальные комбинации.
Это очень важно для уменьшения возвратов в случаях почти совпадения.
7) Предпросмотр
Предпросмотр позволяет добавить ограничения на последовательности слева/справа от текущей позиции. В частности с отрицательным предпросмотром можно искать строки, которые не содержат некоторую последовательность (что бы мы без этого делали!). Как это может помочь увеличить производительность?
Предположим мы хотим взять URL адрес из тега ссылки. Рассмотрим следующий регексп:
a .* href=(\S*).*/
Для обычных тегов это выражение найдет адрес только если в тексте будет атрибут "href" (\S используется для всех символов кроме разделителей) . Но на некоторых необычных тегах, например, произойдет откат.
Для примера: “a href= href=href=…. href=something”.
Следующий регексп предотвратит это при замене “.*” в выражении на что-то, что не соответствует "href":
a ((?!href).)* href=(\S*)((?!href).)*/
8) Укажите длину
Java содержит регексп оптимизатор, который проверяет длину входной строки против минимальной и максимальных длин полученных из регулярного выражения. Это позволяет прекращать поиск сразу в некоторых случаях. Для того чтобы помочь этому механизму следует по возможности указывать число повторений (например [01]{6}, соответствует всем двоичным строкам длиной в шесть символов).
9) Выделите одинаковые строки
Иногда строки, которые являются одинаковыми скрыты внутри групп или альтернатив:
(hello|hell|heel)
Это выражение может быть упрощено до:
he(llo|ll|el)
Делая так мы даем регексп оптимизатору больше информации.
10) Тестируйте ваш регексп
Наверно это будет мудрым, вначале тестировать регулярное выражение когда оно будет использоваться в критически важном к производительности приложении. Напишите микро-бенчмарк который протестирует ваше выражение на различных входных данных. Не забудьте проверить на данных различной длины, и также данных, которые почти соответствуют вашему образцу.
Ссылки:
http://java.sun.com/docs/books/tutorial/essential/regex/index.html
http://www.javaworld.com/javaworld/jw-09-2007/jw-09-optimizingregex.html?page=1
http://www.softec.st/en/OpenSource/DevelopersCorner/RegularExpressions/RegularExpressionEngines.html
http://www.devarticles.com/c/a/Java/NFA-DFA-POSIX-and-the-Mechanics-of-Expression-Processing/
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
В переводе лучше подойдет не «артист», а «художник» или «мастер своего дела» и предложение можно переписать, например, так: это сложный и одновременно мощный инструмент и над быть мастером своего дела, чтобы воспользоваться им правильно. Хз, в общем.
Не рапорт, а отчет — у нас не военная тематика =)