Google знает, как найти

Материал из Wiki.

Любая автоматизированная информационно-поисковая система (ИПС) состоит из двух основных частей: формирователя собственной базы данных и генератора ответов на запросы пользователей. Главными показателями для первой являются ее объем и продуманность внутренней структуры, а для второй - скорость поиска информации и удобство пользования. На самом деле такое деление очень условно, потому что функциональная гибкость запросов изначально зависит от структуры базы данных: невозможно запросить что-то, что не было заложено в алгоритмы разработчиками.

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

С другой стороны, пусть существует хорошо проработанная база данных. По определенному запросу пользователя программа-обработчик поисковой системы выдаст множество документов, где встречается заданное словосочетание. Задачей номер один для создателей ИПС является такая сортировка результатов поиска, чтобы в самых первых позициях находились именно те документы, которые были затребованы. Этот параметр называется релевантностью ответа. Если задать в поиске только общие слова, например <корм для собак>, тогда как вы ищете информацию про его ингредиенты, вряд ли в первой паре страниц отчета вам выдадут то, что вы искали. Поисковая система просто не в состоянии знать ваши мысли. Поэтому, задавая запрос, максимально конкретизируйте его для получения наиболее точного результата.

Давайте изучим внутреннюю структуру ИПС на примере Google (www.google.com.

Google появился сравнительно недавно, в 1998 г. Его создатели, сотрудники Стенфордского университета (США) Сергей Брин и Лоуренс Пейдж, постарались сделать его механизм более гибким и расширяемым, чем существовавшие на то время у грандов поиска - Аltavista и Inktomi. На данный момент Google и Fast (еще одна ИПС, www.alltheweb.com) имеют самый большой объем проиндексированных страниц - более двух миллиардов (данные на июль 2002 г.). Речь идет не только о собственно html- и xml-документах, но и pdf, doc и даже флэш-анимации. Причем только Google, в отличие от других иностранных ИПС (мы не рассматриваем "Яндекс", "Рамблер> и <Апорт>), хорошо индексирует русскоязычные Web-ресурсы в зоне.ru.

Почти в каждой поисковой системе есть своя внутренняя система оценки <качества> документов. В Google она называется PageRank (PR). Суть ее заключается в том, что при решении о порядке выдачи пользователю списка страниц, попадающих под его запрос, во внимание принимается некий коэффициент, зависящий от количества ссылок с других сайтов на эту страницу и от их популярности. На самом деле в этом есть рациональное зерно. Ведь если рассматриваемая страница действительно такая важная, что ее стоит прочитать, скорее всего, на нее уже ссылаются другие источники. Верно и обратное: если на документ никто не ссылается - кому он тогда нужен?! Причем PageRank - это не просто общая сумма ссылок, это нормализованное отношение количества ссылок, приводящих на данную страницу, к количеству исходящих c нее. Расчетная формула, опубликованная С. Брином и Л. Пейджем, выглядит следующим образом:

где d - эмпирически подобранный коэффициент (d=0.85); Т1...Tn - страницы, ссылающиеся на рассматриваемый документ; С(Tn)... С(Tn) - общее количество ссылок, ведущих вовне со страниц Т1...Tn.

Отсюда видно, что PageRank любого документа зависит от PageRank документов, с которых возможен переход на него. Таким образом, он всегда будет высоким для страниц, имеющих популярность в Интернете.

Важно также отметить, что PageRank имеет смысл вероятности, с которой среднестатистический Интернет-путешественник попадет на определенную страницу, хаотически блуждая по ссылкам. Сумма PageRank всех страниц равна единице

где N - количество проиндексированных страниц).

Вышеприведенная формула достаточно проста, и если задаться целью построить некоторое количество взаимосвязанных страниц, то, по-видимому, PageRank каждой может быть искусственно завышен. Например, можно попытаться сократить число ведущих вне ссылок и создать большое кольцо, в котором документ ссылается только на <друзей>. Тогда каждый из них вследствие итеративности алгоритмов расчета PageRank будет иметь достаточно высокий коэффициент <важности>. Несмотря на это в модели Google, вероятно, предусмотрены какие-то механизмы, позволяющие не начислять слишком высокий PageRank <подозрительным> и <нежелательным> сайтам. И естественно, эти механизмы являются ноу-хау и не подлежат разглашению.

Еще одна важная черта ИПС Google заключается в том, что в ней хранятся описания ссылок на проиндексированные страницы. Эта особенность позволяет более адекватно проводить поиск в накопленной базе данных. Скажем, автор странички забыл указать ее название между тегами <title></title>. Любая ИПС при выдаче результатов поиска ставит высокий приоритет словам, указанным именно в названии. В этом случае Google будет ориентироваться по текстам ссылок на эту страничку, справедливо основываясь на предположении, что если кто-то ставит ссылку на что-то, то уж, по крайней мере, он эту страничку изучил и постарался наиболее емко отобразить ее содержание в тексте ссылки. Именно поэтому во всех наставлениях по правильному оформлению содержимого документов имеется следующий совет.

Никогда не ставьте ссылку под словами <здесь>, <тут>, <сюда> (например: полную версию постановления смотри <a href=<...>>здесь</a>). Попробуйте написать так: <на сайте есть также и <a href=<...>>полная версия постановления</a>>. Кстати, сказанное верно еще и потому, что почти во всех браузерах текст внутри тега <a> подсвечивается тем или иным образом (выделяется подчеркиванием, цветом). Глаз при беглом просмотре странички более вероятно зацепится за выделенные информативные слова, чем за неконкретное краткое наставление <вам сюда>. Как говорится, покупатель и продавец, будьте взаимно вежливы!

Кроме расчетов PageRank и запоминания текста ссылок, Google хранит шрифтовой размер и смещение каждого слова относительно начала документа. (Примечание: некоторые ИПС ориентируются также и на цветовое выделение слов относительно текста.) В спецификации HTML 3.2 было определено семь уровней заголовков по размеру шрифта (от <h1> - самого крупного, до <h7> - самого мелкого). Поэтому поисковик всегда выдаст по запросу документ, в котором данное слово выделено более крупным шрифтом или находится ближе к его началу. Благодаря тому что система знает конкретное место каждого слова в документе, становится возможен так называемый Proximity search - поиск по наиболее близкому расположению слов друг относительно друга. Например, по запросу <слово1 слово2> ИПС найдет много документов у себя в базе данных, но в отчет в первых строках пойдут только те, в которых <слово1> находится максимально близко слева от <слова2>.

Теперь более подробно рассмотрим схему функционирования информационно-поисковой системы Google. Всю основную работу по просеиванию сквозь себя содержимого Сети выполняют Интернет-роботы (боты, crawlers). Каждый из них берет один адрес (URL, uniform resource locator; каждый URL соответствует определенному идентификатору документа) из базы данных URL-сервера, скачивает и передает содержимое странички на сервер хранения документов (рис. 1). Необходимо отметить, что все содержимое сервера хранится в заархивированном виде для увеличения его вместимости.

Рис. 1. Структура информационно-поисковой системы Google

Другая программа - индексатор - занимается тем, что разлагает текст документа на составляющие его слова (хит в терминологии Google), запоминая при этом местонахождение, шрифтовой вес, а также написано ли слово заглавными или строчными буквами и принадлежит ли оно к категории <особенных> (названия документов, метатеги, URL'ы и тексты ссылок). Вся эта информация складывается в набор контейнеров, именуемых на рисунке прямым индексом. Структура хранимых в нем данных выглядит следующим образом (рис. 2).

Рис. 2. Структура прямого индекса (doc_id - идентификатор документа; word_id - идентификатор слова; null_word - символ окончания документа; n_hits - частота, с которой слово встречается в документе)

Идентификаторы слов берутся из словаря, который постоянно пополняется. Одновременно с этим индексатор просматривает содержимое тегов <a></a> и проверяет корректность всех ссылок в службе разрешения имен DNS (domain name service). Если ему встретился URL, которого нет в базе данных по doc_id, он пополняет не только ее, но и коллекцию ссылок. В дальнейшем этот Интернет-адрес попадает в URL-сервер и круг замыкается. Система поиска новых документов, при условии, что на них хоть кто-нибудь ссылается, становится самодостаточной - она сама себя подпитывает.

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

Заметим, что каждая из программ, обозначенных на рис. 1 эллипсом, работает независимо от других, причем аппаратные конфигурации серверов и рабочих станций, на которых функционирует <движок> Google, выбираются так, чтоб не создавать <пробок> при обработке информации, собранной Интернет-роботами.

Описанная выше структура прямого индекса не очень удобна при поиске документов на основании встречающихся в них слов (пользователь задает слово или словосочетание, а система должна найти подходящий документ). Чтобы решить эту проблему, был введен так называемый инверсный, или обратный, индекс (рис. 3). В нем любому слову из словаря соответствует набор doc_id-документов, в которых это слово встречается. Работой по постоянному формированию инверсного индекса занимаются сортировщики. Так как, во-первых, всегда появляются новые документы и, во-вторых, обновляются старые, индекс приходится постоянно перестраивать.

Рис. 3. Структура инверсного индекса (word_id - идентификатор слова; ndocs - количество документов с этим словом; doc_id - идентификатор документа; n_hits - частота, с которой слово встречается в документе)

Пусть от пользователя поступил запрос найти документы со словом <мухобойка>. Программа, формирующая ответы, посмотрит в словарь, найдет там word_id для <мухобойки>, сформирует запрос в базу данных с использованием инверсного индекса и получит набор документов, в которых это слово встречается. Далее на основании PageRank, количества хитов, их качества и, может быть, других ограничений и приоритетов разработчиков будут распределены порядковые номера страниц в выходном списке. В итоге Интернет-пользователь получит самую оптимальную, по мнению ИПС, информацию о том, где и что писали о правилах и способах мухоубийства.

Качество поисковой системы, как уже было отмечено, зависит не только от количества проиндексированных документов, правил их отбора в итоговый список, но и от того, как часто Интернет-роботы заново проверяют содержимое ранее обработанных сайтов. В таблице на примере thermo.karelia.ru приведены данные об общем объеме запрошенных роботами документов и количестве заходов на сайт (по данным Webalizer - анализатора журналов Web-сервера).

Из таблицы видно, что роботы <Яндекса> и Google ведут себя по-разному. <Яндекс> останавливается на корневом документе Web-сервера (например, index.html) и скачивает содержимое сайта последовательно, документ за документом, в один поток. Google распараллеливает работу между несколькими роботами, причем каждый из них при скачивании может <отвлекаться> на другие дела. То есть эти две поисковые системы характеризуются совершенно различными структурами URL-серверов и способами пополнения информации из Интернета.

Второй важный вывод, который напрашивается по результатам изучения приведенной таблицы, заключается в том, что русскоязычные поисковики <лучше> иностранных, они более часто посещают ресурсы постсоветского пространства. Даже <Апорт>, уступивший на данный момент третье место Google по общему количеству обрабатываемых запросов (данные с www.spylog.ru), как минимум раз в месяц просматривает содержимое каждого сайта.

Последние две строчки в таблице требуют некоторых пояснений. За надписью Sunet.ru скрывается один из московских провайдеров Интернет-услуг (e-Style). Причем поражает завидное постоянство, с которым действует их робот. Какой из поисковых систем они предоставляют информацию и предоставляют ли ее вообще - автору неизвестно.

Dec.com - робот некогда существовавшего гиганта Digital Equipment Corporation (впоследствии он был перекуплен компанией Compaq). Dec поддерживал Altavista, поэтому можно предположить, что получаемая информация идет в закрома самой известной ИПС.

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

На основании изложенных соображений можно выделить ряд рекомендаций создателям Web-ресурсов для улучшения позиций их проектов в рейтингах информационно-поисковых систем (впрочем, не только для этого):

• четко продумывать структуру каждого сайта;
• называть каждую страницу уникальным именем, максимально отражающим ее содержимое;
• избегать использования одного и того же имени файла для группы документов с передачей после него различных параметров (например, index.php? razdel=1&document=2) (программисты иногда забывают менять значение переменной, содержащей название документа);
• избегать навигации "плохо индексируемыми" способами (формы, флэш-анимация).

[править] Об авторе

Алексей Петрович Мощевикин - к.ф.-м.н., Петрозаводский государственный университет, alexmou@dfe3300.karelia.ru

[править] Объем документов, загруженных роботами поисковых систем с thermo.karelia.ru, Мбайт

Примечание. в скобках указано количество заходов роботом на сайт за месяц

© Алексей Мощевикин

Источник|2003