совпадение подстроки быстрее с регулярным выражением?

Question

После прочтения RE / NFA и DFA, кажется, что нахождение подстроки в строке может на самом деле быть асимптотически быстрее, используя RE, а не поиск грубой силы O (mn). Я рассуждаю так, что DFA будет фактически поддерживать состояние и избегать обработки каждого символа в «стоге сена» более одного раза. Следовательно, поиск в длинных строках может быть намного быстрее, если он выполняется с помощью регулярных выражений.

Конечно, это действительно только для тех сопоставителей RE, которые конвертируют из NFA в DFA.

Кто-нибудь испытал лучшую производительность совпадения струн в реальной жизни, когда использовал RE, а не метод грубой силы?

Answer 1

Большинство регулярных выражений, используемых на практике, представляют собой PCRE (Perl-совместимые регулярные выражения), которые шире обычного языка и, следовательно, не могут быть выражены с помощью обычной грамматики.У PCRE есть такие вещи, как положительные / отрицательные утверждения типа «взгляд в сторону» или «взгляд назад» и даже рекурсия, поэтому при синтаксическом анализе может потребоваться обработка некоторых символов более одного раза.Конечно, все сводится к конкретной реализации RE: оптимизирована ли она, если выражения остаются в пределах обычной грамматики или нет.

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

Answer 2

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

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

Может быть реализация RE через DFA (с захватом группы), но у нее есть издержки (см. Статью Laurikari NFA с помеченными переходами,их преобразование в детерминированные автоматы и применение к регулярным выражениям ).

Для простого поиска по подстроке можно использовать алгоритм Knuth-Morris-Pratt , который создает DFA для поиска подстроки, и егоимеет оптимальную O (len (s)) сложность.Но это также накладные расходы, и если вы протестируете наивный подход (O (нм)) с этим оптимальным алгоритмом на реальных словах и выражениях (которые не так повторяются), вы можете обнаружить, что наивный подход лучше в среднем.

Для точного поиска подстроки вы также можете попробовать Boyer – Moore algo, который имеет O (mn) сложность в худшем случае, но работает лучше, чем KMP в среднем на реальных данных.

Answer 3

Если вы посмотрите на документацию по большинству языков, там будет упомянуто, что если вам не нужно использовать силу регулярного выражения, вы должны использовать версию без регулярного выражения из соображений производительности ... Пример: http://www.php.net/manual/en/function.preg-split.php заявляет: «Если вы вам не нужны возможности регулярных выражений, вы можете выбрать более быстрые (хотя и более простые) альтернативы, такие как explode () или str_split (). "

Это компромисс, который существует везде. Чем гибче и функциональнее решение, тем ниже его производительность.