14 Dec 13:42 avatar

Поиск в Internet: новые методики

Источник: www.itc.kiev.ua

Количество информации, размещенной в Internet, растет с каждым днем, однако уровень ее структуризации низок, а частота обновления весьма высока. Уже в 1998 г., согласно исследованию Ли Джилса (Lee Giles) и Стива Лоуренса (Steve Lawrence) из NEC Research, Всемирная Паутина насчитывала более 320 миллионов страниц, в то время как индексные базы наиболее мощных поисковых узлов содержат сведения только о приблизительно 140 миллионах документов. Проблема наполнения, стоявшая вчера, трансформировалась в проблему поиска открытых и бесплатных, но погребенных в недрах колоссальной, запутанной гипертекстовой среды источников. Традиционные поисковые механизмы не справляются с задачей индексирования и даже не в состоянии представить имеющиеся данные в упорядоченном виде. В прошлом году появилось несколько новых поисковых средств, использующих различные методики для повышения релевантности выдаваемых результатов. К сожалению, возникают опасения относительно их жизнеспособности, ведь они находятся в прямом противоречии с потребностями традиционных провайдеров баннерной рекламы. Впрочем, каждый из описанных в данной статье сайтов пытается по-своему решить эту проблему.

DirectHit
Вспомните, как часто вам приходилось задавать вопросы «Где это находится?» или «Как пройти туда-то?» друзьям, коллегам по работе и просто первому встречному на незнакомой улице. Формулировать их нас заставляет желание использовать опыт и знания других людей, и это естественно. Поиск информации в Internet напоминает движение по неосвещенной дорожке толпы людей, которые по очереди упорно наступают на один и тот же садовый инструмент. Увы, идущий впереди никак не может предупредить следующего за ним. Мы прилежно изучаем стандартный набор бесполезных ссылок, полученных на типичный запрос, и после сотни-другой издаем восторженное: «Эврика!». Вы довольны, хотя повода нет. DirectHit частично решает эту проблему, предоставляя своим посетителям возможность воспользоваться бесценным опытом предшественников. Служба анализирует поведение миллионов людей, ежедневно обращающихся к различным поисковым узлам, и для каждого запроса фиксирует наиболее часто используемые ссылки. Учитывается также количество времени, проведенное человеком за изучением содержимого Web-страниц, скрывающихся за ссылками. Чем оно больше, тем выше становится значение релевантности ресурса. Функция Related Searches отслеживает корреляции и связи между различными запросами, так что, сформулировав запрос, посетитель получает набор связанных тем, которые он тоже может просмотреть, расширив ареал поиска.

Кроме этого, DirectHit разработала еще одно интересное нововведение: Personalized Search. Этот вариант сервиса учитывает различия в ментальности разных социальных групп. Пользователь, подписавшись на услуги Personalized Search, сначала заполняет анкету, в которой указывает свой пол, место проживания, род занятий и прочие сведения. Теперь система сможет предложить ему ссылки, заинтересовавшие других людей с похожими анкетными данными. Например, для европейца слово «motorsport» ассоциируется с чемпионатом Formula-1, а для жителя США — с серией CART и соревнованиями NASCAR.

Индексная база службы пополняется с помощью робота под названием Grabber. При обновлении применяется избирательная стратегия, согласно которой сайты, получившие наибольшее количество переходов с результатов поиска, просматриваются чаще (раз в неделю), чем все остальные ресурсы (полное обновление раз в месяц). Производительность аппаратного кластера, поддерживающего функционирование робота, позволяет индексировать до 10 миллионов сайтов в день.

DirectHit не пытается «раскрутиться» как самостоятельная служба, а понемногу продвигает свои услуги через различных партнеров. Необходимо отметить, что к сегодняшнему дню их собралось внушительное количество. AT&T WorldNet, Microsoft, Lycos, HotBot, Apple Computer, ICQ, AOL и многие, многие другие известные компании используют ее возможности в своих поисковых средствах. Дошло до того, что в феврале этого года DirectHit была приобретена корпорацией AskJeeves и теперь применяется в одноименной системе обработки запросов на естественном языке.

