Веб-краулеры: систематический обход Всемирной паутины

Введение

Программное обеспечение, которое систематически просматривает Всемирную паутину.

Веб-сканер, иногда называемый пауком или spiderbot и часто сокращаемый до crawler, — это интернет-бот, который систематически просматривает Всемирную паутину и обычно управляется поисковыми системами для индексации веб-сайтов (web spidering). Поисковые системы и некоторые другие веб-сайты используют программное обеспечение для сканирования или обхода веб-сайтов, чтобы обновлять свой веб-контент или индексы веб-контента других сайтов. Веб-сканеры копируют страницы для обработки поисковой системой, которая индексирует загруженные страницы, чтобы пользователи могли более эффективно осуществлять поиск. Сканеры потребляют ресурсы посещаемых систем и часто посещают сайты без запроса. При доступе к большим коллекциям страниц возникают вопросы планирования, нагрузки и "вежливости". Существуют механизмы, позволяющие общедоступным сайтам, не желающим быть просканированными, сообщить об этом сканирующему агенту. Например, включение файла robots.txt может потребовать от ботов индексировать только части веб-сайта или не индексировать его вовсе. Количество интернет-страниц чрезвычайно велико; даже самые крупные сканеры не могут создать полный индекс. По этой причине поисковым системам было сложно выдавать релевантные результаты поиска в первые годы существования Всемирной паутины, до 2000 года. Сегодня релевантные результаты выдаются практически мгновенно. Сканеры могут проверять гиперссылки и HTML-код. Они также могут использоваться для веб-скрейпинга и программирования, основанного на данных.

Номенклатура

Веб-краулер также известен как паук, муравей, автоматический индексатор или (в контексте программного обеспечения FOAF) веб-скаттер.

Обзор

Веб-сканер начинает с перечня URL-адресов для посещения. Эти начальные URL-адреса называются зерновыми. По мере посещения этих URL-адресов, осуществляя взаимодействие с веб-серверами, отвечающими на эти запросы, сканер определяет все гиперссылки на полученных веб-страницах и добавляет их в список URL-адресов, ожидающих обработки – так называемый фронтир сканирования. URL-адреса из фронтира посещаются рекурсивно в соответствии с определенным набором правил. Если сканер выполняет архивирование веб-сайтов (или веб-архивирование), он копирует и сохраняет информацию в процессе работы. Архивы обычно хранятся таким образом, чтобы их можно было просматривать, читать и перемещаться по ним, как по действующему веб-сайту, но они сохраняются в виде «снимков». Архив известен как репозиторий и предназначен для хранения и управления коллекцией веб-страниц. В репозитории хранятся только HTML-страницы, при этом каждая страница сохраняется как отдельный файл. Репозиторий аналогичен любой другой системе хранения данных, например, современной базе данных. Единственное отличие состоит в том, что репозиторию не требуется весь функционал, предлагаемый системой управления базами данных. Репозиторий хранит самую последнюю версию веб-страницы, полученную сканером. Большой объем данных означает, что сканер может загрузить лишь ограниченное количество веб-страниц за определенный промежуток времени, поэтому ему необходимо расставлять приоритеты при загрузке. Высокая скорость изменений может означать, что страницы уже были обновлены или даже удалены. Огромное количество потенциальных URL-адресов, генерируемых серверным программным обеспечением, также затрудняет для веб-сканеров избежание извлечения дублирующегося контента. Существуют бесконечные комбинации параметров HTTP GET (основанных на URL), из которых лишь небольшая часть фактически возвращает уникальный контент. Например, простая онлайн-галерея фотографий может предлагать пользователям три опции, заданные через параметры HTTP GET в URL. Если существует четыре способа сортировки изображений, три варианта размера эскизов, два формата файлов и возможность отключения контента, предоставленного пользователями, то к одному и тому же набору контента можно получить доступ через 48 различных URL-адресов, все из которых могут быть размещены на сайте. Эта математическая комбинация создает проблему для сканеров, поскольку им приходится просматривать бесконечные комбинации относительно незначительных изменений, вносимых скриптами, чтобы извлечь уникальный контент. Как отмечали Эдвардс и др., «учитывая, что пропускная способность для проведения сканирования не является ни бесконечной, ни бесплатной, становится все более важным сканировать Web не только масштабируемым, но и эффективным способом, если необходимо поддерживать разумный уровень качества или актуальности». Сканер должен тщательно выбирать на каждом шаге, какие страницы посетить следующими.

