Архивы: по дате | по разделам | по авторам

Единица и сто нулей

Архив
автор : Андрей Драница   27.04.2002

Google - искаженное написание английского слова "googol", придуманного Милтоном Сироттой, племянником американского математика Эдварда Кайзера, для обозначения числа, состоящего из единицы и ста нулей.

Google - искаженное написание английского слова «googol», придуманного Милтоном Сироттой, племянником американского математика Эдварда Кайзера, для обозначения числа, состоящего из единицы и ста нулей.

Откуда он взялся такой?

Как и многие знаковые проекты в сфере ИТ, Google обязан своим появлением двум незаурядным людям - Лоуренсу Пейджу (Lawrence Page) и Сергею Брину (Sergey Brin). Последний, кстати, является нашим, пусть и бывшим, соотечественником, перебравшимся в Соединенные Штаты.

Работа над проектом началась в 1995 году в стенах Стэнфордского университета 1 и довольно быстро принесла первые плоды в виде Back Rub (1996) - прототипа Google. А через три года была создана компания Google и запущен собственно поисковый сервер.

Индекс ресурсов, охватывающий миллиард с лишним веб-страниц 2, размещается на массиве недорогих резервируемых серверов (RAIS). Для поиска в такой огромной базе данных (более 2 терабайт) используется пул из шести тысяч серверов, занимающих три вычислительных центра 3. Серверы имеют оперативную память объемом от 256 Мбайт до 1 Гбайт и работают под управлением RedHat Linux.

Дисковые подсистемы тоже вполне «земные»: вместо высокоскоростных подсистем SCSI компания применяет в качестве стандарта более дешевую технологию IDE. Обширный поисковый каталог Google распределен и дублируется на более чем семи тысячах отдельных дисковых накопителей, что позволяет сбалансировать нагрузку, направляя запросы на доступные в данный момент серверы и дисковые подсистемы.

Только на своем сайте Google обрабатывает больше 20 миллионов запросов в сутки, и еще около 45 миллионов приходит с сайтов партнеров (Yahoo, Netscape, Cisco). Применение RAIS позволило создать расширяемую модульную систему, которая может приспосабливаться к пиковым нагрузкам, - причем систему надежную и относительно недорогую. Так как более половины запросов приходит из-за пределов США, компания собирается открыть филиалы в Азии и Европе, чтобы снизить потери времени при поиске.

На сегодняшний день более 30 тысяч сайтов используют Google в качестве локальной поисковой системы (примерно такой же сервис у нас предоставляет «Яндекс»).

Google Inside

Прежде всего, Google - это целый программный комплекс, объединяющий несколько взаимосвязанных компонентов.

Первый из них - «веб-паук» (Crawler), в его задачу входит непосредственная загрузка веб-страниц из Интернета. Обычно параллельно работают три таких поисковых робота, каждый из которых может одновременно загружать до трехсот документов. Все веб-пауки связаны с сервером ссылок (URLServer 4), который хранит и передает ссылки «паукам» на обработку.

После загрузки веб-страница, получив уникальный номер - docID, отправляется в специальное хранилище - Storeserver. Этот сервер занимается сжатием и хранением веб-страниц в архиве.

Затем эстафета передается индексатору (Indexer), который извлекает документ из архива и обрабатывает его. Документ конвертируется в набор входящих в него слов, так называемые хиты (hits). Каждая запись о хите содержит собственно слово, его позицию в документе, информацию о регистре и размере шрифта, которым это слово отображено. Далее индексатор распределяет хиты в хранилища, называемые цилиндрами (Barrels), тем самым создавая частично отсортированный предварительный индекс. У индексатора есть и дополнительная функция - извлечение ссылок и их запись в специальный файл, который содержит всю возможную информацию о ссылке: ее текст, к какому файлу она принадлежит и куда указывает.

