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 that you have read and understand our privacy policy and code of conduct.

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