хочу обогнать Microsoft Indexing Service!
Есть такая маза, если ты смог сделать алгоритм именно О(n поменяй местами текст и ключевые слова, ага. Тогда у тебя получится алгоритм O(1) 
если не хочешь изобретать велосипед, заюзай в своей проге Lucene 
Хеш-функции, индексы тебе не знакомы?
Думаешь, что там просто в лоб такие дела делаются (даже твой подход в лоб).
Для начала ботай книгу для ослов (Алгоритмы: построение и анализ потом читай стандартный
алгоритм поиска в поисковиках (базовым его можно назвать)
Думаешь, что там просто в лоб такие дела делаются (даже твой подход в лоб).
Для начала ботай книгу для ослов (Алгоритмы: построение и анализ потом читай стандартный
алгоритм поиска в поисковиках (базовым его можно назвать)
Для начала ботай книгу для ослов (Алгоритмы: построение и анализ)По-моему, эта книжка не создана для того чтобы её читать. В лучшем случае её можно использовать для самообороны.
а что тебя в этом смущает? алгоритмы О(n) бывают.
отвечаю на твой вопрос: менять местами невыгодно - слишком большая начальная задержка (n>>>k).
+если быть до конца честным, мой имеет сложность O(n*log чем я пренебрегаю.
отвечаю на твой вопрос: менять местами невыгодно - слишком большая начальная задержка (n>>>k).
+если быть до конца честным, мой имеет сложность O(n*log чем я пренебрегаю.
а что это?
быстро ли оно работает?
быстро ли оно работает?
а нельзя ли по подробнее.. это может интересно.. а как здесь можно приделать хеш-функции?
Я читал и живой вроде 
п.с. книгу для ослов проботал, все что хорошего нашел - это кнута и ко.
Насчет стандартных алгоритмов поисковиков было бы интересно почитать. Буду очень благодарен, если скажешь где это есть.
Насчет стандартных алгоритмов поисковиков было бы интересно почитать. Буду очень благодарен, если скажешь где это есть.
потому видимо и живой, что читал, если верить автору этого поста
да, нее, зря ты как;) намальная книжка (если ее не слишком часто открывать 
)
)> если быть до конца честным, мой имеет сложность O(n*log чем я пренебрегаю.
а чего ржать-то?
не вижу ничего такого чтобы не пренебречь операцией, на которую тратиться в среднем на много порядков меньше (уж точно меньше 10^-5) времени работы.
не вижу ничего такого чтобы не пренебречь операцией, на которую тратиться в среднем на много порядков меньше (уж точно меньше 10^-5) времени работы.
а кажется понял в чем причина
я очепятался - там O(n+log.
если быть точным, то там что-то типа Log(k*k я точно не помню, в любом случае к*к <<< n
я очепятался - там O(n+log.
если быть точным, то там что-то типа Log(k*k я точно не помню, в любом случае к*к <<< n
индексы тебе не знакомы?а кажется я понял, ты предлагаешь искать не в тексте, а в индексе, что ли?
способ хороший, но здесь он по понятным причинам не подходит
Стандартные эффективные методы поиска подстрок в тексте ты уже смотрел?
Ты в курсе, что можно не сравнивать каждый символ? А, например, сравнивать только каждый второй?
Ты в курсе, что можно не сравнивать каждый символ? А, например, сравнивать только каждый второй?
Интересно - по каким понятным причинам ? Вообще то индексы тоже не глупые люди придумали - не вижу никаких причин для того чтобы отказаться от индексов в твоем случае...
? Вообще то индексы тоже не глупые люди придумали - не вижу никаких причин для того чтобы отказаться от индексов в твоем случае...много текстов на русском языке, (можно считать, что это массив строк) (n шт)Немного спама.
небольшой набор ключевых слов. (k шт)
задача:
выбрать среди текстов те, где есть ключевые слова.
вопрос:
как это быстро сделать?
Надо скачать и настроить Яндекс-Сервер, благо для "мелкого" использования он бесплатный. 
Спасибо за внимание. Индексы нужны, если много раз искать одно и тоже.
В данном задаче, насколько я понимаю, искать надо только один раз.
В данном задаче, насколько я понимаю, искать надо только один раз.
да, ДаркГрей правильно сказал - документы приходят "голые", без всякого индекса и их нужно один раз отобрать и остальное выкинуть.
Стандартные эффективные методы поиска подстрок в тексте ты уже смотрел?ээ.. не совсем понял как это..
Ты в курсе, что можно не сравнивать каждый символ? А, например, сравнивать только каждый второй?
но неважно, ты насколько я понял говоришь примерную идею алгоритма, да? А где можно прочитать про эти алгоритмы?
Все что я нашел в книжке с ослами - это про построение автомата, с которым бегать по строке и уже упомянутого К-М-Пратта.. (
а насчет индексов это тоже интересно!
я бы с удовольствием почитал как он строится в поисковых системах и из чего состоит, может кто-нибудь знает где про это можно прочитать?
я бы с удовольствием почитал как он строится в поисковых системах и из чего состоит, может кто-нибудь знает где про это можно прочитать?
> А где можно прочитать про эти алгоритмы?
Все в той же книжке с ослами.
Это алгоритм - Бойера-Мура.
Все в той же книжке с ослами.
Это алгоритм - Бойера-Мура.
Log(k*k)ну теперь и я поржу
Посмотри еще http://www.ozon.ru/context/detail/id/1393109/
вот конторка еще этим занимается
http://www.rco.ru/
http://www.rco.ru/
Оставить комментарий
migel
дано:много текстов на русском языке, (можно считать, что это массив строк) (n шт)
небольшой набор ключевых слов. (k шт)
задача:
выбрать среди текстов те, где есть ключевые слова.
вопрос:
как это быстро сделать?
вариант решения:
чтобы получить O(n а не О(nk я немного исхитрился, сделал по набору ключевых слов некоторое дерево из букв и с ним цикл бегает по документу по всем документам. - т.е. линейно все подряд. И ВСЕ РАВНО ПОЧЕМУ-ТО ПОЛУЧАЕТСЯ МЕДЛЕННО! сабж обгоняет мою прогу в несколько раз! КАК У НЕГО ЭТО ПОЛУЧАЕТСЯ? Неужели здесь могут быть какие-то алгоритмические примочки?
(ведь у нас здесь случай русского текста и поэтому всяких там алгоритмов Кнута-Морриса-Пратта не нужно, да и к тому же мой имеет ту же сложность)
Или может медленно работающие команды использую, тогда скажите, ПЛИЗ, как правильно такой цикл писать?