Следующий компонент - обработчик ссылок (URLResolver) - читает сформированный индексатором файл ссылок, конвертирует относительные URL в абсолютные, помещает текст ссылки в предварительный индекс и устанавливает docID того документа, на который ссылка указывает. Вторая задача URLresolver - составление базы данных связей между документами. В дальнейшем эта база используется для определения ранга документа, PageRank (об этой хитрой штуке мы поговорим отдельно).

Затем за дело берется программа сортировки (Sorter). Она сортирует цилиндры по идентификаторам слов (wordIDs) и помещает результаты в инвертированный индекс. Сортировщик генерирует список идентификаторов слов и их смещение в инвертированном индексе.

Генератор словарей (DumpLexicon) берет этот список вместе со словарем, сформированным индексатором, и составляет новый словарь, который в дальнейшем служит для поиска документов по запросам конечных пользователей.

Конечное звено этой схемы - сервер поиска (Searcher). Он работает вместе с веб-сервером и для ответов на запросы использует словарь, сформированный DumpLexicon, вместе с инвертируемым индексом и PageRank.

Секрет Google

Список наград и призовых мест, занятых Google в различных отраслевых топах, конечно, впечатляет. Чем же этот поисковый механизм завоевал сердца множества пользователей, от сетевых обозревателей до рядовых «серферов»? Одна из важнейших причин - высокая релевантность, то бишь соответствие между ожидаемым и фактически полученным. С учетом того, что это самое соответствие есть категория субъективная, возникает резонный вопрос: почему одна «бездушная железка» выдает более релевантные результаты, чем другие такие же поисковые серверы? Ведь не искусственный же интеллект отвечает на запросы! В индексировании от Google нет ничего особенного, аналогичным образом это делают и другие поисковики. «Секрет фирмы» - в том, как Google сортирует сотни и тысячи найденных страниц, выделяя из них наиболее подходящие, независимо от их посещаемости или присутствия в Интернет-каталогах.

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

Есть и упрощенное, так сказать гуманитарное, объяснение принципа PageRank. Представьте себе человека за компьютером, «ползающего» (или летающего, в зависимости от скорости соединения) по Сети. Он открывает случайную страницу (просто набрал абракадабру в строке Location и попал на какой-то сайт) и жмет на случайно выбранную ссылку. Перемещается на другую страницу, опять жмет на случайную ссылку и так далее, постоянно переходя от страницы к странице, но никогда не нажимая кнопку Back. Иногда ему такое блуждание надоедает, и он снова перескакивает на случайную страницу - не по ссылке, а наугад набрав URL. Так вот, вероятность того, что блуждающий серфер зайдет на домашнюю страничку Васи Пупкина, и есть ее PageRank.

Очевидно, что PageRank вашей страницы тем выше, чем больше других страниц ссылается на нее и чем эти страницы популярнее. Повысить PageRank и, как следствие, подняться в списке результатов поиска можно двумя методами. Первый - сделать страницу популярной (не путать с посещаемой!), чтобы на нее как можно чаще указывали другие. Второй - добиться того, чтобы какая-то страница с высоким PageRank поставила на вас ссылку. Но сущность PageRank такова, что им сложно манипулировать: добиться, чтобы ссылку на вашу страницу разместили на Yahoo, не менее трудно, чем получить признание сотни веб-мастеров, которые будут ссылаться на ваше творение.

Чем живет Google

Большинство Интернет-компаний переживают не лучшие времена. Сокращать рекламные бюджеты и персонал дальше некуда, поэтому многие стали ликвидировать или переводить на коммерческие рельсы бесплатные услуги, пытаться активнее зарабатывать на рекламе и т. п. А за счет чего живет Google? Ответ одновременно и банален, и удивителен: за счет рекламы, той самой, которая не может прокормить и более именитых игроков на этом рынке. Не секрет, что владельцы поисковых серверов продают места в списках результатов самых популярных запросов. Одни - открыто, другие - нет, но, так или иначе, пользователь на первом месте получает не наиболее релевантную, а наиболее оплаченную ссылку. Google пошел другим путем: рекламные ссылки выдаются отдельно от основных результатов поиска и выделены визуально, что не мешает им демонстрировать хорошую отдачу - после окончания рекламных кампаний больше половины клиентов подписывают новые контракты, несмотря на довольно высокую стоимость размещения (от 8 до 15 долларов за тысячу показов).