A Web crawler starts with a list of URLs to visit. Those first URLs are called the seeds. As the crawler visits these URLs, by communicating with web servers that respond to those URLs, it identifies all the hyperlinks in the retrieved web pages and adds them to the list of URLs to visit, called the crawl frontier. URLs from the frontier are recursively visited according to a set of policies. If the crawler is performing archiving of websites (or web archiving), it copies and saves the information as it goes. The archives are usually stored in such a way they can be viewed, read and navigated as if they were on the live web, but are preserved as 'snapshots'. The archive is known as the repository and is designed to store and manage the collection of web pages. The repository only stores HTML pages and these pages are stored as distinct files. A repository is similar to any other system that stores data, like a modern day database. The only difference is that a repository does not need all the functionality offered by a database system. The repository stores the most recent version of the web page retrieved by the crawler. The large volume implies the crawler can only download a limited number of the Web pages within a given time, so it needs to prioritize its downloads. The high rate of change can imply the pages might have already been updated or even deleted. The number of possible URLs crawled being generated by server side software has also made it difficult for web crawlers to avoid retrieving duplicate content. Endless combinations of HTTP GET (URL based) parameters exist, of which only a small selection will actually return unique content. For example, a simple online photo gallery may offer three options to users, as specified through HTTP GET parameters in the URL. If there exist four ways to sort images, three choices of thumbnail size, two file formats, and an option to disable user provided content, then the same set of content can be accessed with 48 different URLs, all of which may be linked on the site. This mathematical combination creates a problem for crawlers, as they must sort through endless combinations of relatively minor scripted changes in order to retrieve unique content. As Edwards et al. noted, "Given that the bandwidth for conducting crawls is neither infinite nor free, it is becoming essential to crawl the Web in not only a scalable, but efficient way, if some reasonable measure of quality or freshness is to be maintained." A crawler must carefully choose at each step which pages to visit next.

Политика отбора

