Идея очень простая. Чем больше нулей, тем реже встречаются такие хеш-значения. Если какому-то объекту случайно досталось очень редкое хеш-значение, значит, объектов было много.
Запомнить при этом нужно только одно число – самое большое количество нулей, которое мы видели, например 4. Для этого достаточно минимального объема памяти. Если нам попалось хеш-значение, у которого нулей больше, например 5, мы выкидываем из памяти 4 и запоминаем 5[22].
Очевидно, что этот метод очень приблизительный. Например, хеш-значение с четырьмя нулями нам могло встретиться и в самом начале. Столь грубые оценки для практики не годятся.
В HyperLogLog для улучшения точности добавлено много хитрых приемов. Хеш-значения разбиваются на регистры, оценка считается в каждом регистре отдельно, а потом усредняется специальным образом. Кроме этого, учитывается коррекция, когда объектов очень мало или, наоборот, очень много. Подробно об этом можно прочитать в блоге{23}. Там можно даже запустить программу и посмотреть, как метод работает.
На практике стараются достичь еще более высокой точности. Собственно, об этом статья сотрудников Google{24}, о которой мы упоминали выше. Она так и называется «HyperLogLog на практике». Например, авторы уделили особое внимание коррекции при маленьком числе объектов. Грубо говоря, если клиент в состоянии посчитать объекты вручную, то и компьютер должен давать абсолютно правильный ответ.
Так грубая, почти нахальная оценка Флажоле привела к решению задачи подсчета, решению с оптимальным балансом между эффективностью и точностью.
Четыре виртуальных рукопожатия
Помимо того что задача подсчета важна сама по себе, она находит и другие, совершенно неожиданные применения.
Все мы знаем, что мир тесен. Знакомишься с человеком, и тут же находятся общие знакомые или хотя бы знакомые знакомых. Многих исследователей интересовал вопрос, насколько тесен виртуальный мир социальных сетей.
Вопросы подобного рода имеют длинную историю. В конце 1960-х годов социолог Стэнли Милграм провел свой знаменитый эксперимент. Он раздал случайным людям в штатах Небраска и Канзас письма, адресованные брокеру из Бостона. Географически и по роду занятий эти люди были достаточно далеки от адресата. По правилам эксперимента, участники могли переслать письма только своим знакомым, которые должны были передать их дальше, своим знакомым, и так далее, пока они в конце концов не достигнут адресата. Из 296 писем большинство затерялось в дороге, но 64 письма дошли-таки по назначению. При этом оказалось, что цепочка, связывающая совершенно незнакомых людей, на удивление короткая. В среднем отправителя и адресата разделяло всего 5 человек! На рис. 7.1 мы схематически изобразили, как письмо пересылалось всего шесть раз, через пять промежуточных человек.