Изменения

При использовании <tex>m</tex> единиц дополнительной памяти алгоритм '''HyperLogLog''' оценивает количество различных элементов со стандартной ошибкой около <tex>\frac{1.04}{\sqrt{2^rm}}</tex>. Также этот алгоритм способен оценивать значения, превышающие 10⁹, используя 1.5 kB памяти для получения ответа с точностью 2%.

В основе алгоритма {{Определение|definition=Обозначим за '''HyperLogLogмощность''' лежит наблюдение, что мощность набора равномерно распределенных случайных чисел можно оценить, вычислив максимальное количество ведущих нулей в двоичном представлении каждого числа в наборе. Таким образом, если максимальное наблюдаемое количество начальных нулей равно <tex>n</tex>, то оценка количества различных элементов в наборе будет <tex>2^n</tex>нём.}}

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

Суть алгоритма заключается в следующем: к каждому элементу исходного набора применяется [[wikipedia:ru:Хеш-функция|хеш-функция]] для получения набора равномерно распределенных случайных чисел с той же мощностью, что и исходный набор. Затем мощность этого случайно распределенного набора оценивается с помощью описанного выше алгоритма. Но при таком подходе могут возникать различные проблемы за счёт большой [[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> \sum\limits_{j=0}^{2^{r - 1}} 2^{z_j} </tex>, но такой подход приводит не к самому выгодному результату. Выгоднее всего будет пересчитывать результат при помощи среднего гармонического всех полученных оценок:<tex>E \approx \alpha \cdot (2^r)^2 \cdot I</tex>

<tex>E I</tex> {{---}} это индикатор, вычисляемый по формуле <tex>I = (\approx sum\alpha limits_{j=0}^{2^{r - 1}} \cdot (frac{1}{2^r{z_j}})^2 \cdot I{-1} </tex>

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

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

Поскольку множитель <tex> \alpha</tex> может быть достаточно сложным для вычисления, можно подобрать его примерное значение в зависимости от <tex>alpha_{r}\approx\begin{cases} r=4 & 0.673\\ r=5 & 0.697\\ r=6 & 0.709\\ r\ge7 & \frac{0.7213}{1+\frac{1.079}{2^r}} \end{cases} </tex>:

:Число <tex>\alpha_{r}\approx\begin{cases}r=4 & 0.673\\r=5 & 0.697\\r=6 & 0.709\\r\ge7 & \frac{0.7213}{1+\frac{1.079}{2^r}}\end{cases}E</tex>и будет итоговой оценкой мощности данного набора.

==ДоказательствоПлан доказательства==

'''Идеальным мультимножеством''' с количеством различных элементов мощностью <tex>n</tex> называется последовательность, полученная произвольными повторениями и перестановками, применяемыми к <tex>n</tex> равномерно распределенным случайным величинам на действительном интервале [0, 1].

Пусть алгоритм '''HyperLogLog''' применяется к идеальному мультимножеству, содержащему мощностью <tex>n</tex> различных элементов (число <tex>n</tex> нам неизвестно), используя <tex>reg = 2^r</tex> корзин, и пусть <tex>E</tex> {{---}} полученная результирующая оценка количества различных элементов в этом мультимножестве.

Оценка дополнительной памяти: <tex>2^r \cdot log_2mathcal{O}(k) = 2^r \cdot log_2 log_2 m </tex>, где <tex>mn) </tex> {{---}} количество возможных значений хэш-функции.

Полученное при помощи алгоритма '''HyperLogLog ''' значение <tex>E</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>. Это может быть полезным при больших <tex>n</tex>, близких к (в нашем примере) 2^{32}, когда вероятность коллизии при хешировании становится довольно высокой.