Учитывая нынешний размер Интернета, даже крупные поисковые системы охватывают лишь часть общедоступной его части. Исследование 2009 года показало, что даже крупномасштабные поисковые системы индексируют не более 40–70% индексируемого Веба; предыдущее исследование Стива Лоуренса и Ли Джайлса показало, что ни одна поисковая система не индексировала более 16% Веба в 1999 году. Поскольку сканер всегда загружает лишь часть веб-страниц, крайне желательно, чтобы загруженная часть содержала наиболее релевантные страницы, а не просто случайную выборку. Для этого требуется метрика важности для приоритизации веб-страниц. Важность страницы является функцией ее внутреннего качества, популярности в терминах ссылок или посещений и даже ее URL-адреса (последнее справедливо для вертикальных поисковых систем, ограниченных одним доменом верхнего уровня, или поисковых систем, ограниченных фиксированным веб-сайтом). Разработка хорошей политики отбора имеет дополнительную сложность: она должна работать с неполной информацией, поскольку полный набор веб-страниц неизвестен во время сканирования. Чжунху Чо и др. провели первое исследование политик планирования сканирования. Их набор данных состоял из 180 000 страниц домена stanford.edu, на котором было проведено моделирование сканирования с использованием различных стратегий. Протестированными метриками упорядочивания были: поиск в ширину, количество обратных ссылок и частичные вычисления PageRank. Один из выводов заключался в том, что если сканер хочет загружать страницы с высоким PageRank на ранних этапах процесса сканирования, то стратегия частичного PageRank предпочтительнее, за ней следует поиск в ширину и количество обратных ссылок. Однако эти результаты относятся только к одному домену. Чо также написал докторскую диссертацию в Стэнфорде, посвященную сканированию Веба. Наджорк и Винер провели фактическое сканирование 328 миллионов страниц, используя поиск в ширину. Они обнаружили, что поиск в ширину захватывает страницы с высоким PageRank на ранних этапах сканирования (но не сравнивали эту стратегию с другими). Объяснение, данное авторами, заключается в том, что "самые важные страницы имеют много ссылок с многочисленных хостов, и эти ссылки будут найдены рано, независимо от того, с какого хоста или страницы начинается сканирование". Абитебуль разработал стратегию сканирования, основанную на алгоритме OPIC (On-line Page Importance Computation). В OPIC каждой странице присваивается начальная сумма "денег", которая равномерно распределяется между страницами, на которые она указывает. Это похоже на вычисление PageRank, но оно быстрее и выполняется за один шаг. Сканер, управляемый OPIC, сначала загружает страницы в границе сканирования с более высокими суммами "денег". Эксперименты проводились на синтетическом графе из 100 000 страниц с распределением степенного закона входящих ссылок. Однако сравнения с другими стратегиями или экспериментов в реальном Вебе не проводилось. Болди и др. использовали моделирование на подмножествах Веба из 40 миллионов страниц домена .it и 100 миллионов страниц из сканирования WebBase, тестируя поиск в ширину против поиска в глубину, случайный порядок и всезнающую стратегию. Сравнение основывалось на том, насколько хорошо PageRank, вычисленный на частичном сканировании, приближает истинное значение PageRank. Некоторые посещения, которые очень быстро накапливают PageRank (в частности, поиск в ширину и всезнающее посещение), обеспечивают очень плохие последовательные приближения. Баэза-Ятес и др. использовали моделирование на двух подмножествах Веба из 3 миллионов страниц доменов .gr и .cl, тестируя несколько стратегий сканирования. Они показали, что стратегия OPIC и стратегия, использующая длину очередей на сайт, лучше, чем поиск в ширину, и что также очень эффективно использовать предыдущее сканирование, когда оно доступно, для управления текущим. Данешпажух и др. разработали алгоритм на основе сообществ для обнаружения хороших начальных точек. Их метод сканирует веб-страницы с высоким PageRank из разных сообществ за меньшее количество итераций по сравнению со сканированием, начинающимся со случайных начальных точек. С помощью этого нового метода можно извлечь хорошие начальные точки из ранее сканированного веб-графа. Используя эти начальные точки, новое сканирование может быть очень эффективным.

