Спайдеры

Спайдер (spider) — это программа, используемая для получения некоторых или всех ресурсов с большого числа Web-сайтов. На первых порах спайдеры [Fic94] использовались в качестве вспомогательного средства при обслуживании Web-сай- тов. В настоящее время спайдеры в основном используются для сбора информации в интересах поисковых систем. До сих пор мы обсуждали роль Web-браузеров — наиболее распространенного типа Web-клиентов. Поиск информации в Web также остается одним из популярных приложений, что и явилось причиной для создания таких инструментов, как спайдеры. Далее мы подробно рассмотрим клиенты-спай- деры и поговорим об их использовании в поисковых системах.

В главе 1 мы говорили о роли, которую играли предшествующие Web-системы в оказании помощи пользователям при поиске интересующих их документов в Internet. Эти системы имели каталоги, служившие в качестве предметпых указателей для наборов документов. Gopher и WAIS имели дополнительные возможности для индексирования документов, хотя при этом каждый сайт должен был регистрировать свое содержимое на центральных серверах.

Поиск в Web

Системы, связанные с Web, такие как Gopher, были также ориептироваиы на поиск информации. Централизованный характер Gopher с его требованиями глобальной регистрации создали условия для всеобъемлющего поиска, однако необходимость обслуживания центрального реестра стало серьезной помехой в достижении успеха. С самого пачала поиск активно использовался приложениями в Web. При быстром увеличении числа Web-сайтов, пользователей и Web-страниц, отсутствовала расширяемая технология, позволяющая отдельным пользователям или владельцам сайтов ориентироваться в быстро растущем наборе доступных документов. Децентрализованная суть Web сделала поиск сайтов и страниц необходимостью. Если пользователь ищет вхождения строки в небольшом файле, можно выполнить поиск по запросу. Выполнение же поиска в наборе из нескольких гысяч файлов потребует времени. Если же следует просмотреть десятки тысяч файлов, размещенных на тысячах компьютеров, задержка для пользователя будет еще больше. Наконец, если сотни тысяч пользователей ищут текстовые строки в десятках миллионов документов, размещенных на миллионах компьютеров, проблема становится значительно более сложной. Именно эту проблему призваны решать поисковые системы.

Один из способов существенно ускорить поиск — это иметь упорядоченный набор указателей вхождений искомых строк на их позиции в документах. Такой набор указателей называется инвертированным индексом. Например, предметный указатель в конце этой книги является подмножеством инвертированного индекса; он отсылает обратно к страницам, где встречаются указанные термины. Авторы могут принять решение не использовать все слова, которые встречаются в книге, в предметном указателе. Предметный указатель при этом получился бы слишком большим и не слишком полезным. Предметный указатель в книге указывает только на основные вхождения проиндексированных слов, в то время как инвертированный индекс обычно содержит все вхождения каждого из индексированных терминов. Слова, которые исключены из процесса индексирования, называются сорными словами (stop words). В качестве примеров можно привести часто встречающиеся слова, такие как «the» и «end».

Первоначально, когда коллекция документов на удаленных сайтах была небольшой, имело смысл создавать локальные инвертированные индексы на каждом из удаленных сайтов. Однако с резким расширением Web создание локальных инвертированных индексов стало нецелесообразным. Лучшим выходом стало иметь несколько централизованных предметпых указателей, которые могли бы использоваться миллионами пользователей. Для осуществления масштабного поиска необходимы два компонента: спайдеры и поисковые системы. В этом разделе мы познакомимся со снайдерами и увидим, как они используется совместно с поисковыми системами. .

Клиент-спайдер

Спайдер — это ключевой инструмент для поиска в Web. Как уиомипалось ранее, спайдер представляет собой программу, которая получает некоторые или все ресурсы с большого числа сайтов, главным образом с целью создания инвертированных индексов, которые позднее будут использоваться поисковыми приложениями. Подобно другим Web-клиенгам, спайдер формирует HTTP-запросы для доступа к ресурсам Web-сайта и осуществляет синтаксический анализ ответов. Главными различиями между спайдером и браузером являются гораздо большее число сайтов, к которым осуществляется обращение и посылаются запросы, отсутствие какого-либо отображения ответов и достаточно необычное использование ответов.

