Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 43
.*
не понятно только, где это могло понадобиться?
А для чего такие сложности?
Судя по тому, что в итоговый шаблон вы в конец и начало ставите маркеры начала и конца строки — значит вы этой регулярке будете подсовывать по одному слову или конкретные строки сопоставимые заданным (уж не тексты ли вы туда предлагаете вводить).
В таком случае, я бы просто сделал список альтернатив ^(S1|S2|...|SN)$ и всё.
Итогом предложенной вами минимизации в общем случае, вероятно, будет более медленное регулярное выражение, если речь идет о PCRE, не говоря уже о накладных расходах на её создание.
Судя по тому, что в итоговый шаблон вы в конец и начало ставите маркеры начала и конца строки — значит вы этой регулярке будете подсовывать по одному слову или конкретные строки сопоставимые заданным (уж не тексты ли вы туда предлагаете вводить).
В таком случае, я бы просто сделал список альтернатив ^(S1|S2|...|SN)$ и всё.
Итогом предложенной вами минимизации в общем случае, вероятно, будет более медленное регулярное выражение, если речь идет о PCRE, не говоря уже о накладных расходах на её создание.
Критикуйте и пользуйтесь.Вы забыли привести пример реализации, чтобы было чем пользоваться. Пока что одни непонятки, может продемонстрируете что-то более конкретное?
Поддерживаю! Более-менее разумный компилятор регулярных выражений должен проделывать эту работу намного лучше. Хотя, чем чёрт не шутит.
В общем, хотелось бы увидеть тест от автора топика, где он сравнивает скорость обработки своих регэкспов с тривиальным ^(S1|S2|...|SN)$
В общем, хотелось бы увидеть тест от автора топика, где он сравнивает скорость обработки своих регэкспов с тривиальным ^(S1|S2|...|SN)$
N прядка 1000 — 5000. К томуже как регексп затем будет пользоваться для отыскания строк, схожих по структуре с S1..SN. Тривиальное объединение с «или» никуда не годиться.
Ну это как бы не серьезно… Вы пример покажите, еще лучше с тестами, тогда будет видно, что годится, что не годится. Потому что глядя на то, как вы меняете некоторые части на .* — ваша правота вызывает сомнение. Но вроде как и убедится не на чем — ни тестовых данных ни строк, ни даже структуры вы не показываете, зато делаете какие-то выводы. Тем более альтернативы у вас все равно останутся для различающихся подстрок.
Причем возможно вы и правы, например в случае Sn строк имеющих общий префикс, скажем P и разные остатки SRi, приведение регулярки к виду ^(P(?:SR1|SR2|...|SRN))$ безусловно даст выигрыш, но это явно не общий случай.
P.S. А вы на каком языке пишете? Интересно потому что регулярка с 1000-1500 вариатив произвольной длины — это само по себе жесть. Почему бы не воспользоваться более приземленными функциямипоиска подстрок в цикле? И какой тип RE?
Причем возможно вы и правы, например в случае Sn строк имеющих общий префикс, скажем P и разные остатки SRi, приведение регулярки к виду ^(P(?:SR1|SR2|...|SRN))$ безусловно даст выигрыш, но это явно не общий случай.
P.S. А вы на каком языке пишете? Интересно потому что регулярка с 1000-1500 вариатив произвольной длины — это само по себе жесть. Почему бы не воспользоваться более приземленными функциямипоиска подстрок в цикле? И какой тип RE?
>>Вы забыли привести пример реализации, чтобы было чем пользоваться.
пользоваться можно не только реализацией, но и алгоритмом ;)
пользоваться можно не только реализацией, но и алгоритмом ;)
И как ваш алгоритм отреагирует на «asd873gr@» и «yui21qw%»? А человек вполне нормально построит регэксп, исходя из вашего задания.
Пример приведите какой-нибудь. А то непонятно, как вы собираетесь по построенному дереву собирать регэксп. И как потом объединяете SX и S3 тоже совершенно непонятно.
Используем симметричный обход дерева:
1. в каждом узле есть некоторая строка.
2. Для корня получаем регексп — сперва получаем регексп из левого поддерева (пусть UL)
3. Дополняем его строкой в корне (пусть UL||U)
4. Дополняем его regexp'om из правого поддерева (UL || U || UR)
5. Регекспы из левого и правого поддеревьев строятся рекурсией.
Объединение SX и S3: для первого пункта берете S1=SX, S2=S3 и повторяете первый пункт в точности.
1. в каждом узле есть некоторая строка.
2. Для корня получаем регексп — сперва получаем регексп из левого поддерева (пусть UL)
3. Дополняем его строкой в корне (пусть UL||U)
4. Дополняем его regexp'om из правого поддерева (UL || U || UR)
5. Регекспы из левого и правого поддеревьев строятся рекурсией.
Объединение SX и S3: для первого пункта берете S1=SX, S2=S3 и повторяете первый пункт в точности.
Офф топ.
если у программиста есть проблема и он думает — «Я решу ее при помощи регулярных выражений», то с этого момента у программиста уже две проблемы.
если у программиста есть проблема и он думает — «Я решу ее при помощи регулярных выражений», то с этого момента у программиста уже две проблемы.
Автор, может перенесете этот топик в блог Алгоритмы?
Было бы интересно привлечь к обсуждению вопроса больше специалистов. Ну и вообще самое место ему там, вроде.
Было бы интересно привлечь к обсуждению вопроса больше специалистов. Ну и вообще самое место ему там, вроде.
о, конечно! Сам искал подобный блог.
Спасибо. Только зачем вы поменяли содержимое топика(весьма сильно надо сказать) и не написали, что это апдейт? Если вы рассчитываете на обсуждение в комментариях — то не надо запутывать людей. Некоторые комментарии начинают выглядеть глупо для вновь читающих, после того, как топик изменен, они же не знают каким он был, и чего это тут народ про примера хочет, хотя он в топике есть же…
Off: Очень жаль, что на Хабре у топика не пишется дата модификации
Off: Очень жаль, что на Хабре у топика не пишется дата модификации
Честно говоря, не вижу смысла в таком решении. И саму задачу не понимаю. Формулировка в виде «На входе алгоритма есть набор строк S1..SN. Требуется, по данным строкам построить такое минимальное регулярное выражение R, чтобы R(Si)=true, i [1,N] (N порядка нескольких тысяч)» сразу даёт решение «.*». Если бы было добавлено условие «R(X)=false для любого X не из множества {S1,…,SN}», то задача была бы более разумной.
:)
Ну это наверно подразумевалось, ведь .* совпадет с любой строкой, даже пустой, т.е. в таком варианте регулярка вообще не нужна, ибо ее результат всегда true. Просто автор забыл дописать еще одно формальное условие
Ну это наверно подразумевалось, ведь .* совпадет с любой строкой, даже пустой, т.е. в таком варианте регулярка вообще не нужна, ибо ее результат всегда true. Просто автор забыл дописать еще одно формальное условие
Если бы было добавлено условие «R(X)=false для любого X не из множества {S1,…,SN}» задача сводилась бы к проверки на принадлежность X к данному множеству, что мне кажется ненамного более разумным.
Изначально стояла задача искусственного интеллекта, которая уже давно решена стандартными способами. Это классификаторы вроде нейронных сетей.
Но ваше решение мне тоже нравится! :)
Но ваше решение мне тоже нравится! :)
Покажите, пожалуйста, что программа выведет на таком входе:
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
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
— REGEXP = ^http://.*$
SIZE: 6
TIME: 0.0070 s
SIZE: 6
TIME: 0.0070 s
Эх. Всё, конечно, правильно, но в моем случае хотелось бы получать что то вроде
REGEXP = ^http://(.*habrahabr.ru/blog.*|gmail.com)/$
REGEXP = ^http://(.*habrahabr.ru/blog.*|gmail.com)/$
согласен, сам подумываю над оптимизацией алгоритма. Для этого в некоторых случаях при постоении дерева если нет общих подстрок возвращаем не ".*", а "(S1L | S2L)". Я там написал, что возможна оптимизация.
Хм. Задача таки непонятна. Вас устраивает что в данный регексп будет проходить такая строка?
banahabrahabr.ru/blogogohrenoten/
banahabrahabr.ru/blogogohrenoten/
меня устраивает. Сила его в том, что не будет проходить подобные строки:
F=http://habrahabr.ru/forum/google_chrome/38748/ false
F=http://habrahabr.ru/shop/item/37839 false
да, алгоритм специфический — тут главное — основная идея. На этапе вставок ".*" вы можете поэкспериментировать с регулярными выражениями.
F=http://habrahabr.ru/forum/google_chrome/38748/ false
F=http://habrahabr.ru/shop/item/37839 false
да, алгоритм специфический — тут главное — основная идея. На этапе вставок ".*" вы можете поэкспериментировать с регулярными выражениями.
Если я правильно понял задачу, то она похожа на нахождение наибольшей общей подпоследовательности.
Плохо в этом алгоритме то, что он находит не только заданные строки Si, но и многие другие. Чем это много лучше .* мне лично неясно.
Очень весело узнавать полное условие задачи («Это очень грубое выражение, но оно подходит для моей задачи» в предпоследнем пункте) только после того, как прочтешь решение :)
если строки это исключительно URLи, то на мой взгляд стоит учитывать их заранее известную структуру при построении регулярного выражения.
Вообще странно, что вы ничего не нашли похожего… Можно было попробовать, например, начинать информационные раскопки с алгоритма Ахо-Корасик (он правда для поиска множества подстрок в строке, но как раз строит автомат)
Вообще странно, что вы ничего не нашли похожего… Можно было попробовать, например, начинать информационные раскопки с алгоритма Ахо-Корасик (он правда для поиска множества подстрок в строке, но как раз строит автомат)
Я просто сейчас под влиянием курса по обучающимся системам…
Возможно, стоит отказаться от регярок в сторону SVM или LDA?
Перевести все строки в какое-нибудь n-мерное пространство и попробывать найти linear classifier?
Возможно, стоит отказаться от регярок в сторону SVM или LDA?
Перевести все строки в какое-нибудь n-мерное пространство и попробывать найти linear classifier?
Сам недавно столкнулся с такой задачей, пришел к похожему алгоритму. С той разницей что я искал первую попавшуюся общую подстроку достаточной длины, то есть последовательно, а не делением на две части.
зы. Думаю что всё-таки .*? надо вставлять, или у вас установлен флаг «не жадности»? (не знаю как оно в яве)
зы. Думаю что всё-таки .*? надо вставлять, или у вас установлен флаг «не жадности»? (не знаю как оно в яве)
решать задачу от обратного в данном случае прощще,
нужно искать плохие строки их меньше и регулярное выражение у них будет короче.
Автору респект, он начал так мной и не начатый проект под кодовым названием «Regexp from Heap»
нужно искать плохие строки их меньше и регулярное выражение у них будет короче.
Автору респект, он начал так мной и не начатый проект под кодовым названием «Regexp from Heap»
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Построение regexp'a по входным строкам S1..SN