Я не новичок в использовании регулярных выражений, и я понимаю основную теорию, на которой они основаны, - машины с конечным состоянием.
Я не так хорошо разбираюсь в алгоритмическом анализе и не понимаю, как сравнивается регулярное выражение, например, базовый линейный поиск. Я спрашиваю, потому что на поверхности это похоже на поиск линейного массива. (Если регулярное выражение простое.)
Где я могу пойти, чтобы узнать больше об использовании механизма регулярных выражений?
Это один из самых популярных контуров: Регулярное соответствие выражений может быть простым и быстрым. Запуск скомпилированного регулярного выражения DFA для строки действительно O (n), но может потребовать до O (2 ^ m) время построения/пространство (где m = размер регулярного выражения).
Вы знакомы с термином "детерминированные/недетерминированные конечные автоматы"?
Реальные регулярные выражения (когда я говорю реальный Я имею в виду те регулярные выражения, которые распознают обычные языки, а не регулярное выражение, которое включает в себя почти все языки программирования с обратными ссылками, и т.д.) могут быть преобразованы в DFA/NFA, и оба могут быть реализованы механическим способом на языке программирования (NFA можно преобразовать в DFA).
Что вам нужно сделать:
Таким образом, с учетом регулярного выражения вы можете преобразовать его в DFA и запустить его, чтобы увидеть, соответствует ли он или нет указанному тексту.
Это может быть реализовано в O(n), потому что DFA не обращается назад (например, машина Тьюринга), поэтому он соответствует строке или нет. Это означает, что вы не будете принимать совпадения совпадений, иначе вам придется вернуться и снова начать сопоставление...
Классическое регулярное выражение может быть реализовано таким образом, чтобы оно было быстрым на практике, но имело очень плохое поведение в худшем случае (стандартный DFA) или таким образом, чтобы гарантировать разумное поведение в худшем случае (сохраняя его как NFA). Стандартный DFA может быть расширен для поддержки множества дополнительных совпадающих символов и флагов, которые используют тот факт, что это в основном поиск по отслеживанию.
Примеры стандартного подхода повсюду (например, встроены в Perl). Существует пример, в котором говорится о хорошем худшем поведении в http://code.google.com/p/re2/ - на самом деле это даже лучше, чем я ожидал в худшем случае, поэтому они возможно, нашли дополнительный трюк или два.
Если вы вообще заинтересованы в этом или заботитесь о написании программ, которые могут быть сделаны для блокировки твердых данных патологических входов, прочитайте http://swtch.com/~rsc/regexp/regexp1.html.