Кому нужна математика? Понятная книга о том, как устроен цифровой мир (Литвак, Райгородский) - страница 59

Филипп Флажоле и соавторы предложили новый метод подсчета под названием HyperLogLog.

LogLog означает, что по сравнению с числом объектов нам нужно очень маленькое количество оперативной памяти. Под LogLog здесь понимают двойной логарифм по основанию 2, и это на самом деле очень маленькое число. Например, при миллиарде объектов двойной логарифм будет

log_>2(log_>2(1000 000 000)) ≈ 4,9,

то есть порядка 5 битов памяти – всего пять нулей и единиц!

Приставка Hyper использована тоже не просто так. Идею подобного метода Флажоле предлагал и раньше, но предыдущие версии давали слишком грубые результаты.

Метод HyperLogLog сильно улучшил точность, что позволило применить его на практике.

Как и в методе К-Minimum Values, Флажоле исходил из предположения, что записи в базе данных можно представить в виде разбросанных случайным образом чисел. На практике это действительно так, потому что каждой записи, будь то число, имя, адрес или название, присваивается так называемое хеш-значение. Это последовательность из нулей и единиц одинаковой небольшой длины. Если две записи совпадают (например, одно и то же название повторяется два раза), то и их хеш-значения совпадают. Например, хеш-значения длины 8 для разных веб-магазинов могут выглядеть примерно как в табл. 7.1. Мы выделили жирным шрифтом название, которое повторяется два раза:

Таблица 7.1. Фиктивный пример хеш-значений веб-магазинов

На практике обычно применяют хеш-значения длины 32 или 64. Хеш-значения генерируются с помощью специальных программ, так называемых хеш-функций, весьма нетривиальным образом. Усмотреть связь между изначальной записью и ее хеш-значением фактически невозможно. Поэтому можно считать, что хеш-значения присваиваются случайным образом. И метод К-Minimum Values, и метод Флажоле пользуются не самими записями, а их хеш-значениями.

Напомним, что по методу К-Minimum Values нужно запомнить несколько самых маленьких хеш-значений. Флажоле пошел еще дальше, предложив запоминать только число нулей в начале хеш-значения.

Для примера опять возьмем хеш-значения длины 8. Допустим, нам попалось хеш-значение

00001011

Последовательности, у которых в начале ровно четыре нуля, встречаются не очень часто, в среднем одна на 32. Если мы наткнулись на такую последовательность, то можно предположить, что в среднем мы видели 32 разных хеш-значения, то есть число объектов – примерно 32. Что, если мы видели еще больше нулей, скажем пять?

00000101

Такие последовательности еще более редки, одна на 64, то есть объектов примерно 64! Разве не гениально?