Изменения

В основе алгоритма '''HyperLogLog''' лежит наблюдение, что мощность набора [[wikipedia:ru:Равномерное_распределение|равномерно распределенных]] на заданном интервале <tex>[0, m-1]</tex> случайных чисел можно оценить, вычислив максимальное количество ведущих нулей в двоичном представлении каждого числа в наборе. Таким образом, если максимальное наблюдаемое количество начальных нулей равно <tex>n</tex>, то оценка количества различных элементов в наборе будет <tex>2^n</tex>.

Но при таком подходе могут возникать различные проблемы за счёт большой [[wikipedia:ru:Дисперсия_случайной_величины|дисперсии]] получаемой величины, а также некоторых крайних случаев: к примеру, если хэш хеш некоторого элемента будет равен <tex>0</tex>, то максимальное количество ведущих нулей сразу станет равным <tex>\log_2{m}</tex>, где <tex>m</tex> {{---}} максимальное значение выбранной хэшхеш-функции. Чтобы избежать подобных проблем и минимизировать дисперсию, модифицируем алгоритм следующим образом: разделим исходный поток элементов на <tex>2^r</tex> корзин, для каждой из них вычислим максимальное наблюдаемое количество начальных нулей среди элементов в этой корзине, а затем на основе полученных для всех корзин значений вычислим итоговый ответ на задачу.

* <tex>h : \mathcal{U} \to {0, 1 ... 2^k-1}</tex> {{---}} выбранная хэшхеш-функция с возможными значениями от <tex>0</tex> до <tex>m-1</tex>, <tex>k = \log_2{m}</tex>.

* <tex>r</tex> {{---}} количество бит исходного хэшахеша, характеризующих номер корзины, в которую будет отправлен соответствующий элемент.

Разобьём исходный набор <tex>\mathcal{M}</tex> на наборы <tex>\mathcal{M}_0..\mathcal{M}_{2^r - 1}</tex> следующим образом: для каждого поступающего элемента <tex>a_i</tex> вычислим его хэш хеш <tex>h(a_i)</tex> и представим его в двоичном виде. Тогда первые <tex>r</tex> бит этого двоичного представления будут характеризовать номер корзины <tex>j</tex>, а оставшиеся биты сформируют остаточный хэш хеш <tex>h'(a_i)</tex>, который и будет использоваться для поиска максимального количества начальных нулей в корзине <tex>\mathcal{M}_j</tex>.

<tex>\alpha</tex> {{---}} корректирующий множитель, вычисляемый по формуле <tex>\alpha = (2^r \int\limits_{0}^{\infty} (\log_2{\frac{2 + u}{1 + u}})^{2^r} \,du )^{-1}</tex>.

reg\to\infty & \sqrt{3 \log(2) - 1} = 1.03896

Оценка дополнительной памяти: <tex>\mathcal{O}(2^r \cdot \log_2 \log_2 n) </tex>.

* При <tex>E \leq \frac{5}{2}2^r</tex> в оценке могут появляться нелинейные искажения, которые необходимо скорректировать. Вычислим количество <tex>z_j</tex> равных <tex>0</tex>, обозначим эту величину за <tex>V</tex>. Если <tex>V = 0</tex>, то уже полученное алгоритмом значение <tex>E</tex> в корректировке не нуждается, иначе оно должно быть вычислено по формуле <tex>E_{result} = 2^r \log(\frac{2^r}{V})</tex>.* В том случае, если значение <tex>E</tex> превосходит ограничение на размер <tex>z_j</tex>, возрастает вероятность коллизии при хешировании и итоговая оценка также должна быть скорректирована. Рассмотрим 32-битный случай: при <tex>E > \frac{2^{32}}{30}</tex> итоговое значение можно вычислить как <tex>E_{result} = -2^{32} \log(1 - \frac{E}{2^{32}})</tex>.