Катастрофическая обратная переборка
Катастрофическая обратная переборка — это явление в регулярных выражениях, при котором движок тратит чрезмерное количество времени на оценку определённых шаблонов, что приводит к значительному снижению производительности. Эта проблема может возникать, когда движок регулярных выражений неоднократно пытается сопоставить части строки различными способами, особенно при работе со сложными шаблонами, содержащими вложенные квантификаторы.
Что вызывает катастрофическую обратную переборку?
Катастрофическая обратная переборка обычно возникает при использовании вложенных квантификаторов в регулярных выражениях. Эти квантификаторы позволяют сопоставлять части шаблона несколькими способами, что заставляет движок выполнять избыточный возврат. Вот пример:
Если на вашем компьютере это не занимает много времени, вы можете добавить ещё один символ a в переменную str. Почему же это занимает так много времени? Давайте разберёмся. Шаблон /^(a+)+$/ состоит из:
^— утверждает позицию в начале строки.(a+)— сопоставляет один или более символовa.+— позволяет предыдущей группе(a+)повторяться один или более раз.$— утверждает позицию в конце строки.
Теперь процесс сопоставления выглядит так:
- Начальное сопоставление: Движок начинает с начала строки (
^). - Сопоставление первой группы: Движок сопоставляет первый
a+, потребляя все символыa(aaa...). - Внешний квантификатор: Внешний
+позволяет движку повторять группу(a+).
Когда движок достигает восклицательного знака (!), он не может сопоставить его с шаблоном, из-за чего сопоставление завершается неудачей. В этот момент начинается возврат:
- Попытка возврата: Движок возвращается назад, чтобы повторно разделить сопоставленные символы
aмежду внутреннимa+и внешним+квантификаторами. Он заново оценивает каждое разделение, чтобы проверить, может ли другое разбиение сопоставить шаблон до конца строки. - Экспоненциальный рост: Этот процесс возврата может расти экспоненциально, поскольку движок пробует каждый возможный способ разбиения строки символов
aна разные группы, которые потенциально могут соответствовать(a+)+.
Для строки из n символов a количество способов разбить их на группы для (a+)+ может быть значительным, что приводит к резкому увеличению времени вычислений.
Как выявить шаблоны, склонные к катастрофической обратной переборке
Шаблоны, особенно склонные к катастрофической обратной переборке, часто включают:
- Вложенные квантификаторы (например,
(a+)+) - Пересекающиеся классы символов (например,
([a-zA-Z0-9_]+)+) - Двусмысленные подшаблоны, которые могут сопоставляться множеством способов
Стратегии предотвращения катастрофической обратной переборки
Чтобы предотвратить катастрофическую обратную переборку, рассмотрите следующие стратегии:
1. Переструктурирование вложенных квантификаторов
Нежадные квантификаторы не предотвращают катастрофическую обратную переборку во вложенных шаблонах. Вместо этого переструктурируйте регулярное выражение, чтобы устранить вложенные квантификаторы, или используйте ограниченные квантификаторы.
2. Оптимизация регулярных выражений
Упростите свои регулярные выражения, чтобы избежать ненужной сложности и вложенности. Убедитесь, что каждая часть шаблона максимально конкретна.
Практические примеры и решения
Пример 1: Сопоставление вложенных HTML-тегов
Распространённый случай использования регулярных выражений — сопоставление вложенных HTML-тегов, что при неправильной обработке может легко привести к катастрофической обратной переборке. Примечание: Регулярные выражения, как правило, не подходят для разбора произвольных или глубоко вложенных HTML-структур; для сложных документов используйте специализированный HTML-парсер.
Проблемный шаблон
Улучшенный шаблон
Пример 2: Сопоставление повторяющихся шаблонов
Проблемный шаблон
Улучшенный шаблон
Заключение
Катастрофическая обратная переборка может серьёзно повлиять на производительность ваших JavaScript-приложений при использовании регулярных выражений. Понимая причины возникновения проблемы и применяя такие стратегии, как переструктурирование шаблонов, избегание вложенных квантификаторов и использование ограниченных квантификаторов, вы сможете предотвратить эти проблемы с производительностью. Всегда тестируйте свои регулярные выражения с входными данными различной длины и сложности, чтобы убедиться в их эффективной работе.
Практика
Какие основные причины катастрофической обратной переборки в регулярных выражениях?