Если в битовой схеме хеша есть k число начальных нулей, почему размер оценки считается равным 2 k + 1? не должно быть 2 k? вероятность того, K ведущие нули должны быть 1/(2 к) и, следовательно, размер должен быть 2 KПочему 1 добавлено к первому счету нуля в алгоритме гиперлогового журнала
В моем коде я всегда получаю правильную оценку размера, когда я использую K + 1 вместо к , Но я не понимаю логики этого.
Интуиция, которую вы ищете, заключается в том, что алгоритм полагается на вероятность увидеть весь бит-шаблон в начале хэша (k нулей, за которым следует 1), а не только нули.
Более сложная часть находится оттуда, чтобы оценить мощность на 2 k + 1. К сожалению, официальное доказательство этого не является простым. Фактически, большая часть оригинальной оригинальной статьи, введёвшей метод (Flajolet and Martin, Probabilistic counting Algorithms для приложений базы данных, http://algo.inria.fr/flajolet/Publications/FlMa85.pdf), посвящена доказательству того, что вычисленная с ней оценка является хорошей. Последующие документы (документы LogLog и HyperLogLog) имеют аналогичные доказательства для их улучшенных оценок.
Надеюсь, что это поможет!
Согласно теории вероятности, вы правы! Вы ожидали бы, что сделаете 2 наблюдения за наблюдением (0), прежде чем наблюдаете значение с k начальными нулями.
Причина, по которой ваша оценка удваивается, может быть потому, что ваша случайная функция (или функция хеширования) возвращает подписанный int, который всегда положителен, и всегда присутствует нулевой фронт. Это должно примерно удвоить ваши шансы увидеть значение с k начальными нулями. Вот почему вы получите правильный ответ, когда используете 2 k + 1 вместо 2 k.
k Ведущие нули означают, что первые k бит являются нулями, за которыми следует один бит. (В противном случае у нас было бы больше k ведущих нулевых битов.) Поэтому k ведущих нулей на самом деле характеризуется битовой последовательностью длины (k + 1), для которой вероятность равна 1/2^(k + 1).