How to become an author
Search
Write a publication
Pull to refresh

Comments 43

Вы просто читаете мысли :-)
Total votes 1: ↑1 and ↓0+1
/http:\/\/(?:[a-z]+.)?habrahabr.ru\/blogs?\/(?:[a-z_0-9]+\/)?\d+\//

check here
Total votes 2: ↑2 and ↓0+2
пардон, /http:\/\/(?:[a-z]+\.)?habrahabr\.ru\/blogs?\/(?:[a-z_0-9]+\/)?\d+\//
Total votes 2: ↑1 and ↓10
Так не указано, но явно подразумевается, что результирующий regexp должен дать true на строках «похожих» на основной набор и false на строках, совсем не похожих.

.* не соответствует второму требованию.
Total votes 1: ↑1 and ↓0+1
не понятно только, где это могло понадобиться?
Total votes 2: ↑2 and ↓0+2
При реализации или настройке спамфильтров, например.
Total votes 2: ↑2 and ↓0+2
А для чего такие сложности?
Судя по тому, что в итоговый шаблон вы в конец и начало ставите маркеры начала и конца строки — значит вы этой регулярке будете подсовывать по одному слову или конкретные строки сопоставимые заданным (уж не тексты ли вы туда предлагаете вводить).

В таком случае, я бы просто сделал список альтернатив ^(S1|S2|...|SN)$ и всё.
Итогом предложенной вами минимизации в общем случае, вероятно, будет более медленное регулярное выражение, если речь идет о PCRE, не говоря уже о накладных расходах на её создание.

Критикуйте и пользуйтесь.
Вы забыли привести пример реализации, чтобы было чем пользоваться. Пока что одни непонятки, может продемонстрируете что-то более конкретное?
Total votes 3: ↑3 and ↓0+3
Поддерживаю! Более-менее разумный компилятор регулярных выражений должен проделывать эту работу намного лучше. Хотя, чем чёрт не шутит.
В общем, хотелось бы увидеть тест от автора топика, где он сравнивает скорость обработки своих регэкспов с тривиальным ^(S1|S2|...|SN)$
Total votes 1: ↑1 and ↓0+1
N прядка 1000 — 5000. К томуже как регексп затем будет пользоваться для отыскания строк, схожих по структуре с S1..SN. Тривиальное объединение с «или» никуда не годиться.
Total votes 3: ↑3 and ↓0+3
Ну это как бы не серьезно… Вы пример покажите, еще лучше с тестами, тогда будет видно, что годится, что не годится. Потому что глядя на то, как вы меняете некоторые части на .* — ваша правота вызывает сомнение. Но вроде как и убедится не на чем — ни тестовых данных ни строк, ни даже структуры вы не показываете, зато делаете какие-то выводы. Тем более альтернативы у вас все равно останутся для различающихся подстрок.

Причем возможно вы и правы, например в случае Sn строк имеющих общий префикс, скажем P и разные остатки SRi, приведение регулярки к виду ^(P(?:SR1|SR2|...|SRN))$ безусловно даст выигрыш, но это явно не общий случай.

P.S. А вы на каком языке пишете? Интересно потому что регулярка с 1000-1500 вариатив произвольной длины — это само по себе жесть. Почему бы не воспользоваться более приземленными функциямипоиска подстрок в цикле? И какой тип RE?
Total votes 3: ↑3 and ↓0+3
>>Вы забыли привести пример реализации, чтобы было чем пользоваться.
пользоваться можно не только реализацией, но и алгоритмом ;)
Total votes 1: ↑1 and ↓0+1
И как ваш алгоритм отреагирует на «asd873gr@» и «yui21qw%»? А человек вполне нормально построит регэксп, исходя из вашего задания.
Total votes 1: ↑1 and ↓0+1
Пример приведите какой-нибудь. А то непонятно, как вы собираетесь по построенному дереву собирать регэксп. И как потом объединяете SX и S3 тоже совершенно непонятно.
Total votes 1: ↑1 and ↓0+1
Используем симметричный обход дерева:
1. в каждом узле есть некоторая строка.
2. Для корня получаем регексп — сперва получаем регексп из левого поддерева (пусть UL)
3. Дополняем его строкой в корне (пусть UL||U)
4. Дополняем его regexp'om из правого поддерева (UL || U || UR)
5. Регекспы из левого и правого поддеревьев строятся рекурсией.

Объединение SX и S3: для первого пункта берете S1=SX, S2=S3 и повторяете первый пункт в точности.
Total votes 1: ↑1 and ↓0+1
Офф топ.
если у программиста есть проблема и он думает — «Я решу ее при помощи регулярных выражений», то с этого момента у программиста уже две проблемы.
Total votes 21: ↑17 and ↓4+13
Автор, может перенесете этот топик в блог Алгоритмы?
Было бы интересно привлечь к обсуждению вопроса больше специалистов. Ну и вообще самое место ему там, вроде.
Total votes 2: ↑2 and ↓0+2
Спасибо. Только зачем вы поменяли содержимое топика(весьма сильно надо сказать) и не написали, что это апдейт? Если вы рассчитываете на обсуждение в комментариях — то не надо запутывать людей. Некоторые комментарии начинают выглядеть глупо для вновь читающих, после того, как топик изменен, они же не знают каким он был, и чего это тут народ про примера хочет, хотя он в топике есть же…

