регулярное выражение в проблеме Java

Question

Я обнаружил некоторую проблему при тестировании моей системы NLP. У меня есть Java регулярное выражение "(.*\\.\\s*)*Dendryt.*" и для строки "v Table of Contents List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . " это просто не останавливать вычисления.

Понятно, что эта сложность регулярных выражений очень высока, я попытаюсь ее реорганизовать. Есть ли у вас какие-либо предложения для меня для будущего развития регулярных выражений ???

Спасибо.

Answer 1

Вы сталкиваетесь с катастрофическим возвратом , повторяя группу, содержащую повторяющиеся квантификаторы.Последующий комбинаторный взрыв (при достаточном вводе) приведет к переполнению стека (tada!) .

Упрощенно, ваше регулярное выражение пытается

(.*\.\s*) соответствоватьлюбая последовательность символов , включая точки и пробелы , за которыми следует точка, за которой следует ноль или более пробелов, а затем

(...)* повторяют это любое количество раз.

Dendryt Только тогда он пытается сопоставить «Дендрит».

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

В качестве иллюстрации приведен скриншот отладчика регулярных выражений RegexBuddy в упрощенной версии ваших данных:

Снимок экрана RegexBuddy http://img714.imageshack.us/img714/3275/screen017.png

Движок отказывается после 1 миллиона перестановок.

Ваше регулярное выражение будет немного лучше, как это (не забудьте избежать обратной косой черты при преобразовании его в строку Java):

(.*)(\.\s*)*+Dendryt

В этом случае *+, так называемый собственнический квантификатор, откажется откатываться после того, как его сопоставили.Таким образом, механизм регулярных выражений может выйти из строя намного быстрее, но он все еще плох, потому что (.*) соответствует всему , даже точкам.

([^.]*)(\.\s*)*+Dendryt

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

Answer 2

Попробуйте это:

"[^.]*+(?>\\.\\s*)*+Dendryt.*"

[^.]*+ потребляет все до первой точки, а + делает * притяжательным , поэтому регулярное выражение никогда не будет возвращаться после этой точки.

(?>\\.\\s*) - это атомная группа : она соответствует точке и любому последующему пробелу, как если бы она была одной единицей. Если механизм регулярных выражений должен вернуться к этой точке, он пропустит его прямо туда, где группа начала сопоставлять.

Но не вернется к этому моменту, потому что я также сделал квантификатор группы притяжательным. Я хотел проиллюстрировать использование атомных групп, но вместо этого я мог бы сделать \\s* притяжательным - или оба.

Притяжательные квантификаторы и атомные группы полностью отключают возврат, но использовать их не всегда возможно. Когда вам нужно разрешить возврат, сведите его к минимуму; не позволяйте квантификаторам потреблять больше, чем нужно. И особенно, как сказал Тим, избегайте вложенных квантификаторов и количественных подвыражений, которые могут совпадать.

На самом деле, это хорошее упражнение - избегать использования .* и .+; это заставляет вас думать о механике этого. Если нет ничего конкретного, что вы хотите сопоставить, подумайте о том, что вы не хотите сопоставить, например, когда я использовал [^.]* вместо первого .* в вашем регулярном выражении.