Given the current size of the Web, even large search engines cover only a portion of the publicly available part. A 2009 study showed even large scale search engines index no more than 40–70% of the indexable Web; a previous study by Steve Lawrence and Lee Giles showed that no search engine indexed more than 16% of the Web in 1999. As a crawler always downloads just a fraction of the Web pages, it is highly desirable for the downloaded fraction to contain the most relevant pages and not just a random sample of the Web. This requires a metric of importance for prioritizing Web pages. The importance of a page is a function of its intrinsic quality, its popularity in terms of links or visits, and even of its URL (the latter is the case of vertical search engines restricted to a single top level domain, or search engines restricted to a fixed Web site). Designing a good selection policy has an added difficulty: it must work with partial information, as the complete set of Web pages is not known during crawling. Junghoo Cho et al. made the first study on policies for crawling scheduling. Their data set was a 180,000 pages crawl from the stanford. edu domain, in which a crawling simulation was done with different strategies. The ordering metrics tested were breadth first, backlink count and partial PageRank calculations. One of the conclusions was that if the crawler wants to download pages with high Pagerank early during the crawling process, then the partial Pagerank strategy is the better, followed by breadth first and backlink count. However, these results are for just a single domain. Cho also wrote his PhD dissertation at Stanford on web crawling. Najork and Wiener performed an actual crawl on 328 million pages, using breadth first ordering. They found that a breadth first crawl captures pages with high Pagerank early in the crawl (but they did not compare this strategy against other strategies). The explanation given by the authors for this result is that "the most important pages have many links to them from numerous hosts, and those links will be found early, regardless of on which host or page the crawl originates." Abiteboul designed a crawling strategy based on an algorithm called OPIC (On line Page Importance Computation). In OPIC, each page is given an initial sum of "cash" that is distributed equally among the pages it points to. It is similar to a PageRank computation, but it is faster and is only done in one step. An OPIC driven crawler downloads first the pages in the crawling frontier with higher amounts of "cash". Experiments were carried in a 100,000 pages synthetic graph with a power law distribution of in links. However, there was no comparison with other strategies nor experiments in the real Web. Boldi et al. used simulation on subsets of the Web of 40 million pages from the it domain and 100 million pages from the WebBase crawl, testing breadth first against depth first, random ordering and an omniscient strategy. The comparison was based on how well PageRank computed on a partial crawl approximates the true PageRank value. Some visits that accumulate PageRank very quickly (most notably, breadth first and the omniscient visit) provide very poor progressive approximations. Baeza Yates et al. used simulation on two subsets of the Web of 3 million pages from the gr and cl domain, testing several crawling strategies. They showed that both the OPIC strategy and a strategy that uses the length of the per site queues are better than breadth first crawling, and that it is also very effective to use a previous crawl, when it is available, to guide the current one. Daneshpajouh et al. designed a community based algorithm for discovering good seeds. Their method crawls web pages with high PageRank from different communities in less iteration in comparison with crawl starting from random seeds. One can extract good seed from a previously crawled Web graph using this new method. Using these seeds, a new crawl can be very effective.

Ограничение последующих ссылок

Возможно, сканер захочет находить только HTML-страницы и избегать всех остальных типов MIME. Чтобы запрашивать только HTML-ресурсы, сканер может отправлять HTTP HEAD-запрос для определения типа MIME веб-ресурса перед запросом всего ресурса с помощью GET-запроса. Чтобы избежать большого количества HEAD-запросов, сканер может анализировать URL и запрашивать ресурс только если URL заканчивается определенными символами, такими как html, htm, asp, aspx, php, jsp, jspx или косой чертой. Эта стратегия может привести к непреднамеренному пропуску множества HTML-веб-ресурсов. Некоторые сканеры также могут избегать запроса ресурсов, содержащих символ "?" (динамически генерируемых), чтобы избежать ловушек для сканеров, которые могут привести к загрузке сканером бесконечного количества URL-адресов с веб-сайта. Эта стратегия ненадежна, если сайт использует переписывание URL для упрощения своих адресов.

Нормализация URL

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

Поднимающийся по тропе ползание

Некоторые веб-сканеры стремятся загрузить как можно больше ресурсов с определенного веб-сайта. Для этого был разработан сканер с обходом по пути, который поднимается по каждому пути в каждом URL, который он собирается просканировать. Например, если начальный URL — http://llama.org/hamster/monkey/page.html, он попытается просканировать /hamster/monkey/, /hamster/ и /. Коти обнаружил, что такой сканер очень эффективен для поиска изолированных ресурсов или ресурсов, для которых не была бы найдена ни одна входящая ссылка при обычном сканировании.

Фокусированный ползание

Важность страницы для сканера также может быть выражена как функция сходства страницы с заданным запросом. Веб-сканеры, которые пытаются загрузить страницы, похожие друг на друга, называются тематическими или сфокусированными сканерами. Концепции тематического и сфокусированного сканирования впервые были предложены Филиппо Менчером и Соуменом Чакрабарти с соавторами. Основная проблема при сфокусированном сканировании заключается в том, что в контексте веб-сканера желательно иметь возможность предсказать сходство текста данной страницы с запросом до её фактической загрузки. Возможным предиктором является анкорный текст ссылок; такой подход использовал Пинкертон в одном из первых веб-сканеров на заре развития Интернета. Дилигенти и др. предлагают использовать полное содержание уже посещенных страниц для оценки сходства между исходным запросом и ещё не посещенными страницами. Эффективность сфокусированного сканирования в значительной степени зависит от обилия ссылок по конкретной теме поиска, и обычно сфокусированный сканер использует общую веб-поисковую систему для получения начальных точек.

