Блог

Главная - Вопросы по программированию - Очень медленное регулярное выражение в Java

Очень медленное регулярное выражение в Java

#regex #powershell

Вопрос:

Используя Java, я хочу определить, начинается ли строка со слов и разделителя, а затем «myword», но это регулярное выражение занимает слишком много времени. Что не так ?

 ^s*(w (s|/|amp;|-)*)*myword

Комментарии:

1. Что вы имеете в виду, говоря » занимает слишком много времени»? Узор слишком длинный? Или требуется много времени, чтобы вернуть результат с каким-то конкретным вводом?

2. В этом примере «Консультант DEPUIS JUILLET 2011 Монреаль» не возвращает никаких результатов ниже 60 секунд

3. Вам нужно String rx = "^\s*(\w (?:[\s/amp;-] \w )*)[\s/amp;-] myword"; , проверьте ideone.com/CT4ENA

4. Спасибо, это работает, но почему этот более эффективен ?

Ответ №1:

Шаблон ^s*(w (s|/|amp;|-)*)*myword неэффективен из-за вложенного квантора. w требуется по крайней мере один символ слова и (s|/|amp;|-)* может совпадать с нулем или более некоторых символов. Когда значение * применяется к группе, а входная строка не имеет разделителей между символами слов, выражение становится похожим на (w )* шаблон, который является классическим шаблоном катастрофического возврата.

Просто небольшая иллюстрация w и (w )* производительность:

w :                                                  (w )*

введите описание изображения здесь введите описание изображения здесь

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

В этом случае вы можете развернуть имеющуюся у вас группу как

 String rx = "^\s*(\w (?:[\s/amp;-] \w )*)[\s/amp;-] myword";

Смотрите демонстрацию IDEON

Здесь (w (s|/|amp;|-)*)* развернуто как (w (?:[s/amp;-] w )*) (я сохранил внешние скобки для создания группы захвата № 1, вы можете удалить эти скобки, если они вас не интересуют). w соответствует одному или нескольким словесным символам (поэтому это обязательный подшаблон), а (?:[s/amp;-] w )* подшаблон соответствует нулю или более ( * таким образом, вся эта группа необязательна) последовательностям одного или нескольких символов из определенного класса символов [s/amp;-] (поэтому это обязательно), за которыми следуют один или несколько словесных символов w .

Метки: