Я тестирую свое регулярное выражение в https://regex101.com/ перед выполнением каких-либо кодировок.Regex катастрофическое возвращение назад, когда не соответствует

Regex:

\[(.*?)\]((?:.\s*)*?)\[\/\1\]

Пример строки:

[tag1] Тест в Тест Текст Текст Текст Тест Тест текста.

Тестирование тестового текста Проверка текста «Текст текстового теста» Текст тестового текста.

Тестовый текст? Тестирование текстового теста Текстовый тест Текстовый тест Текстовый тест Текстовый тест Текст.

Тест Текст, Тест Тест Текст Текст Текст Тест Тест Тест Текст Текст Тест Текст Тест Текст. [/ Tag1]

[tag2] Тест в Тест Текст Текст Текст Тест Тест текста.

Тестирование тестового текста Проверка текста «Текст текстового теста» Текст тестового текста.

Тестовый текст? Тестирование текстового теста Текстовый тест Текстовый тест Текстовый тест Текстовый тест Текст.

Test Text, Test Text Test Text Test Text Test Text Test Text Test Text Test Text. [/ Tag2]

....

....

I Я пытаюсь захватить 2 группы в некоторых длинных строках. первый - это текст внутри квадратных скобок, а второй - текст внутри тега.

Регулярное выражение и строка выше не имеют проблем, когда регулярное выражение соответствует. Если в матче, сделанные шаги только 1000+ каждого матча. Но если открывающий и закрывающий теги не совпадают, происходит катастрофическое отступление, и матч заканчивается на 126 000+ шагов и прекращается поиск других соответствующих строк.

Я знаю, что для предотвращения проблемы обратного отслеживания необходимо избегать использования вложенных конструктов с «+» или «*», но я не могу найти лучшего способа сделать это.

Возможно, кто-то может предложить или предложить лучшее регулярное выражение, чем мое?

источник

2016-06-07 Ambrose

Я не уверен, что понимаю вашу проблему .... Когда возникает проблема? –

Кроме того, хотя я до сих пор не понимаю вашу проблему, возможно, попробуйте это регулярное выражение? '\ [([^]] +?) \] ([^ [] +) \ [\/\ 1 \]' –

Да, это работает, спасибо. Я просто хочу лучшее регулярное выражение, чем мое, не влияя на производительность позже, когда я применяю его к моему коду. – Ambrose

Предисловие

Первое, используйте соответствующую среду для тестирования. Если вы используете регулярное выражение в .NET, не проверяйте его в тесте регулярных выражений, который не поддерживает .NET regex.

Regex101.com НЕ поддерживает .NET regex!

Вы шаблон регулярного выражения не вызывает какие-либо катастрофические откаты со строкой вы публикуемой в RegexStorm.net.

первопричины

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

Повышение рисунка

enhacement не столь очевиден, но многие придут с раствором, как один дается Federico: использовать ленивую точку соответствия шаблона. Таким образом, (?s)\[([^]]*)](.*?)\[/\1] (demo) выглядит жизнеспособным решением. Он дает 7 843 итераций в секунду при RegexHero.net.

Используя разворачиваемый метод цикла, мы можем повысить производительность регулярного выражения n раз в зависимости от ввода. Здесь мы можем написать подшаблон .*? как любой символ, но [, а любой [ не следует /\1] до \[/\1].Это может быть написано с отрицаниями классов символов и опережение внутри 1 группы количественно (она даже не требует каких-либо модификаторов или флагов):

\[([^]]*)]([^[]*(?:\[(?!/\1])[^[]*)*)\[/\1]

См this RegexStorm demo. Этот шаблон регулярного выражения дает 114 225 итераций в секунду. Это связано с тем, что нет [ всего между [tag1] и [/tag1], производительность будет ухудшаться, если строка содержит много [ или состоит только из [ (что не должно происходить в реальной жизни).

Тестирование

Вот RegexHero тестирование:

Ваш оригинальный регулярное выражение дали только 5094 IPs на этом сайте.

источник

2016-06-07 20:30:22

Отличный инструмент. Не знал, что '[A-Za-z0-9 _] +' был на + 20% быстрее, чем '\ w +' –

Ну, это не идентичные шаблоны в .NET. '\ w' соответствует всем буквам Unicode (с диакритикой) и цифрам. –

@Wiktor Спасибо! Этот ответ определенно говорит много. После некоторого тестирования я могу сказать, что ваше регулярное выражение лучше. Mine не будет совпадать, если есть «[» символ между тегом, хотя их не будет. Наверное, я буду читать больше о lookahead в regex. Также, помогите объяснить, почему я не должен переоценивать свои шаблоны? Я думал, что я должен избегать всех специальных символов, чтобы избежать проблемы синтаксиса. – Ambrose

Я думаю, что катастрофический откат выходит из этого рисунка:

(?:.\s*)*?

Имея вложенное повторение в группе, которая может быть повторена всегда создает боль для регулярных выражений двигателей.Глядя на диаграмме регулярных выражений ясно, что ваш шаблон создает некрасивые накладные расходы:

Regular expression visualization

Вы могли бы улучшить свое регулярное выражение, чтобы иметь рисунок так:

\[(.*?)\](.*?)\[\/\1\]  // Using single line flag 
(?s)\[(.*?)\](.*?)\[\/\1\] // Using inline single line flag

Regular expression visualization

Working demo

Также вы, если лет у не хотите использовать флаг однолинейной вы можете использовать небольшой трюк, как это:

\[(.*?)\]([\s\S]*?)\[\/\1\]

Кроме того, могут оказаться полезными при помощи + (1 или более) оператора вместо * (0 или больше):

\[(.+?)\](.+?)\[\/\1\]

Regular expression visualization

источник

2016-06-07 19:37:49

Спасибо, что указали, что часть нарушена. Я всегда знаю, что шаблон является проблемой, но поскольку я новичок в регулярном выражении, я просто не могу думать лучше, чем тот, который у меня был. Это определенно дает мне некоторое представление о регулярном выражении. – Ambrose

По-видимому, это регулярное выражение: \[([^\]]+)\]([^\[]+)\[\/\1\] имеет значительно меньше шагов. Спасибо всем за ответы.

Demo

источник

2016-06-07 20:07:16 Ambrose

Во-первых, вы не должны переоценивать свои шаблоны. '[', поскольку первый символ в символьном классе не должен быть экранирован, а '' 'вне класса char не нужно экранировать. Затем '[^ [] +' соответствует одному или нескольким символам, отличным от '[', и что, если есть '[' символы между '[tag1]' и '[/ tag1]'? Это регулярное выражение не будет работать. И еще раз, не используйте regex101 для тестирования регулярного выражения .NET. Он неправильно проанализирует '[\ w- [az]]' шаблон. –

@ WiktorStribiżew В других вариантах регулярных выражений [например, Java, которые вы должны были бы избежать] (http://fiddle.re/9qx4ga) afaik. Я бы не сказал «overescaped» для более совместимого шаблона. Конечно, что-то вроде '[] []' (что будет работать в pcre для сопоставления квадратных скобок) выглядит круто, но на самом деле это не так (по крайней мере, я иногда использую). –

Этот шаблон для квадратных скобок относится к POSIX и является очень регулярным регулярным выражением. Интересно, почему JS, Java и процессоры регулярных выражений ICU были лишены этого классного умного размещения символов в классе символов. –

Regex катастрофическое возвращение назад, когда не соответствует

ответ

Предисловие

первопричины

Повышение рисунка

Тестирование

Смежные вопросы