Но не поиском единым живет компания. Два других начинания службы DirectHit связаны с электронной коммерцией. Одно из них — система Direct Hit Text Sponsorship — является своеобразным аукционом для рекламодателей. Суть заключается в небольших текстовых сообщениях, которые можно размещать на страницах с результатами поиска по запросам на определенную тему. Другое нововведение — Direct Hit Shopping Network — к сожалению, пока еще чуждо отечественному Web-серферу. Служба занимается сбором информации о товарах на торговых сайтах.

Google
Начало этой поисковой службе с непонятным названием положили студенты Стэндфордского университета: бывший москвич Сергей Брин (Sergey Brin) и Ларри Пэйдж (Larry Page). Слово «Google» является производным от «термина» googol, придуманного племянником известного американского математика Эдварда Каснера (Edward Kasner), и означает число, записываемое как единица со ста нулями. Академичность происхождения определила академичность подхода. Компаньоны взяли на вооружение общеизвестную систему «оценки ценности» статей, принятую в мировом научном сообществе. Рейтинг статьи есть производная от количества сделанных цитат и ссылок на нее в других научных публикациях. Google высчитывает релевантность документа, попавшего в результаты поиска, в соответствии с количеством ссылающихся на него других Web-страниц. «Старинные» бумажные принципы оказались действенными и в Internet. Но Сергей и Ларри пошли дальше, создав продуманную и оригинальную методику.

Цитируемость документа выводится Google с использованием системы PageRank. Значение PageRank любого документа учитывает количество ссылок на него во всех прочих проиндексированных источниках и вычисляется по формуле:

PR(A) = (1-d) + d (PR(T1)/C(T1) +… + PR(Tn)/C(Tn)),

где A — оцениваемый документ, PR(X) — рейтинг документа X, C(X) — общее количество ссылок со страницы X, T1…Tn — документы, ссылающиеся на A, а d — некий фактор случайности, описывающий поведение посетителей. Итак, PR(A) представляет собой вероятность попадания хаотически путешествующего по Web серфера на страницу A. Величина d, которую изобретатели установили равной 0,85, характеризует вероятность того, что, находясь на странице, участвующей в оценочной формуле, серфер вдруг заскучает и решит взбодриться, перескочив на произвольную страницу в Internet, путем набора URL прямо в соответствующем поле броузера. Как видно из формулы, «рекомендация» от страницы, имеющей высокую «репутацию», обладает большим весом, что позволяет правильно оценивать значимость непопулярных, но качественных сайтов. В эту схему хорошо укладываются запросы, состоящие из одного слова, а в случае нескольких заданных терминов приходится учитывать и другие факторы. Например, оценка близости искомых слов в документе выбирается из десяти дискретных значений, начиная от совпадения фразы и заканчивая «очень далеко». Порядок слов в запросе не играет роли для Google. Система также активно использует индексирование по ссылкам.

Сбором данных в системе занимаются несколько независимых роботов, получающих задание от URL-сервера, коллекционирующего ссылки. Найденные документы архивируются и помещаются в репозиторий, далее формируется три индекса страниц: по словам, документам и ссылкам.

Для пользователя титульная страница Google весьма похожа на варианты text-only других поисковых серверов. В центре — поле ввода запроса и две кнопки. Первая — Google Search — приведет вас к странице, забитой информацией о десятке найденных документов, а вторая — «I’m Feeling Lucky» — сразу отправит ваш броузер по наиболее релевантному, по мнению системы, URL. Чуть ниже примостилась скромная ссылка (browse web pages) на недавно организованный Internet-каталог. Составляя запрос, следует помнить, что Google:
а) автоматически вставляет между всеми словами запроса оператор AND и не поддерживает оператор OR, а также возвращает только те страницы, которые содержат абсолютно все термины запроса;
б) позволяет исключить слова-«паразиты» с помощью символа "-" и не работает с шаблонами (?, * и т. д.);
в) рассматривает слова, заключенные в двойные парные кавычки, как указание искать только полные совпадения фраз и автоматически удаляет отдельно стоящие цифры и буквы, слова com, http и тому подобные «бессмысленные» термины, но сделает исключение для вас, если обнаружит значок "+" перед ними;
г) предлагает особый вид услуг — выдачу всех ссылок на заданную страницу.

На первой же странице результатов поиска Google можно получить сведения об общем количестве найденных документов и времени, затраченном на обработку запроса. Далее идут собственно ссылки на них, сгруппированные по сайтам. Для каждого из них система пытается найти соответствие в базе данных настоящих имен и торговых марок RealNames. Если это не удается, то отображает заголовок страницы по содержимому мета-тега TITLE, а в случае отсутствия такового или если страница пока занесена в базу только по ссылке, показывает ее URL. Чуть ниже располагается ее краткая аннотация. Ссылка, озаглавленная «Cached», выведет уже упомянутую копию текста страницы, записанную в архиве службы, а функция GoogleScout поможет отыскать все похожие документы (аналогично многим российским поисковым машинам).

Компания Google не ограничилась только поисковым сервисом и занимается созданием собственного Internet-каталога под названием GoogleDirectory. И в этом случае Брин и Пэйдж пытаются воспользоваться чужим опытом — данные для каталога поставляет организация добровольцев Open Directory Project, работающая под эгидой Netscape. Ее члены уже долгое время коллекционируют интересные ресурсы Всемирной Сети. На сегодняшний день GoogleDirectory насчитывает описания более полутора миллионов специально отобранных узлов. Технология PageRank позволила придать старой идее новые качества — сайты каждой категории отсортированы соответственно своему рейтингу цитируемости. Информация, почерпнутая из каталога, всегда дополняет результаты традиционного поиска в Web, так что дважды искать вам не придется.

Бизнес службы зиждется на двух китах: услугах WebSearch и тематической рекламе. Подписавшись на WebSearch, владелец сайта получает в свое распоряжение аппаратные и программные ресурсы компании, что позволяет ему избавиться от дополнительных расходов и беспокойства по поводу надежности функционирования системы. Страницу результатов можно модифицировать так, чтобы добиться единообразного оформления со своим узлом. Различные варианты партнерства, Free, Silver и Gold, соответствуют уровню разрешенной адаптации. Если за Free не надо платить ни цента, то последние два потребуют платы в размере 600 и 2000 долларов. Того, кто не желает платить, но не прочь заработать, приглашают стать Google’s Affiliate, разместить форму поиска на своем сайте и получать по 3 цента за каждый запрос. Впрочем, и без них служба обзавелась влиятельными клиентами: Netscape, WashingtonPost.com, RedHat и Virgin Net. Что касается тематической рекламы, то, подобно Яndex, Google коллекционирует запросы пользователей, а затем сортирует их по категориям, пополняя свой так называемый Virtual Directory. Рекламодатель, желающий разместить на сайте собственную информацию, выбирает категорию, наиболее соответствующую тематике его бизнеса. Система автоматически классифицирует каждый новый запрос на основании его схожести с образцами, собранными в Virtual Directory, и выбирает подходящие рекламные объявления.