На практике, однако, с сайтов может запрашиваться только часть ресурсов. Многие спайдеры, например, не запрашивают изображепия или мультимедийные ресурсы. Это делается, если спайдер используется для построения индекса только текстовых ресурсов.

Допустим, сайт www.kandrse.com желает предоставить пойсковый сервис, сходный с тем, который предоставляют популярные системы Excite и AltaVista. Сайт www.kandrse.com использует спайдер для загрузки страниц, подлежащих индексированию. Спайдер обычно начинается с базового списка популярных сайтов — известного как начальный список (start-list), за которым следуют все URL, которые будут найдены в составе сайтов начального списка. В качестве примера начального списка можно привести перечень категорий, присутствующий на популярных сайтах, таких как Yahoo. Построение иачалыюго списка популярных сайтов и распределение задач представляют собой наиболее интересную техническую задачу при создании спайдеров.

Спайдер загружает начальную страницу сайта (например, http://www.cnn.com/) и просматривает все встроенные в нее гиперссылки. Для каждой гиперссылки оп может загрузить соответствующую страиицу, — это называется обходом сначала в ширину (breadth-wise). Осуществляется переход по каждой гипертекстовой ссылке в составе сайта (т.е. гиперссылкам, имеющим суффикс cnn.com/, например, http://www.cnn.com/nebraska.html или http://www.cnn.com/weatherpage.html), а затем переходы по гинерссылкам на нолученпой странице и т.д. Есть и другой способ: спайдер может отобрать первую встроенную гинерссылку и, предполагая, что гиперссылка обращается также к HTML-докумеиту, осуществить сиигаксиче- ский анализ документа и перейти по первой встроенной гиперссылке (если она имеется). Подобный подход называется обходом сначала в глубину (depth-wise). Здесь следует позаботиться о недопущении замкнутых циклов в результате перехода по гиперссылке, которая ранее уже была обработана. Множество страниц может иметь встроенные ссылки на одну и ту же страницу, либо страница в глубине иерархии сайта может иметь ссылку на страницу верхнего уровня. Например, страница http://www.cnn.com/foreign/Iatvia/riga/opera/2000/schedule.html может иметь ссылку на http://www.cnn.com. Спайдер может также использовать другие алгоритмы для пропуска нежелательных страниц или сайтов; например, содержимое сайта может быть признано неподобающим. Миогие спайдеры также принимают решение осуществлять индексирование лишь до определенного уровня глубины сайта. В результате сочетания обходов в ширипу и в глубипу могут быть собраны все ресурсы сайта. Время последнего посещения сайта записывается и используется при принятии решения о повторном его индексировании.

Спайдер может попытаться загрузить все ресурсы сайта за один раз, либо, что является более правильным, разбить эту задачу на отдельные части и выполнять ее в течепие некоторого периода времени. В прогивиом случае исходный сервер сайта может оказаться слишком загруженным при получении запросов от снайдера и не сможет обслуживать запросы от обычных пользователей. Большинство используемых в Web спайдеров не возвращаются к одному и тому же сайту чаще одного или двух раз в минуту. могут не загружать определенные в ресурсы в поисковую систему www.kandrse.com. Например, если сайт поисковой системы намеревается построить инвертированный иидекс только текстовых ресурсов, загружать изображения пет надобности.

После того как сайт был проиндексирован, спайдер должен периодически повторно посещать сайт, поскольку содержимое последнего может изменяться. Однако содержимое одних сайтов может меняться не столь часто, как содержимое других сайтов. Спайдер должен обладать достаточным интеллектом, чтобы переиндексировать сайты в соответствии со скоростью изменения информации на них. Это позволяет сократить объем работы и избежать излишних обращений к сайту. Кроме того, некоторые составные части сайта могут меняться чаще, чем другие. Спайдер должен, таким образом, учитывать структуру информации на сайте и просматривать регулярно меняющиеся части более часто.

В то время как статические ресурсы могут быть достаточно легко проанализированы спайдером, динамические ресурсы обычно не индексируются. Ряд ресурсов сайта может динамически создаваться с помощью CGI-сцепариев (см. главу 4, раздел 4.2.3). Сценарии часто используют параметры, а спайдер «пе знает», какие значения параметров следует использовать при вызове. Основным назначением индексирования сайтов является возможность возвращать егшеок гиперссылок на страницы в ответ на запрос. Таким образом, даже если бы это было возможно, в индексировании динамических ресурсов нет особого смысла. Если спайдер «замечает», что сайт состоит главным образом из динамических ресурсов, он может не индексировать статические страниц сайта, а также динамически генерируемые ресурсы, которые не изменяются в зависимости от параметров запросов. Иногда на сайте имеются ресурсы, которые педостижимы через ссылки извпе. не знают о существовании таких ресурсов и не индексируют их.

Сайт может оказаться не в состоянии противодействовать индексированию себя снайдером. Хотя многим сайтам индексирование выгодно (многие создатели Web- страниц хотели бы, чтобы их страницы увидело как можно больше людей), некоторые сайты предпочитают, чтобы их «ие беспокоили». Для разрешения этой проблемы существует ряд соглашений. Нет простого способа сделать так, чтобы ресурс был доступеп любым клиентам кроме спайдеров, поскольку вряд ли можно различать клиентов, посещающих сайт. Каждый запрос, поступающий от клиента, рассматривается как независимый запрос, и серверам пришлось бы хранить значительный объем информации о состоянии, чтобы отслеживать частоту поступления запросов от определенных клиентов в надежде обнаружить спайдер. Кроме того, подобный мехапнзм может оказаться бесполезным, если спайдеры не посылают все свои запросы с одного IP-адреса, либо меняют частоту передачи запросов конкретному сайту. Даже если исходному серверу известно, что клиентом является спай- дер, обеспечить селективный доступ может оказаться затруднительным, поскольку серверу придется проверять каждый входящий запрос, чтобы выяснить, не поступил ли он от спайдера. Подобное действие может увеличить время ожидания на стороне клиентов.

Существует два соглашения, которым обычно следуют сайты, чтобы каким-то образом контролировать работу индексирующих их снайдеров. должны иметь стимул вести себя надлежащим образом; в противпом случае поисковая система может заслужить плохую репутацию. На уровне сайта это может быть реализовано следующим образом: администратор Web-сайта ведет файл с именем robots.txt. Робот — это одно из названий автоматизированного клиента (такого, как спайдер), а файл robots.txt содержит правила доступа, которым должны следовать роботы. Web-сайты используют этот файл в соответствии со стандартом Robot Exclusion Standard [RES]. Файл содержит список каталогов, которые спайдеры не должны посещать, а также спецификацию агентов пользователя, к которым эти ограничения применяются.

Например, рассмотрим следующий файл robots.txt:

User-agent: * Disallow: /stats Disallow: /cgi-bin/ Disallow: /Excite/

В нем указывается, что всем агентам пользователя разрешается загружать ресурсы с сайта для индексирования. Если в поле User-agent присутствуют одпа или несколько строк (вместо "*"), например:

User-agent: ArachnoPhobia, BlackWidow

то два указанных агента пользователя распознаются как клиенты, которые не могут обращаться к сайгу для индексирования. Web-сервер не осуществляет ка- кой-либо явпой проверки или действий по запрету доступа.

Строки Disallow используются для указания каталогов (/states, /cgi-bin, /Exci- te), которые не должны просматриваться программами-роботами, в том числе спайдерами. Онять-таки, сервер не может реализовать такие ограничения. Стандарт Robot Exclusion Standard [RESJ определяет соглашения, которым должен следовать «добропорядочный» робот. Побудительным мотивом для роботов следовать стандарту является то, что сайтам часто известен набор ресурсов, которые пет смысла индексировать. В приведенном выше примере каталог cgi-bin скорее всего содержит группу ресурсов, которые при вызове с различными значениями параметров с большой вероятностью будут возвращать различные результаты.

Таблица 2.4. Некоторые поисковые систсмы

Поисковая система

Имя агента

Доменное имя спайдера

AltaVista

(обычный спайдер)

Scooter/2.0 G.R.A.B. X2.0 Scooter/1.0 scootcr@pa.dec.com

scooter.pa-x.dec.com scooter*.av.pa-x.dec.com

Euroseek

Arachnoidea

(arachnoidea@euroseek.com)

*.euroscek.net (infra.euroscek.net)

Второй способ сообщить роботам о том, какие ресурсы не следует индексировать — воспользоваться HTML-тегом МЕТА. Например, тег

<META NAME="ROBOTS" CONTENT="NOINDEX, N0F0LL0W">

ипформирует робота, что текущий ресурс не должен индексироваться и не следует осуществлять переходы по гиперссылкам в ресурсе. При синтаксическом анализе HTML-документа спайдеры просматривают значение атрибута CONTENT тега МЕТА с целью выяснения, могут ли они индексировать этот документ или осуществлять переходы по имеющимся в нем гиперссылкам.

В таблице 2.4 представлен список известпых спайдеров [Spi], используемых некоторыми популярными поисковыми системами. В первом столбце указано название поисковой системы, во втором столбце — имя, присвоенное спайдеру, а в третьем столбце — доменное имя компьютера, на котором размещен спайдер. Информация предоставляется в виде идентификационных данных, которые Web-сайт может использовать, для обеспечения не слишком частого доступа спайдера к сайгу. Большинство известных спайдеров следуют стандарту Robot Exclusion Standard. К главным отличиям между спайдерами относятся общее число посещаемых сайтов, общее количество индексируемых ресурсов и частота нереиндексировапия. Ряд современных спайдеров способны осуществлять индексирование миллиардов Web-страииц и делать их доступными для поиска. Сравнение эффективности различных поисковых систем можно найти в [LG99]. Большинство компаний не раскрывают информацию о своих спайдерах, поскольку среди поисковых систем имеется силытая конкуренция. Подробную информацию о расширяемом средстве сканирования Web с описанием его возможностей можно найти в [HN99].

Использование спайдеров в поисковых системах

помогают поисковым системам индексировать страницы Web-сайтов. В зависимости от сложности спайдера, размера пачалыюго списка и достунных спайдеру ресурсов, инвертированный индекс может быть создан для всех или для некоторых страниц. За последние 20 лет были созданы сложные алгоритмы построения предметных указателей для больших наборов документов [WMB99].

Сайты поисковых систем являются, пожалуй, наиболее популярными в Web. Сайты порталов, такие как yahoo.com, excite.com, google.com и altavista.com, являются отправными точками для множества приложений. О порталах подробнее рассказывается в главе 4, раздел 4.1. Практически все порталы имеют пользовательский интерфейс для поиска. Поисковая система предоставляет пользователю возможность для ввода одного или нескольких ключевых слов. Ключевые слова ищутся в инвертированном индексе, после чего возвращаются указатели на содержащие эти слова документы (если таковые имеются). Поиск может быть ограничен одной базой данных (например, содержащей ссылки на Группы новостей или сводки показателей стоимости акций), либо поиск осуществляется по всему индексированному содержимому Web. Многие пользователи тратят значительное время на поиск. Одной из причин этого является отсутствие хорошего едииого предметного указателя для Web. К наиболее популярным сайтам относится Yahoo!, который индексирует сайты, по не содержимое всех страииц. Другими словами, для целей индексирования отбираются только основные страницы сайтов. Поисковые сайты, такие как AltaVista и Google, индексируют отдельные страницы в составе Web- сайтов. Таким образом, сайты, подобные Yahoo!, могуг использоваться для поиска общей информации по теме, не вдаваясь в подробности, тогда как AltaVista и Google более результативны для поиска отдельных документов.

Список возвращенных документов (или указателей на документы) называется результирующим множеством. Поисковые системы различаются но уровню сложности. Большинство поисковых систем предоставляет простые функции поиска, с помощью которых в предметном указателе ищется одно или несколько ключевых слов и возвращаются указатели на документы, в которых найдепо любое вхождение ключевого слова. Наличие нескольких ключевых слов интерпретйруется как требование выполнения логического оператора or (wiu). Поисковая система Google [Goo] предоставляет пользователям простой интерфейс. Искомые термины объединяются с помощью логического оиератора and (и), при этом возвращаются ссылки только на документы, содержащие все ключевые слова. Усовершенствованная версия поисковой системы AltaVista [Alt] и ее вариаит Raging [Rag] имеют более сложный интерфейс: пользователи могут использовать любую комбинацию операторов and (и), or (wiu), not (не) и near (около). Оператор not (не) представляет собой унарное отрицание, и документы, содержащие искомый термин, исключаются из результирующего множества. Оператор near (около) используется для задания расстояния между ключевыми словами в документе Путем сочетаний различных операторов можно получить результирующее множество, соответствующее требованиям пользователя и содержащее умеренное число документов.

Двумя основными показателями поисковых систем, выработанными в результате многолетних исследований, являются полнота (recall) и точность (precision). Полнота оценивает широту охвата искомого множества, т.е. объем результирующего множества как функция от размера списка документов, в которых встречаются искомые ключевые слова. Если объем результирующего множества большой, пользователи могут быть уверены, что Они получили полный ответ. К сожалению, принимая во виимапие неоднозначность естественного языка, большинство «ответов» в результирующем множестве могут не устраивать пользователя.

Предположим, например, что пользователь хочет узнать имя создателя храма Парфенон в Греции. Строка поиска «создатель Парфенона» может вериуть множество страниц, относящихся к издательской компании «Парфенои», к греческим ресторанам под названием «Парфенон», а также к различным архитекторам. Показателем качества ответа является точность — уместность документов в данном результирующем множестве. Часто полнота и точность являются взаимоисключающими: возврат меньшего числа документов может увеличить точность, но полнота при этом уменьшится. Аналогично, более широкое результирующее множество в целом снижает точность. Противоречие между точностыо и полнотой во многом остается неразрешимым, и многие поисковые системы тратят массу усилий, пытаясь повысить релевантность, возвращая, тем не менее, результирующее множество достаточно большого объема. Сложность запросов на естественном языке и отсутствие универсальных методов их обработки приводит к низкому качеству результатов. Подавляющее большинство запросов — на сегодняшний день, около 90% — к популярным поисковым системам, таким как AltaVista или Google, состоят из одного термина.

После выполнения поиска и формирования списка всех документов, в которых присутствуют ключевые слова, а также фильтрации но показателям полноты и точности с целью получения желаемого размера результирующего множества, поисковая система должиа ранжировать результаты. Ранжирование — это определение порядка, в котором будут возвращаться результаты поиска. Если мощность множества результата для искомой строки «создатель Парфепоп» составила 823, многие поисковые системы могут возвратить только первые 200 соответствий. Однако определение первых 200 соответствий требует ранжирования записей в результирующем множестве. Ранжирование по частоте вхождений искомых ключевых слов в документе не обязательно является хорошим показателем. Раижирование на основе частоты вхождений ключевых слов является рисковаииой, поскольку некоторые авторы документов намеренпо заполняют свои документы ключевыми словами, известными как «ловушки запросов». Например, поскольку значительное число запросов направлено на поиск материалов порнографического содержания (эта тема не слишком широко обсуждается в научной литературе), создатели таких Web-сграниц добавляют на свои страницы множество наиболее распространенных ключевых слов. Достаточно легко Можно сделать эти ключевые слова невидимыми при воспроизведении HTML-документа, установив для них нулевой размер шрифта или сделав так, чтобы текст сливался с фоном. Другими словами, эти ключевые слова воспринимаются только программными компонентами поисковых систем, осуществляющими ранжирование. Более интеллектуальные поисковые системы уменьшают значение частоты вхождений терминов при использовании его в качестве параметра для ранжировании. Хотя ранжирование — достаточно известная и очевидная концепция, используемая при поиске ииформации, исследования показали, что большинство пользователей просматривают лишь несколько элементов в результирующем множестве. На деле большинство популярных поисковых систем возвращает по 10 результатов за раз, хотя результирующее множество может содержать тысячи документов. Большинство пользователей обычно не идут дальше второй страницы результирующего миожества; г.е. просматривается максимум 20 записей. Популярная поисковая система Google дает возможность пользователям непосредственно переходить к первому документу в ранжированном списке результатов в обход страницы с результатами поиска.

В последнее время в поисковых системах было реализовано несколько новых идей. Например, поисковые системы, такие как Google и Clever [CleJ, использовали Понятие авторитетных (authoritative) Web-страниц при ранжировании страниц для повышения релевантности ответов. Многие пользователи считают, что Web- сайт газеты New York Times является полезным сайтом и добавляют на свои собственные страницы ссылки на этот сайт. Количество ссылок на страницу является показателем как популярности, так и в некоторой сгепеии доверия пользователей к информации на этой странице. Если набор страниц ранжировап на основе числа ссылок, указывающих на эти страницы, то страницы, количество ссылок на которые наибольшее, возвращаются пользователю в первую очередь. Подобная классификация использует неявно выраженную степень доверия к странице пользователей. Такая информация собирается спайдерами и используется для рапжировапия результатов поиска. При этом существенно возрастает потенциальная релевантность результатов поиска, поскольку обычно люди не создают ссылки на мало полезные сайты. Программы разбиения сайтов на категории иснользуют снецифиче- ские характеристики сайтов, такие как большое число маленьких изображений и наличие определенных ключевых слов. Поисковые системы могут учитывать категории сайтов и возвращать более качественные результаты поиска. Набор ключевых слов, введенных пользователем для поиска, может использоваться для определения, что же действительно ищет пользователь. Например, при поиске домашней страницы пользователя в качестве ключевого слова наиболее часто указывается имя пользователя. Таким образом, если выражение для поиска представляется схожим с именем пользователя, оптимальным при ранжировании будег помещение на первое место домашпей страницы пользователя (если оиа существует).

Интервал времени между обработкой документа снайдером, составлением поисковой системой инвертированного ипдекса и использованием его при поиске может быть различным для различных поисковых систем. Обычно он находится в пределах от одной до двух недель. Если за это время документ изменяется, искомые ключевые слова могут больше не присутствовать в документе, когда пользователь осуществляет поиск. Что еще хуже, документ может быть удален с сайта. Web-сайт может быть недоступен во время проведения поиска. В действительности, принимая во внимание эти возможности, некоторые поисковые системы кэши- руют копии искомых ресурсов во время индексирования. Пользователь может, rio крайней мере, увидеть версию документа, имевшуюся на момент индексирования. Часго кэшируется только текст HTML, а встроенные изображения игнорируются.

Спайдер — довольно активно работающий клиент в смысле частоты и числа запросов. Он играет важную роль в одном из наиболее популярных приложений в Web — поиске. Совершенствование алгоритмов функционирования и эффективности спайдеров может оказать значительное влияние на Web.

Источник: Web-протоколы. Теория и практика. — M.: ЗАО «Издательство БИНОМ», 2002 г. – 592 c.: ил.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100