Алгоритм поиска Google

Мы рассматриваем алгоритм работы поисковой системы Google не в качестве рекламы (работает она с известными промашками и ограничениями), а сугубо в качестве примера нестандартно организованной поисковой системы.

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

PageRank — один из алгоритмов ранжирования по внешним ссылкам. Алгоритм применяется к коллекции документов, связанных гиперссылками, и назначает каждому из них некоторое численное значение (ранг), измеряющее его «важность» или «авторитетность» среди остальных документов. Вообще говоря, алгоритм может применяться не только к веб-страницам, но и к любому набору объектов, связанных между собой взаимными ссылками, т. е. к любому графу.

Порядок ранжирования в Google работает следующим образом. Сначала учитываются обычные текстовые критерии, такие как тэг Title и ключевые слова, а затем используется алгоритм PageRank для сортировки результатов таким образом, чтобы более «важные» сайты получали наибольший ранг и поднимались вверх на странице результатов поиска.

Главная задача заключается в том, чтобы найти критерий, выражающий важность страницы. В случае с PageRank таким критерием была выбрана теоретическая посещаемость страницы. Авторы исходили из того, что если страница Л ссылается на страницу В, то страница Л считает, что страница В — важная страница. Логично предположить, что документ, имеющий большее число качественных внешних ссылок, содержит наиболее ценную информацию.

Ранг R страницы Л рассчитывается по формуле.

где R (A) — ранг страницы Л; /?(7}) — ранг страницы T_it которая ссылается на страницу Л; C (Tj) — количество исходящих ссылок на странице 7}; г/ — демпфирующий фактор, который может иметь значение от 0 до 1 (коэффициент «затухания» передающегося ранга).

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