Православный взгляд на ИТ
Архив форума
Мы и братия наши как бы две картины. Если человек, смотря на себя, находит в себе недостатки, то в брате своем он видит совершенства. Если же сам себе кажется совершенным, то, сравнивая с собой брата, находит его худым.
Авва Исаия

 О регулярных выражениях
Александр Иванов - 22:34 30.07.2005
Нет ли на форуме человека, хорошо разбирающегося в перловых (либо php-шных) регулярных выражениях? Нужна помощь в одной непростой задачке.

 Re: О регулярных выражениях
Братец Дыкъ - 01:42 01.08.2005
Александр Иванов, Вы писали:
> Нет ли на форуме человека, хорошо разбирающегося в перловых (либо php-шных) регулярных выражениях? Нужна помощь в одной непростой задачке.


Саша, ты брось эту задачку сюда, так вернее кто-то поможет, чем объявлять ждать человека, который объявит себя экспертов в перловых регулярных выражениях. :)

От себя же могу сразу сказать, если задачка с RE "непростая", ни их нафиг эти RE. :)
RE - замячательны при решении простых задач, но плохо маштабируются по мере увеличения сложности. Пиши свой парсер, разбивай задачу на группу более простых подзадач, которые решай с RE, но не трать время на написание сложного RE.

 Сам вопрос
Александр Иванов - 13:14 01.08.2005
Сам вопрос в следующем. Требуется в тексте отлавливать и преобразовывать ссылки вида ((Ссылка какая-то)) в гиперссылку. Сложность в том, что в тексте самой ссылки могут встречаться скобки, но не двойные, а также сама ссылка может быть заключена в одинарные скобки. Сейчас это реализовано не RE, а разбором строки с рекурсией. Подумал, что замена анализа на RE ускорит обработку форматтера.

Дело вот в чем. Я продолжаю работу над офлайн-клиентом для энциклопедии. До недавнего времени идеалогия состояла в том, что необходимые функции форматтера я переписывал заново на Delphi со всеми вытекающими - двойная работа, больше шансов сделать ошибку. Сейчас я нашел модуль, который позволяет запускать php-скрипты прямо из Delphi, таким образом можно использовать для клиента тот же модуль форматирования, что и для Древа - очень заманчиво. Это работает, но наблюдаются сильные тормоза - страница Календарь (несколько сотен ссылок) открывается около 3-х секунд, выглядит не очень красиво. Когда использовался форматтер, написанный на Delphi, таких тормозов не было. Вот я и стал думать об оптимизации кода, прежде чем отвергнуть саму идею использования php в Delphi.

 Re: Возможный ответ
Братец Дыкъ - 01:20 02.08.2005
Александр Иванов, Вы писали:
> Сам вопрос в следующем. Требуется в тексте отлавливать и преобразовывать ссылки вида ((Ссылка какая-то)) в гиперссылку. Сложность в том, что в тексте самой ссылки могут встречаться скобки, но не двойные, а также сама ссылка может быть заключена в одинарные скобки. Сейчас это реализовано не RE, а разбором строки с рекурсией. Подумал, что замена анализа на RE ускорит обработку форматтера.


Понятно.
Я бы использовал preg_replace_callback с таким патерном:
\(\((.+?)\)\)(?=\))

Объясняю его по частям:
1) \(\( - наши открфвадщие двойные строчки
2) ( - начало сабпатерна, того что мы хотим получить в результате матча RE
3) .+? - тут подробней: .+ - любая не пустая подстрока, ? - означает что мы включаем nongreedy match подробней об этом позже.
4) ) и \)\) - обратное пунктам 1 и 2

Остановимся пока на этом. Если бы мы включили такое RE и без ? в п.3, то PHP нашелбы самую длиную подстроку подходящую под эти условия, слепляя все ссылки в одну. В примере:
"((аааа) бб ((ввв)) ггг", он бы выбрал: "((аааа) бб ((ввв))", и дал бы матч: "аааа) бб ((ввв", что совсем не то что нам надо.

Для этого и были придуманы nongreedy модификаторы.
Знак вопроса после ., + или же ?, сообщает движку что в этом месте надо найти не самую длиную подстроку удолитворяющую патерну, а самую короткую. В нашем примере мы мачнем "аааа" и "ввв", как нам и надо.

Но тут возникает другая проблема. В подстроке"аа ((ббб (бб))) ввв", мы получим результат: "аа ^((ббб (бб))^) ввв" (матч помечен символами "^"), что нам не подходит. Чтобы поправить это мы воспользуемся одним из видов assertions, а именно negative look ahead, который составляет последнюю часть нашего RE: "(?=\))". Assertion это тоже патерн, но он сам не участвует в матче, а только говорит что должно быть или небыть впереди или позади успешного матча. В данном случае "(?=" говорит, что сразу за матчем не должна идти круглая скобочка.

Почему тут надо использовать assertion, а не просто продлить патерн, таким образом: "\(\((.+?)\)\)[^)]"? Дело в том что при такой записи RE символ идущий за закрывающей скобочкой (то что мы кодируем: "[^)]") тоже попадет в матч, а RE движки устроенны таким образом что они ищут только не перекрывабшиеся совпадения (иначе бы при их реализации наступил бы хаос), поэтому следущий матч движок начнет искать *за этим символом*. Что в случае вдвух ссылок вплотную, приведет к тому что вторая ссылка будет пропущена.

Вот вроде и все c RE.
В каллбеке же для preg_replace_callback, надо будет проверить, являются ли первый и последний символ "(" и ")" соответсвенно, это будет означать что ссылка взята в скобочки и ее красивей будет показывать "([A]xxxxx[\A])" а не "[A](xxxxx)[\A]". А также посмотреть нет ли в строке знака равно - сам знаешь что с ним нужно делать. :)

Будет ди это быстрее чем рекурсивный парсер - покажет только опыт, нетривиальные регулярные выражения - очень капризны вплане перфоманса. Но тут интуиция мне подсказывает все должно быть тип-топ.

P.S.
Приведенное выше RE я не тестировал, в нем возможны опечатки, но надеюсь идея понятна.

 Re: Возможный ответ
Александр Иванов - 11:03 02.08.2005
Костя, за идею спасибо, только реализация пока не получилась - не находит ни одной ссылки. Если найдешь баг раньше меня - дай знать, пожалуйста.

 Результаты тестирования
Александр Иванов - 12:30 02.08.2005
Убрал (?=\)), большинство ссылок заработало, в т.ч. календарь. Проверил, результаты печальные. При использовании php парсер и RE дают примерно одинаковые результаты, около 2500 мсек. В то время как дельфовый парсер дает около 240 мсек. Вряд ли имеет смысл дальше рыть, буду использовать только Дельфи.

Была еще шальная мысль вообще отказаться от Дельфи, а писать клиент на php, установка клиента подразумевала бы установку среды для запуска php. Пока отказался от этой идеи, поскольку для удобства потребуется широкое применение javascript, я с ним мало знаком.


Архив форума