Бесконечный поиск по регекспам.

Модератор: Модераторы разделов

Аватара пользователя
jojahti
Сообщения: 310

Бесконечный поиск по регекспам.

Сообщение jojahti »

Привет, это снова я пришёл доставать всех тупыми вопросами. :rolleyes:
Если соответствующего совпадения нету, иногда появляется такой эффект, как регексп ищется, ищется, ищется и т.д. даже nil не возвращается.
Например такой кусок текста. Прозреваю, что это из-за того, что он нулевые совпадения куда-то фигачит в астрономических количествах, потому что если поправить ((,?[ ]+)|)) на явное совпадение ((,?[ ]+)|(?=[.]))) , то всё начинает работать моментально.

text = "Firsthand the barbarians, those near-legendary."
puts "match" if text =~ /\A(([A-z]+)((,?[ ]+)|))+[.]/


От чего получается эффект бесконечного поиска?
Спасибо сказали:
watashiwa_daredeska
Бывший модератор
Сообщения: 4038
Статус: Искусственный интеллект (pre-alpha)
ОС: Debian GNU/Linux

Re: Бесконечный поиск по регекспам.

Сообщение watashiwa_daredeska »

jojahti писал(а):
12.04.2011 17:35
От чего получается эффект бесконечного поиска?
От перебора с возвратом. Мощные движки регекспов все как один жутко неэффективны в среднем и имеют кучу подводных камней. В подавляющем большинстве случаев можно обойтись более простым и на порядки более быстрым вариантом по алгоритму Томпсона + возможности ЯВУ.
http://swtch.com/~rsc/regexp/regexp1.html

Выяснять, почему именно в каком-то очередном движке глючит какая-то г…-оптимизация — занятие неблагодарное.
Спасибо сказали:
frp
Сообщения: 1445
ОС: Debian Squeeze

Re: Бесконечный поиск по регекспам.

Сообщение frp »

jojahti писал(а):
12.04.2011 17:35
От чего получается эффект бесконечного поиска?

От тупого алгоритма.

PS. Лично я делал бы сопоставление с регекспами так:
1. Строим автомат, в случае необходимости строим по несколько переходов на одну букву.
2. Мы сначала находимся в одном, начальном состоянии (мы одновременно можем находится в нескольких состояниях)
3. На каждом шаге берем очередную букву строки, которую сопоставляем с регекспом и переходим из всех состояний, в которых мы сейчас находимся, во все состояния, в которые мы можем с них перейти.

Если на каком-то этапе мы не можем никуда перейти - выходим и говорим, что строка не соответствует регекспу.
Если мы обработали всю строку и одно из текущих состояний - конечное - строка соответствует регекспу.

Сложность данного алгоритма в худшем случае - O(N*M), где N - длина строки, M - количество состояний автомата.
Спасибо сказали:
Аватара пользователя
/dev/random
Администратор
Сообщения: 5492
ОС: Gentoo

Re: Бесконечный поиск по регекспам.

Сообщение /dev/random »

frp, в POSIX RegEx так обычно и делается. Но в PCRE (которыми, похоже, и пользуется ТС) есть куча возможностей, принципиально нереализуемых таким способом.
Спасибо сказали: