1

Есть набор шаблонов для текстов, вида "Ваш заказ доступен по адресу: %w{1,3}. Забирайте скорее!", где %w{1,3} — "набор слов, разделённый одним или несколькими пробелами". Под "словом" понимаем набор букв, цифр, и ряда спецсимволов. {1,3} — квантификатор, работающий аналогично квантификаторам в регулярках. Задача в том, чтобы научиться за минимальное определять тексты на соответствие подобным шаблонам. Было решено преобразовывать такие шаблоны в регулярные выражение. Таким образом, из приведённого выше примера получиться регулярка:

/^Ваш заказ доступен по адресу:\s(?:\s*[\w\d\,\.\!]+\s*){1,3}\.\sЗабирайте скорее!$/u

Естественно, такая регулярка может вызывать проблемы в виде catastrophic backtracking, но способа её оптимизировать я не вижу, с учётом того, что пробелов между словами может быть сколько угодно. Буду благодарен за любые указания на мою слепость :)

1
  • Если вам дан исчерпывающий ответ, отметьте его как верный (галка напротив выбранного ответа). 21 мар 2016 в 7:06

1 ответ 1

2

Я вижу один способ оптимизации: использовать сверхжадный захват (1) строки, включая обязательное завершение с последующей определением наличия этого самого завершения ретроспективной (4) проверкой. (O(66) против O(2441) на тестовой не подходящей строке и одинаковой сложности для подходящих) В примере помечены точки, обсуждаемые в тексте:

/Ваш заказ доступен по адресу:\s(?>\s*[\w\d\,\.\!]+\s*\.?){3,5}(?<=\.\sЗабирайте скорее!)$/
                                  ^1                   ^2  ^3   ^4

Но тут есть сложности с построением такого выражения из первичной строки. Во первых нам надо что бы вся "правильная" строка до самого конца могла быть захвачена набором символов, указанных в квадратных скобках. Во вторых, нам надо посчитать из скольких "слов" состоит часть строки, после применяемой маски. И увеличить на это кол-во слов квантификатор (3). Кроме того, в отличие от вашего варианта жадный захват считает отдельно стоящую точку (перед которой пробел) за отдельное слово, из за этого в конец захватываемого выражения, после пробела пришлось добавить возможность такой точки (2).

Собственно точка - это основной камень преткновения. Допустимость знака точка в середине слов (по вашему abc.def - это одно слово). Если бы она могла быть только в конце слов, то могли бы быть другие, менее жесткие варианты.

Ну и конечно, ваши регулярные выражения (вы не указали какой диалект у вас) должны поддерживать сверхжадный захват

UPD По такому предложению ReinRaus:

/Ваш заказ доступен по адресу:(?:\s++(?:[\w\d,!]++|\.)*?){1,3}\s*+\.\sЗабирайте скорее!$/

Так гораздо проще для генерации ...

6
  • Да, точно. Проблема в точке, которая может быть частью "слова" и входит в обязательный текст в конце
    – ReinRaus
    20 мар 2016 в 15:04
  • @ReinRaus Ага, я ее долго пытался обойти ...
    – Mike
    20 мар 2016 в 15:05
  • Вы обошли ее интересным способом, я бы сделал так: regex101.com/r/iW2iA7/4 , но это дает немного больше шагов.
    – ReinRaus
    20 мар 2016 в 15:09
  • @ReinRaus Шаги это не особо страшно, когда их не тысячи. Да, у вас гораздо проще для генерации
    – Mike
    20 мар 2016 в 15:15
  • Большое спасибо @Mike за подробный ответ и @RainRaus за удобное для генерации выражение. Однако проблема в том, что каждая точка будет считаться как отдельное "слово" , а кто-нибудь рано или поздно додумается сделать. например. так: "Ваш заказ доступен по адресу: ул. Ленина, 6... Заберите его скорее!" Т.к. скорость генерации регулярок некритична, скорее всего сделаем так: Правило вида Ваш заказ доступен по адресу: %w{1,3}. Забирайте скорее! Будет преобразоваываться в рег. выражение: /^Ваш заказ доступен по адресу:\s(?:[\w\d\,\.\!]+)(?:\s++[\w\d\,\.\!]+){1,3}\.\sЗабирайте скорее!$/u 21 мар 2016 в 11:11

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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