Академический ориентированный ползучий

Примером сфокусированных сканеров являются академические сканеры, которые собирают документы, относящиеся к академической сфере и находящиеся в свободном доступе, такие как citeseerxbot – сканер поисковой системы CiteSeerX. Другие академические поисковые системы включают Google Scholar и Microsoft Academic Search. Поскольку большинство научных работ публикуются в формате PDF, такие сканеры особенно заинтересованы в сборе файлов PDF, PostScript и Microsoft Word, включая их zip-архивы. В связи с этим, универсальные сканеры с открытым исходным кодом, такие как Heritrix, нуждаются в настройке для фильтрации других типов MIME, либо используется промежуточное программное обеспечение для извлечения этих документов и импорта их в базу данных и хранилище сфокусированного сканирования. Определение академической принадлежности документов – сложная задача, которая может существенно увеличить нагрузку на процесс сканирования, поэтому она обычно выполняется после сканирования с использованием машинного обучения или алгоритмов регулярных выражений. Эти академические документы обычно получают со страниц факультетов и студентов, или со страниц публикаций исследовательских институтов. Поскольку академические документы составляют лишь небольшую долю всех веб-страниц, правильный выбор начальных URL (seed URLs) важен для повышения эффективности этих веб-сканеров. Другие академические сканеры могут загружать текстовые и HTML-файлы, содержащие метаданные научных работ, такие как названия, статьи и аннотации. Это увеличивает общее количество найденных работ, но значительная часть из них может не предоставлять бесплатную возможность загрузки PDF-файлов.

Семантически ориентированный сканер

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

Политика параллелизации

Параллельный обходчик — это обходчик, который запускает несколько процессов параллельно. Цель состоит в том, чтобы максимизировать скорость загрузки данных, минимизируя накладные расходы, связанные с параллелизацией, и избегать повторной загрузки одной и той же страницы. Чтобы избежать загрузки одной и той же страницы более одного раза, системе обхода требуется политика распределения новых URL-адресов, обнаруженных в процессе обхода, поскольку один и тот же URL-адрес может быть найден двумя разными процессами обхода.

Безопасность

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

Идентификация ползучего

Веб-сканеры обычно идентифицируют себя веб-серверу, используя поле User-Agent в HTTP-запросе. Администраторы веб-сайтов обычно анализируют журналы своих веб-серверов и используют поле User-Agent, чтобы определить, какие сканеры посещали веб-сервер и как часто. В поле User-Agent может быть указан URL-адрес, по которому администратор веб-сайта может найти дополнительную информацию о сканере. Анализ журналов веб-серверов – трудоемкая задача, поэтому некоторые администраторы используют инструменты для идентификации, отслеживания и проверки веб-сканеров. Спамботы и другие вредоносные веб-сканеры вряд ли будут указывать идентифицирующую информацию в поле User-Agent, либо могут маскировать себя под браузер или другого известного сканера. Администраторы веб-сайтов предпочитают, чтобы веб-сканеры идентифицировали себя, чтобы при необходимости можно было связаться с их владельцем. В некоторых случаях сканеры могут случайно попасть в "ловушку для сканеров" или перегружать веб-сервер запросами, и владельцу потребуется их остановить. Идентификация также полезна для администраторов, которым важно знать, когда можно ожидать индексации их веб-страниц определенной поисковой системой.

Попадая в глубокую сеть