Off: Очень жаль, что на Хабре у топика не пишется дата модификации
Total votes 2: ↑2 and ↓0+2
Честно говоря, не вижу смысла в таком решении. И саму задачу не понимаю. Формулировка в виде «На входе алгоритма есть набор строк S1..SN. Требуется, по данным строкам построить такое минимальное регулярное выражение R, чтобы R(Si)=true, i [1,N] (N порядка нескольких тысяч)» сразу даёт решение «.*». Если бы было добавлено условие «R(X)=false для любого X не из множества {S1,…,SN}», то задача была бы более разумной.
Total votes 2: ↑2 and ↓0+2
:)
Ну это наверно подразумевалось, ведь .* совпадет с любой строкой, даже пустой, т.е. в таком варианте регулярка вообще не нужна, ибо ее результат всегда true. Просто автор забыл дописать еще одно формальное условие
Total votes 2: ↑2 and ↓0+2
Если бы было добавлено условие «R(X)=false для любого X не из множества {S1,…,SN}» задача сводилась бы к проверки на принадлежность X к данному множеству, что мне кажется ненамного более разумным.
This comment wasn’t rated yet0
Изначально стояла задача искусственного интеллекта, которая уже давно решена стандартными способами. Это классификаторы вроде нейронных сетей.

Но ваше решение мне тоже нравится! :)
Total votes 3: ↑2 and ↓1+1
Покажите, пожалуйста, что программа выведет на таком входе:

S1=http://habrahabr.ru/blogs/edu_2_0/40236/
S2=http://habrahabr.ru/blogs/microsites/40089/
S3=http://habrahabr.ru/blogs/google_chrome/38748/
S4=http://habrahabr.ru/blogs/show/37839/
S5=http://nikolaikopernik.habrahabr.ru/blog/54889/
S6=http://habrahabr.ru/blogs/telecom/39902/
S7=http://gmail.com

Total votes 1: ↑1 and ↓0+1
Эх. Всё, конечно, правильно, но в моем случае хотелось бы получать что то вроде
REGEXP = ^http://(.*habrahabr.ru/blog.*|gmail.com)/$
Total votes 6: ↑6 and ↓0+6
согласен, сам подумываю над оптимизацией алгоритма. Для этого в некоторых случаях при постоении дерева если нет общих подстрок возвращаем не ".*", а "(S1L | S2L)". Я там написал, что возможна оптимизация.
This comment wasn’t rated yet0
Хм. Задача таки непонятна. Вас устраивает что в данный регексп будет проходить такая строка?
banahabrahabr.ru/blogogohrenoten/
Total votes 1: ↑1 and ↓0+1
меня устраивает. Сила его в том, что не будет проходить подобные строки:
F=http://habrahabr.ru/forum/google_chrome/38748/ false
F=http://habrahabr.ru/shop/item/37839 false

да, алгоритм специфический — тут главное — основная идея. На этапе вставок ".*" вы можете поэкспериментировать с регулярными выражениями.
This comment wasn’t rated yet0
:) читайте пункт 1 (2 точка сверху) — мой алгорим как раз использует алгоритм нахождения наибольшей общей подстроки.
This comment wasn’t rated yet0
Плохо в этом алгоритме то, что он находит не только заданные строки Si, но и многие другие. Чем это много лучше .* мне лично неясно.
Total votes 4: ↑3 and ↓1+2
Это стандартная проблема всех классификаторов — недоученность и переученность. Этот алгоритм кренит в сторону недоучивания.
Total votes 1: ↑1 and ↓0+1
Очень весело узнавать полное условие задачи («Это очень грубое выражение, но оно подходит для моей задачи» в предпоследнем пункте) только после того, как прочтешь решение :)
Total votes 1: ↑1 and ↓0+1
если строки это исключительно URLи, то на мой взгляд стоит учитывать их заранее известную структуру при построении регулярного выражения.

Вообще странно, что вы ничего не нашли похожего… Можно было попробовать, например, начинать информационные раскопки с алгоритма Ахо-Корасик (он правда для поиска множества подстрок в строке, но как раз строит автомат)
Total votes 1: ↑1 and ↓0+1
Я просто сейчас под влиянием курса по обучающимся системам…
Возможно, стоит отказаться от регярок в сторону SVM или LDA?
Перевести все строки в какое-нибудь n-мерное пространство и попробывать найти linear classifier?
Total votes 2: ↑1 and ↓10
возможно. Попробуйте подумать о возможном алгоритме. Это действительно интересно.
This comment wasn’t rated yet0
Сам недавно столкнулся с такой задачей, пришел к похожему алгоритму. С той разницей что я искал первую попавшуюся общую подстроку достаточной длины, то есть последовательно, а не делением на две части.

зы. Думаю что всё-таки .*? надо вставлять, или у вас установлен флаг «не жадности»? (не знаю как оно в яве)
Total votes 1: ↑1 and ↓0+1
А разве есть разница «жадного» и «ленивого» флагов при наличии символов начала и конца строки?
This comment wasn’t rated yet0
решать задачу от обратного в данном случае прощще,
нужно искать плохие строки их меньше и регулярное выражение у них будет короче.

Автору респект, он начал так мной и не начатый проект под кодовым названием «Regexp from Heap»
This comment wasn’t rated yet0
Sign up to leave a comment.

Articles

Show the best of all time

Your account

Sections

Information

Services

Support
© 2006–2024, Habr