Почему Regex очень медленно завершает XML-файл из 3000 строк?

Question

Я заметил, что Regex очень медленно завершает файл XML с 3000 строками [1]:

\(<Annotation\(\s*\w\+="[^"]\{-}"\s\{-}\)*>\)\@<=\(\(<\/Annotation\)\@!\_.\)\{-}"MATCH\_.\{-}\(<\/Annotation>\)\@=

Я всегда думал, что регулярные выражения эффективны. Почему это так долго, чтобы закончить Regex?

[1] Как я могу несколько раз совпадать с A до B в VIM?

Answer 1

Это зависит от самого регулярного выражения, является ли оно эффективным или нет. То, что он делает неэффективным, - это возврат. И чтобы избежать этого, регулярное выражение должно быть как можно более четким.

Давайте возьмем в качестве примера регулярное выражение a.*b и применим его к строке abcdef. Алгоритм сначала сопоставляет литерал a в a.*b с a в abcdef. Далее будет обработано выражение .*. В обычном жадном режиме, где множители расширены до максимума, он будет соответствовать всему остальному bcdef в abdef. Чем будет обработан последний литерал b в a.*b. Но так как конец строки уже достигнут и используется мультипликатор, алгоритм попытается вернуться назад, чтобы соответствовать всему шаблону. Совпадение .* (bcdef) будет уменьшено на один символ (bcde), и алгоритм пытается выполнить остальную часть шаблона. Но b в a.*b не соответствует f в abcdef. Таким образом, .* будет уменьшаться еще на один символ, пока не совпадет с пустой строкой (таким образом, . повторяется ноль раз), а b в a.*b соответствует b в abcdef.

Как вы видите, a.*b, примененное к abdef, требует 6 подходов обратного отслеживания для .*, пока не совпадет все регулярное выражение. Но если мы изменим регулярное выражение и сделаем его отличным, используя a[^b]*b, обратного отслеживания не потребуется, и регулярное выражение может совпадать в первом подходе.

И если вы сейчас решите использовать вместо этого ленивые модификаторы, я скажу вам, что эти правила применяются ко всем модификаторам, как жадным, так и ленивым модификаторам. Разница заключается в том, что вместо того, чтобы сначала расширять совпадение до максимума, а затем делать возврат назад, уменьшая совпадение по одному символу за раз (жадные алгоритмы), ленивые модификаторы сначала расширяются до минимального совпадения, а затем увеличиваются по одному символу за раз.

Answer 2

RE эффективны , но не волшебны: -)

Это не количество строк во входном файле, которое замедляет вас (3000 - это очень небольшое число). Когда RE компилируется, он в основном должен (концептуально) написать программу, которая может анализировать входной файл на основе этого RE.

Скорость этой «программы» всегда зависит от сложности RE.

Например, "^$" будет очень быстрым, "[0-9]{1,9}" будет несколько медленнее и все, что связано с возвратом (т. Е. Необходимо выполнить резервное копирование в RE, обычно что-либо, включающее несколько предложений с переменным числом элементов, из которых ваш пример) будет еще медленнее.

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

Я не слишком беспокоюсь об оптимизации моих RE (но обычно они не такие сложные). Я считаю, что они займут столько же времени, сколько и. Если это слишком долго, я обычно ищу другое решение, которое быстрее, но не настолько адаптируемо.

В случае вашего RE, где вы хотели получить все XML-комментарии, где атрибут about содержит MATCH, я бы сделал это на Perl (или на awk для нас, старожилов :-), поскольку входной файл был разумно исправлен формат:

• «<Аннотация» в первой строке [a]. </li>
• "MATCH" также в первой строке [a].
• в последней строке и самостоятельно [b].

Это будет быстрый простой сканер строк, включающий эхо при выполнении условий [a] (и печать этой строки), печать любой другой строки при включенном эхо и отключение эха при условиях [b] выполнено (после печати строки).

Да, гораздо менее адаптируемый, но почти наверняка быстрее (учитывая ваш хорошо отформатированный ввод).

Answer 3

Мне очень трудно читать ваше регулярное выражение со всеми обратными слешами; если я правильно интерпретирую этот диалект регулярных выражений (vim?), то, что вы говорите, это то, что будет означать многословный pcre:

(?<= <Annotation(\s*\w+="[^"]*?"\s*?)*> )
    ((?! <\/Annotation).)*?
    "MATCH.*?
(?= <\/Annotation> )

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

Это жесткий для процессора, чтобы соответствовать; комбинация в значительной степени убивает любую возможную оптимизацию, которую она могла бы достичь. Для каждого символа в файле необходимо вернуться назад (возможно, к началу файла / концу предыдущего совпадения), чтобы увидеть, совпадает ли lookbehind, а затем сделать шаг вперед (потенциально к концу файла), ища "MATCH.

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

<Annotation(\s+(\w+="[^"]))*\s*>
    (.*? "MATCH .*?)
<Annotation>

Однако, как всегда с этим вопросом, Clippy sez:

Похоже, вы анализируете XML с помощью регулярных выражений.

Хотите помочь?

() Используйте настоящий синтаксический анализатор XML, потому что регулярное выражение по своей сути не в состоянии анализировать XML

() Просто солдат, делающий нечитаемые сложные регулярные выражения, которые все еще не работают

[] Не показывайте мне этот совет снова

Answer 4

«Регулярные выражения эффективны» - слишком широкая характеристика, чтобы быть точной. Если вы игнорируете различия в относительной производительности, предлагаемые различными движками Regex, то насколько эффективен ваш Regex, зависит от сложности шаблона.

Regex эффективен, когда он терпит неудачу быстрее, вместо того, чтобы быстрее соответствовать части текста. Итак, он должен быть достаточно конкретным, так что текст, который не будет полностью совпадать, должен быть отклонен на ранней стадии процесса сопоставления, а не до конца. Это также означает, что откат должен быть сведен к минимуму. Обратите внимание, что возврат может достигнуть катастрофических уровней , что приведет к зависанию даже самого лучшего двигателя Regex. В примере, представленном Яном Гойваэртсом, размер файла даже не упоминается и не имеет значения. Однако важен размер строки.

Вот ветка обсуждения Я начал на RegexAdvice.com несколько лет назад, чтобы попытаться заставить людей обсуждать производительность Регулярных выражений. Думаю, у него есть несколько указателей.