Подстрочный матч быстрее с регулярным выражением?

Question

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

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

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

Answer 1

Прежде всего, я бы порекомендовал вам прочитать статью о внутренних регулярных выражениях на нескольких языках: Regular Expression Matching Can Be Simple And Fast.

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

Может быть выполнена реализация RE через DFA (с групповым захватом), но у него есть накладные расходы (см. Статью Лаурикари NFAs with Tagged Transitions, their Conversion to Deterministic Automata and Application to Regular Expressions).

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

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

Answer 2

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

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

Answer 3

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

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