Огромное количество веб-страниц находится в глубинной или невидимой сети. Доступ к этим страницам обычно возможен только путем отправки запросов к базе данных, и обычные поисковые роботы не могут их обнаружить, если на них нет ссылок. Протокол Google Sitemaps и формат OAI предназначены для обнаружения этих ресурсов глубинной сети. Сканирование глубинной сети также увеличивает количество веб-ссылок, подлежащих сканированию. Некоторые роботы обрабатывают только часть URL-адресов в форме <a href="URL">. В некоторых случаях, например, Googlebot, веб-сканирование выполняется по всему тексту, содержащемуся в гипертекстовом контенте, тегах или тексте. Для работы с контентом глубинной сети могут применяться специальные стратегии. С помощью технологии, называемой парсингом (или веб-скрейпингом), специализированное программное обеспечение может быть настроено для автоматического и многократного отправления запросов к определенной веб-форме с целью сбора полученных данных. Такое программное обеспечение может использоваться для работы с несколькими веб-формами на разных веб-сайтах. Данные, извлеченные из результатов отправки одной веб-формы, могут быть использованы в качестве входных данных для другой веб-формы, обеспечивая таким образом непрерывность в глубинной сети, что невозможно при использовании традиционных поисковых роботов. Страницы, созданные с использованием AJAX, являются одними из тех, которые создают проблемы для поисковых роботов. Google предложил формат AJAX-запросов, который его робот может распознавать и индексировать.

Визуальные и программные сканеры

В Интернете доступно несколько продуктов "визуального веб-скрейпера/паука", которые обходят страницы и структурируют данные в столбцы и строки в соответствии с требованиями пользователей. Одно из основных отличий между классическим и визуальным пауком – это уровень навыков программирования, необходимых для его настройки. Новейшее поколение "визуальных скрейперов" устраняет большую часть необходимости в программировании для настройки и запуска сбора веб-данных. Метод визуального скрейпинга/обхода основан на "обучении" пользователем технологии паука, которая затем выявляет закономерности в полуструктурированных источниках данных. Основной способ обучения визуального паука – выделение данных в браузере и определение столбцов и строк. Хотя технология не нова – например, она легла в основу Needlebase, которую приобрела Google (в рамках более масштабной сделки по покупке ITA Labs) – в этой области наблюдается постоянный рост и инвестиции со стороны инвесторов и конечных пользователей.

Исторические веб-сканеры

World Wide Web Worm был поисковым роботом, использовавшимся для создания простого индекса названий документов и URL-адресов. Этот индекс можно было искать с помощью команды grep в Unix. Yahoo! Slurp было названием поискового робота Yahoo! до тех пор, пока Yahoo! не заключил контракт с Microsoft на использование Bingbot вместо него.

Внутренние веб-сканеры

Applebot — веб-сканер Apple. Он поддерживает Siri и другие продукты. Bingbot — это название веб-сканера Bing от Microsoft. Он заменил Msnbot. Baiduspider — веб-сканер Baidu. DuckDuckBot — веб-сканер DuckDuckGo. Googlebot описан в некоторых деталях, но ссылка относится только к ранней версии его архитектуры, написанной на C++ и Python. Сканер был интегрирован с процессом индексации, поскольку текстовый анализ выполнялся как для полнотекстовой индексации, так и для извлечения URL-адресов. Существует URL-сервер, который отправляет списки URL-адресов для обработки несколькими процессами сканирования. В процессе анализа найденные URL-адреса передавались на URL-сервер, который проверял, не были ли они просмотрены ранее. Если нет, URL-адрес добавлялся в очередь URL-сервера. WebCrawler использовался для создания первого общедоступного полнотекстового индекса части Веба. Он был основан на lib WWW для загрузки страниц и другой программе для анализа и упорядочения URL-адресов для обхода веб-графа в ширину. Он также включал сканер в реальном времени, который переходил по ссылкам на основе сходства анкорного текста с заданным запросом. WebFountain — распределенный модульный сканер, аналогичный Mercator, но написанный на C++. Xenon — веб-сканер, используемый государственными налоговыми органами для выявления мошенничества.