Улучшение производительности регулярного выражения

Question

Мое программное обеспечение позволяет пользователям использовать регулярное выражение для подготовки файлов. Я в процессе добавления библиотеки regexp по умолчанию с общими выражениями, которые могут быть повторно использованы для подготовки различных форматов. Одной из общих задач является удаление crlf в определенных частях файлов, но не в других. Например, это:

<TU>Lorem 
    Ipsum</TU> 
    <SOURCE>This is a sentence 
    that should not contain 
    any line break. 
    </SOURCE> 

должны стать:

<TU>Lorem 
    Ipsum</TU> 
    <SOURCE>This is a sentence that should not contain any line break. 
    </SOURCE> 

У меня есть rexep, что делает работу очень хорошо:

(?(?<=<SOURCE>(?:(?!</?SOURCE>).)*)(\r\n)) 

Проблема заключается в том, что он обрабатывает интенсивный и файлов выше 500 КБ, это может занять 30+ секунд. (regex компилируется, в этом случае нескомпилированный намного медленнее)

Это не большая проблема, но мне интересно, есть ли лучший способ достичь тех же результатов с помощью Regex.

Заранее благодарим за ваши предложения.

Answer 1

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

\r\n(?=(?>[^<>]*(?><(?!/?SOURCE>)[^<>]*)*)</SOURCE>) 

Он начинается с соответствия \r\n, n использует lookahead, чтобы узнать, совпадает ли совпадение между <SOURCE> и </SOURCE>. Он делает это, ища </SOURCE>, но если он найдет <SOURCE>, сначала это не сработает. Атомные группы не позволяют сохранить информацию о состоянии, которая необходима для обратного отслеживания, потому что пропуск или отказ, возврат назад никогда не требуется.

Answer 2

«Компиляция» обычного выражения просто означает преобразование его из Deterministic Finite Automaton в Non-deterministic Finite Automaton. Это не «компиляция в машинный код», как вы могли ожидать.

NFAs обычно меньше, чем их соответствующие DFA, и может выполнять более пространство эффективно. Каждый DFA имеет по крайней мере один эквивалент NFA и наоборот. Однако Perl Compatible Regular Expressions не являются actually Regular. Поэтому я не знаю, что они преобразуются в NFA, или если «компиляция» просто другой формы лексического анализа, которая была сделана, однажды не нужно повторять.

PCREs медленны в соответствии с Russ Cox, частично из-за их нерегулярности, и ваше выражение выше довольно нерегулярно.

О, и если вы пытаетесь распознать вложенные теги с регулярными выражениями, не надо. Используйте реальный парсер (X|HT)?ML. Вы действительно не хотите, чтобы the pony приехал

Answer 3

Я бы предпочел отрицательное выражение для регулярного выражения, чтобы убедиться, что вы действительно можете сопоставить \r\n в текущей позиции. В противном случае движок должен сделать весь lookbehind (произвольный размер для загрузки) на каждом отдельном символе во всем файле, только чтобы узнать, что нет возврата каретки для замены.

(?=\r\n)(?(?<=<SOURCE>(?:(?!</?SOURCE>).)*)(\r\n)) 

должно быть намного быстрее. По крайней мере, в RegexBuddy для выполнения регулярного выражения требуется много меньше шагов. Если это не в .NET, я не знаю, почему. Возможно, условное регулярное выражение не так эффективно (я должен признать, что сначала я не узнал его и не думал о синтаксической ошибке в вашем регулярном выражении). Я думаю, что вам не нужно условное регулярное выражение в этом сценарии. Как насчет

\r\n(?<=<SOURCE>(?:(?!</?SOURCE>).)*) 

Это быстрее? Я предполагаю, что вы используете RegexOptions.Singleline для компиляции регулярного выражения.

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

1. Сопрягай <SOURCE> блок
2. Заменить все CRLFs внутри блока (не требуется регулярное выражения)
3. Заменить <SOURCE> блок