CLEVER
Client-Side Eigenvector Enhanced Retrieval — столь замысловато расшифровывается емкая аббревиатура-название поискового механизма, разрабатываемого в недрах исследовательского центра Almaden корпорации IBM. Родоначальником этой технологии является Джон Клейнберг (Jon Kleinberg) — профессор из Корнелла, автор алгоритма Hypertext-Induced Topic Search (HITS). CLEVER, как и Google, в своей работе основывается на ссылках и рейтингах, но подходит к задаче совсем по-другому. Если детище воспитанников Стэнфордского университета сначала вычисляет коэффициенты PageRank для всех индексированных документов, а потом просто учитывает их при сортировке результатов, то поисковая система IBM оценивает страницы на ходу. Сначала выполняется обыкновенный поиск по терминам заданного запроса. Отобранные страницы просматриваются, по ссылкам выделяется новая порция документов. Их тоже просматривают на предмет связей. И так далее — итерация за итерацией. Согласно последним исследованиям центра, 96% документов, связанных по ссылкам, имеют сходную тематику. После того как определенная часть структуры выявлена, CLEVER высчитывает рейтинг для каждой из найденных страниц на основании количества ссылающихся на нее «собратьев». Система различает два типа сайтов: «первоисточники» (authorities) и «хабы» (hubs). Ценность первых — контент, вторых — ссылки на многочисленные «первоисточники». По мнению Клейнберга, сайты-хабы часто оказываются более полезными, чем непосредственно поставщики контента, поскольку зачастую предлагают более широкий взгляд на тему поиска. Действительно, сегодня пользователь находится в тисках своего собственного запроса: обобщенные термины дают слишком много результатов, а узкоспециализированные — слишком мало. В отличие от Google, ориентированной именно на узлы «первоисточники», CLEVER отдает должное «хабам». Благодаря разветвлению поиска «вширь» удается выявлять тематические сообщества сайтов, число которых, по оценке Рагавана, одного из разработчиков метода, достигает 100 тыс. Тут просматриваются интересные аналогии с Internet-каталогами, редактируемыми людьми. Ни один из них не может справиться с экспоненциальным ростом Web, и даже «монстр» Yahoo! индексирует всего около 1 миллиона страниц. Таким образом, CLEVER сочетает преимущества традиционных поисковых машин и каталогов. Плюсы технологии очевидны, но тут не обойтись без «ложки дегтя». Ранжирование и итеративный процесс подбора выполняются для каждого запроса в отдельности, поэтому по эффективности «умник» вряд ли сможет когда-либо тягаться с Google или традиционным поисковым механизмом. Кроме того, работа системы пока слишком сильно зависит от характера данных и особенностей конкретной тематики. Так что IBM не торопится и проводит консультации с отдельными компаниями о возможном коммерческом применении CLEVER.

Yep.com
«Первый поисковый сервис, основанный на ранжировании сайтов по качеству и популярности» — так характеризуют свое детище сами его создатели. Yep.com представляет собой нечто среднее между службой немедленных сообщений (instant messaging) и настоящим поисковым узлом. Оценки качества содержания того или иного сайта проводятся на основе анализа предпочтений аудитории пользователей программы Yep Web Companion. Она позволяет оставлять на Web-страницах персональные записки, видимые только автору, общаться в чатах, организовывать коллективные Web-туры и давать оценку содержимому посещаемого сайта. Собранные голоса ложатся в основу рейтинга качества, а информация о перемещениях пользователей программы в Internet — рейтинга популярности. Последний пополняется также за счет службы HitBox, которая, как и Yep.com, принадлежит компании WebSideStory. HitBox — некий аналог Топ-100 Рамблера, за исключением того, что сайты-участники публично не соревнуются между собой. Во всяком случае, эта информация не афишируется. Поместив код счетчика на своей странице, Web-мастер получает в руки мощный статистический инструмент, позволяющий отслеживать посещаемость, скорость загрузки страницы, частоту создания закладок посетителями и т. д. Эта информация используется и для определения рейтингов качества и популярности. Как видите, все достаточно просто. Вводя запрос, можно выбрать наиболее важную для вас характеристику: 100% качества, 100% популярности или «золотая середина».

В начале пути…
В обзоре упомянуты только четыре службы, взявшие на вооружение наиболее любопытные технологии. На самом деле наука о поиске в сложных, динамически изменяющихся гипертекстовых средах находится в начальной стадии своего развития. После появления первых публикаций о поисковых механизмах (http://www.cs.colorado.edu/home/mcbryan/mypapers/www94.ps) наступило некое затишье в академических исследованиях, так как основная часть работ сместилась в область коммерческих разработок. Увы, их создатели не имеют ни желания, ни юридической возможности раскрывать секреты своей деятельности. В результате процесс «перекрестного опыления идеями», важность которого для науки трудно переоценить, был сведен на нет. Возможно, появление Google и CLEVER предвещает новый виток развития технологий поиска.

0 комментариев

Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.