Есть ли способ оптимизировать этот случай катастрофического возврата регулярных выражений?

#regex #performance

#регулярное выражение #Производительность

Вопрос:

Итак, я придумал следующее регулярное выражение:

 ([^s\] (?:\.[^s\]*)*)(?:.*?)(S .phpb)

Тестовая ссылка: https://regex101.com/r/NV6Bk4/4

Он соответствует двоичному файлу и имени скрипта командной строки. Пример:

 php --strict myscript.php --arg=value

соответствует php и myscript.php в группе (1) и группе (2).

Проблема в этой части в середине: (?:.*?) , это приводит к комбинаторному взрыву, замедляя регулярное выражение для больших входных данных. Есть ли способ оптимизировать это? Поскольку нет никакой закономерности, я ничего не могу придумать.

Чтобы уточнить, правило, которому я пытаюсь соответствовать, таково: сопоставьте любой путь к команде, возможно, содержащий экранированные пробелы. Игнорируйте любые аргументы, следующие за ним. Сопоставьте файл, заканчивающийся на .php, игнорируйте все, что следует за ним. Команда должна быть в группе (1), имя файла должно быть в группе (2).

1. В какой среде вы запускаете регулярное выражение?

2. На самом деле, гораздо важнее знать настоящие правила. Что сопоставляется и почему? Проблема очевидна: последующие смежные шаблоны могут соответствовать одному и тому же типу символов.

3. Он будет работать в Java 8.

4. Проверьте ^([^s\]* (?:\.[^s\]*)*).*?(S .phpb) , посмотрите демонстрацию . Если ваши совпадения начинаются с начала строки, используйте ^ и используйте притяжательный квантификатор с первым отрицаемым символьным классом

5. Это выглядит многообещающе! Есть ли способ сделать это match() ? К сожалению, это ограничение, которое у меня есть.

Ответ №1:

Вы можете использовать следующее «исправление» с Matcher#matches() :

 ([^s\]* (?:\.[^s\]*)*).*?(S .phpb).*

В Java

 String regex = "([^\s\\]* (?:\\.[^\s\\]*)*).*?(\S \.php\b).*";

Смотрите демонстрацию регулярных выражений. Обратите внимание, что литерал . вне символьного класса должен быть экранирован. Скомпилируйте шаблон с Pattern.DOTALL помощью if, если строка может иметь разрывы строк.

Как вы видите, .*? часть соответствует любому символу, и (?:\.[^s\]*)* прежде чем она сможет соответствовать любым 0 или более символам (так что это своего рода необязательно), и следующий смежный шаблон .*? слева [^s\] — это тот, который может соответствовать тем же символам, .*? что и . Это означает, что механизм регулярных выражений может вернуться к первому подшаблону, и это создает множество способов сопоставления строки, обычно называемых катастрофическим возвратом.

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

Добавьте .* в конце, чтобы заставить его работать .matches() , так как этот метод требует полного совпадения строк.