2

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

  1. Какие процессы происходят между тем моментом как я написал регулярку и до того момента, как какой то механизм каким то образом находит подходящие строки и выдает результат?
  2. Смысл использовать всякие алгоритмы поиска строк типа Ахо Корася и БМХ если есть регулярки?

1 ответ 1

2

Для начала рекомендую прочитать книгу Джеффри Фридла «Регулярные выражения». Она приоткроет немного занавес тайны.

теперь по вопросам.

  1. Самое первое - регулярка парсится и преобразуется в более удобный для движка вид (иногда это называют компиляцией). Некоторые движки делают "граф" для машины состояний, некоторые делают сразу "байт код". пример на хабре. А потом по этому графу или "коду" проходятся и проверяют совпадение.

  2. Да, иногда имеет смысл. Если регулярка применяется разок-другой, то смысла в дополнительных алгоритмах нет. А если регулярка выполняется в нагруженном цикле, то алгоритмы поиска подстрок имеют смысл. Мой опыт показывает, что переписывание регулярок "один-к-одному" с перла на с++ (Qt), дает двукратное падение скорости обработки (программа - построчный парсинг большого (десятки мегабайт) текстового файла). Добавление пары if с проверкой на подстроку для отсеивания заведомо неверных вариантов выровняло скорость.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.