Господа, STLая сортировка очень даже неплоха. Вряд ли кто-нибудь напишет версию, которая будет работать быстрее чем на 10-20%. Опять-таки, говоря про STL неплохо было бы называть версию и конкретную реализацию STL. Так, например, в некоторых версиях (старых) GNU Stl для GCC 2.95 sort "подвисал" на больших объемах. Зато stable_sort работал нормально. Возвращаясь к вопросу стабильной сортировки, а разве stable_sort не стандартизированная фича?
И еще, кстати, мне почему-то кажется, что в современной поисковой машине скорость сортировки в памяти (в смысле 20-30% вариаций) не играет почти никакую роль. Потому, как если происходит слияние временных индексов, то там как минимум 90% времени сжирается работой с диском. А если происходит поиск, то он работает, как правило, с отсортированными или частично отсортированными списками записей.
за такое время на такой железке, с такой памятью стандартные инвертированный файл не справится, или справится едва-едва.
к тому же, имхо, здесь важно не сколько там есть звездочек, а какая длина подстрок без wildcard. сами, посудите какова фильтруаящая способность, скажем, триграммы относительно массива слов длинной 128 символов количеством 13 млн. я думаю, что будет очень хорошо, если на такой железке вам удастся уложить поиск в несколько секунд.
в общем, еще раз хотел подчеркнуть, что не видел в жизни (и литературе) ничего сколько-нибудь адекватного для общего решения. ведь, например, суффиксные деревья, над оптимизаци которых бьется весь цивилизованный мир уже много лет, особо не помогут в случае образца а.*е. потому как кат-офф кондишен не будет срабатывать. слов, начинающихся на а - миллионы и почти все они содержат в себе букву е! так что же вернуть юзеру миллион результатов? надо их как-то отранжировать, если много найдено. это другая сложность. вот и получается, что задача в любом случае поставлена некорректно.
.......................
1. Смотря что считать быстро.
2. Какой размер оперативной памяти.
3. Какие требования к wildcard, типичные, итд. Знаете ли, ни один алгоритм
по wildcard а.*б.*в.*г.*...я где все буквы русского алфавита и 33 звездочек быстро искать не будут.
4. Ну и потом, посчитайте, что если на реализацию такого алгоритма затратить 2 недели, неделю-другую на отладку довдоку (а может даже больше) Ваша цена в 500 баксов выглядит совсем смешной.
5. подумал, дописал, кстати, если это какое-то критичное приложение, то можно написать распределенную искалку.
.
Кстати, согласен с товарищем Тихоновым на все 100, что проблема
а) заключается в сущности используемых стат. методов
б) в недостаточности современных вычислительных ресурсов для отказа
от "статистики"
хочу сказать, что даже такая "тривиальная" операция, как составление смысловой "выжимки" документа, ее автореферата замедлит индексацию в разы. а смысловая "выжимка", кстати говоря, могла бы несколько улучшить качество поиска по коротким запросам и существенно усложнить жизнь спаммерам. одно дело: ломать статистику (с более или менее известными алгоритмами), другое дело программу реферирования (которая гораздо сложнее).
Вот в этом-то и вся фишка, что абсолютное большинство, но
не все. А то, что изменчивые странички нужно переиндексировать
чаще, чтобы извелечь из них нужные ссылки (на постоянные адреса
новостных статей например) это уже дело десятое.
Важно то, что если мы это не будем делать, то качество информации
(на интуитивном уровне) будет сильно ниже. А как перейти
от понятия интуитивному к формальному? Например, приписать большой
вес таким страничкам. Кто сказал, что большие веса будут
у многих страничек? Они будут только у 0.001 всех страничек
если не меньше, но модель, предложенная в статье
это никак не учитывает.
Нет, ну мне нравится пример из статьи с двумя страницами,
одна из которых меняется 10 раз в день, а другая 1.
Если есть возможность обновлять ровно страницу в день, то
оптимум достигается, если переиндексировать только одну
страницу (которая меняется раз в день), а другую не трогать!!!
ну, а если часто меняющаяся пага содержит анонсы сайта,
на который ходит миллион посетителей в день, а другую
посещают раз в полгода?
И кому такая стратегия обновления нужна,
даже если средняя "свежесть" базы, высчитываемая, как среднее
количество актуальных страниц (усредненное по времени) максимальна? :-))
Уважамый Александр, я так заинтересовался ссылочкой, что не
поленился прочитать статью. На первый взгляд парадокс, почти
Уайльдовский. На второй всё становится ясно.
За меру свежести берётся просто среднее количество up-to-date
страниц. Да, относительно этой меры бессмысленно переиндексировать
часто меняющиеся страницы "часто". Другое дело в том, что
мера свежести должна быть "взвешенной" и приписывать многим
часто меняющимся страницам (напр. нюьюсам, форумам) существенно
большие веса!!! Вот тогда и получится, что ньюсовые-хитовые страницы надо обновлять часто, потому что в реальном инете частота изменения
страницы и ее популярность неплохо так коррелируют.
С Уважением,
Itman.
Читать-то я читал, только фраза "лексика" ссылок, требует уточнения. Если имеется в виду повышение релевантности при поиске по словам, которые берутся из ссылок с сайтов с высоким индексом цитирования (типа как о тебе говорят другие), то эта характеристика, при всем моем к ней уважении, как и индекс цитирования должны быть вспомогательными, а не основными.
Вот, к примеру, я решил снова проверить яндекс по запросу яндекс гуру и яндекс почта. Со страницой яндекс-гуру все в порядке - там в тайтле яндекс набран по-человечески. А вот с запросом яндекс почта полный облом. Уверен, что через некоторое время, когда техническая поддержка зачтет этот форум, она поправит и этот запрос :-)
А гугл по этим двум запросам: яндекс почта и яндекс энциклопедия очень точно приводит на главную страницу, потому что
а) теги <img alt ...> отрабатывает
б) учитывает какие ключевые слова юзаются между <a href ..> и </a> при ссылках на страницу с другого сайта. Это один вид так называемых fancy линков.
Ну вот, хоть убейте, не верю я, чтобы регулярно как я заходил на яндекс в час ночи, чтоб там серверы лежали.
Еще один аргумент: яндекс новости. В яндексе ссылка выходит второй и кричит о себе, что она по ссылке найдена. В гугле она первая.
И вообще это письмо не камень в огород яндекса! Я-то, как практически разработчик поисковых систем, понимаю, что принципиальное улучшение качества поиска дает прежде всего грамотно сделанная страничка! А вот веб-мастер яндексовых страниц в смысле поисковых систем не шибко грамотно сработал :-)
Таково мое скромное мнение.
Не исключено, но только пага с энциклопедиями так сделана, что она в принципе не должна лезть на первое место! Там же одно слова яндекс в конце и оно далеко от слова энциклопедия! А она теперь лезет. есть подозрение, что ее ручками "довкрутили". хотя я и не исключаю, разумеется, честного исправления вроде прописывания пары синонимов: Яндекс = Яndex
