Поисковая система Google
В настоящее время поисковая система Google стала одним из основных инструментов поиска в интернете, и у нее огромное количество пользователей. Одной из причин такого успеха является ее эффективность, так как для каждого поискового запроса система быстро выдает упорядоченный список результатов, и первые из них, как правило, содержат то, что мы ищем. Способ упорядочивания результатов поиска, то есть присвоения числового рейтинга каждой странице, использует сложную математику — смесь линейной алгебры, теории графов и теории вероятностей.
При разработке поисковых систем, подобных системе Google, приходится решать и математические, и технические задачи. Другими словами, главный вопрос заключается в том, как упорядочить результаты поиска. Можно предположить, что рейтинг определенной веб-страницы зависит от количества других страниц, ссылающихся на нее. Однако существуют страницы, на которые мало ссылок, но которые очень важны для данного поиска. Поэтому такая модель невыгодна для пользователей. К тому же она может быть легко использована веб-сайтами для искусственного повышения рейтинга.
Создатели Google Сергей Брин и Ларри Пейдж разработали алгоритм для определения рейтинга страницы не по количеству ссылок на нее, а пропорционально важности этой страницы для данного поиска. Этот алгоритм требует решения системы алгебраических уравнений. Фактически задача сводится к линейной алгебре, а именно к вычислению собственных векторов и собственных значений некой матрицы. Если обозначить важность веб-страниц в интернете набором чисел (x1, …., xn), где n — число страниц, существующих в интернете, а хi — число, означающее важность конкретной веб-страницы i, то задача сводится к поиску в n-мерном пространстве элемента (x1, …., xn), который является решением некой системы уравнений.
В 2006 г. было подсчитано, что в интернете существует около 600 миллиардов веб-страниц. Это число и соответствует числу измерений рассматриваемого пространства. Такое пространство, безусловно, является многомерным!
* * *
АЛГОРИТМ, КОТОРЫЙ ИЗМЕНИЛ ИНТЕРНЕТ
В 1998 г. два молодых студента-информатика Стэнфордского университета в Калифорнии Ларри Пейдж и Сергей Брин заканчивали исследовательский проекте несколько загадочным названием «Анатомия системы крупномасштабного гипертекстного интернет-поиска». Он содержал первую версию простого и элегантного алгоритма PageRank, используемого для упорядочивания списка
страниц в зависимости от их значимости. PageRank стал основой поисковой системы Google, которая через несколько лет обошла Yahoo, Altavista и многие другие поисковые системы. Поиск в Google даже стал синонимом поиска в интернете (слово «гуглить»» еще не вошло в словари, но активно употребляется в разговорной речи).
Алгоритм PageRank действительно элегантен и прост и может быть записан следующим образом:
где Wj — рейтинг страницы j; Wi — рейтинг страницы i, которая содержит ссылку на страницу j; число d — коэффициент затухания со значением между 0 и 1, необходимый для сходимости рядов; ni, — число ссылок на странице Wi, на другие страницы; N — общее количество страниц, которые содержат ссылку на страницу j.
Рейтинг любой страницы является суммой рейтингов всех страниц, которые ссылаются на нее, с весовым коэффициентом, зависящим от общего числа ссылок на каждой.
Глава 3. Революция в геометрии XIX века
Геометрические аксиомы не являются экспериментальными данными. Лишь наблюдение физических явлений определяет выбор гипотез среди всех возможных. Тот или иной выбор может быть только более удобным, чем другие возможные.
Поэтому вопрос, какая геометрия истинна — Лобачевского или евклидова, — не имеет смысла. Это все равно что спрашивать, какие координаты вернее — декартовы или полярные.