Второй источник существования - доходы от лицензирования технологии Google: в настоящий момент ее используют более восьмидесяти компаний, в их числе Yahoo, Netscape и Cisco.

Планов у «единицы со ста нулями» громадье, и большинство из них носит, к чести Google, конструктивный, а не популистский характер. Так, в ближайшее время не планируется ввести поиск по FTP или MP3, несмотря на его востребованность: по технологическим причинам сделать из этого действительно полезный и релевантный сервис пока трудно, а марку ронять негоже. Зато к специализированным сервисам (поиск изображений и поиск в группах новостей) добавится поиск по PDF-файлам и новостным сайтам. Компания не оставит без внимания и корпоративный рынок: уже вышло в свет Google Search Appliance (см. «КТ» #432) - специализированное аппаратно-программное решение для поиска в интрасетях. С начала апреля Google перешел на более продвинутую технологию ранжирования сайтов, разработанную с учетом последних достижений в области биофизики - PigeonRank (подробнее об этом можно прочитать здесь: www.google.com/technology/pigeonrank.html).

И, как сказал в одном из интервью Сергей Брин, команда Google всегда будет заниматься совершенствованием механизмов поиска, что для нас, пользователей Интернета, есть несомненное благо.


1 (обратно к тексту) - Google - не единственная поисковая система, у которой «ноги растут» из Стэнфорда: Yahoo и Excite тоже созданы выпускниками этого университета.
2 (обратно к тексту) - Если говорить о распределении поисковых систем по объему проиндексированной информации, то Google- впереди планеты всей с большим отрывом- 1,25 млрд. страниц. Altavista и Excite - по 250 миллионов, Northern Light - 200 млн., HotBot - 110 млн., Lycos - 50 млн.
3 (обратно к тексту) - Для сравнения: «Яндекс», один из лучших российских поисковиков, базируется на тридцати серверах. Подробнее об устройстве «Яндекса» см. company.yandex.ru/programs/web_200203.html.
4 (обратно к тексту) - UrlServer, как и «веб-пауки», написан на Python, а большинство прочих компонентов Google - на С и С++.

Поиск

Что происходит после того, как пользователь набрал целевые слова и нажал кнопку поиска? Упрощенно процесс делится на следующие этапы:

  1. Разбор запроса.
  2. Нахождение идентификаторов wordID для всех слов в запросе.
  3. Генерация сокращенного списка документов, в которых есть указанные слова.
  4. Сканирование списка, продолжающееся до тех пор, пока не находится документ, полностью удовлетворяющий условиям поиска.
  5. Вычисление ранга документа.
  6. Если достигнут конец сокращенного списка, осуществляется генерация полного списка и возврат к шагу 4.
  7. Если конец списка документов не достигнут, снова осуществляется переход к этапу 4.
  8. Сортировка списка документов по рангу и выдача пользователю первых N документов (где N - число результатов, которые пользователь может указать на вкладке Advanced).

Вычисление PageRank

Рассмотрим некую страницу А.

Имеется n страниц (T1, Т2, …, Tn), цитирующих данный документ. Фактор затухания d (damping factor) - это вероятность того, что пользователь, просматривая страницу, перейдет на следующую страницу не по ссылке, а набрав случайный URL. Он может колебаться в пределах от 0 до 1, но обычно устанавливается в значение 0,85. Тогда вероятность перехода по ссылке будет 1-d.

C(A) - общее число ссылок со страницы А на другие документы.

Тогда индекс PageRank PR(A) для страницы А равен:

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

Несмотря на громоздкость функции, индекс легко подсчитывается простым итерационным алгоритмом. К примеру, для 30 миллионов страниц его подсчет на рабочей станции средней руки займет всего несколько часов.

© ООО "Компьютерра-Онлайн", 1997-2022
При цитировании и использовании любых материалов ссылка на "Компьютерру" обязательна.