Предположим, у вас есть очень большой набор данных — слишком большой для хранения в памяти — с повторяющимися записями. Вы хотите знать, сколько дублирующих записей, но ваши данные не отсортированы, и они достаточно велики, чтобы сортировка и подсчет были непрактичными. Как вы оцениваете, сколько уникальных записей содержится в наборе данных? Легко понять, как это может быть полезно во многих приложениях, например при планировании запросов в базе данных: лучший план запроса может сильно зависеть не только от общего количества значений, но и от количества уникальных значений.
Я бы посоветовал вам немного подумать, прежде чем читать дальше, потому что алгоритмы, которые мы обсудим сегодня, довольно новаторские — и хотя они простые, они далеко не очевидны.
Простая и интуитивно понятная оценка мощности
Давайте начнем прямо с простого примера. Предположим, кто-то сгенерировал набор данных с помощью следующей процедуры:
- Генерация
nравномерно распределенных случайных чисел - Произвольно копировать некоторые из этих чисел неопределенное количество раз
- Перемешать полученный набор чисел произвольно
Как мы можем оценить количество уникальных чисел в результирующем наборе данных? Зная, что исходный набор чисел был случайным и равномерно распределенным, возникает одна очень простая возможность: просто найти наименьшее число в наборе. Если максимально возможное значение равно mнаименьшему значению, которое мы находим x, мы можем оценить, что m/x в общем наборе будут уникальные значения. Например, если мы просканируем набор данных с номерами от 0 до 1 и обнаружим, что наименьшее значение в наборе равно 0,01, разумно предположить, что в наборе приблизительно 100 уникальных значений; больше, и мы ожидаем увидеть меньшее минимальное значение. Обратите внимание, что не имеет значения, сколько раз каждое значение повторяется: характер агрегатов таков, min что повторения не влияют на выходное значение.
Эта процедура имеет то преимущество, что она чрезвычайно проста, но она также очень неточна. Нетрудно представить набор только с несколькими различными значениями, содержащими необычно небольшое число; аналогично, множество с множеством различных значений может иметь наименьшее значение, большее, чем мы ожидаем. Наконец, немногие наборы данных ведут себя так хорошо, чтобы быть аккуратно случайными и равномерно распределенными. Тем не менее, этот протоалгоритм дает нам некоторое представление об одном возможном подходе, чтобы получить то, что мы хотим; нам нужны дальнейшие доработки.
Вероятностный подсчет
Первый набор уточнений взят из статьи « Алгоритмы вероятностного подсчета для приложений баз данных » Флайолета и Мартина, с дополнительными уточнениями в статьях « Подсчет большого количества элементов LogLog» по Дюрану-Флажоле и HyperLogLog: анализ почти оптимального алгоритма оценки мощности Flajolet et al. Интересно наблюдать за развитием и совершенствованием идей от бумаги к бумаге, но я собираюсь использовать немного другой подход и продемонстрировать, как построить и улучшить решение с нуля, не используя некоторые алгоритмы из оригинальной статьи. , Заинтересованным читателям рекомендуется прочитать все три; они содержат много математических идей, о которых я не буду здесь подробно рассказывать.
Во-первых, Flajolet и Martin отмечают, что при наличии хорошей хеш-функции мы можем взять любой произвольный набор данных и превратить его в один из необходимых нам типов с равномерно распределенными (псевдо) случайными значениями. С этим простым пониманием мы можем применить нашу предыдущую процедуру к любым данным, которые мы хотим, но они еще далеко не сделаны.
Затем они отмечают, что существуют другие шаблоны, которые мы можем использовать для оценки количества уникальных значений, и некоторые из них работают лучше, чем запись минимального значения хэшированных элементов. Метрика Flajolet и Martin выбирает количество 0 битов в начале хешированных значений. Легко видеть, что в случайных данных последовательность k нулевых битов будет встречаться один раз в каждом 2k элементы в среднем; все, что нам нужно сделать, это найти эти последовательности и записать длину самой длинной последовательности, чтобы оценить общее количество уникальных элементов. Это все еще не очень хорошая оценка, хотя — в лучшем случае это может дать нам степень оценки числа элементов в два раза, и, как и оценка, основанная на минимальном значении, она будет иметь огромное расхождение. С другой стороны, наша оценка очень мала: для записи последовательностей, ведущих от 0 до 32 бит, нам нужно только 5-битное число.
В качестве примечания следует отметить, что оригинальная статья Flajolet-Martin отклоняется здесь и использует процедуру на основе растрового изображения, чтобы получить более точную оценку из одного значения. Я не буду вдаваться в подробности, так как это скоро устарело из-за улучшений в последующих статьях; заинтересованные читатели могут прочитать оригинал статьи для более подробной информации.
Таким образом, теперь у нас есть довольно плохая оценка количества значений в наборе данных на основе битовых комбинаций. Как мы можем улучшить это? Одна простая идея — использовать несколько независимых хеш-функций. Если каждый хеш производит свой собственный набор случайных выходов, мы можем записать самую длинную наблюдаемую последовательность ведущих нулей из каждого; в конце мы можем усреднить наши значения для более точной оценки.
На самом деле это дает нам довольно хороший результат, если говорить статистически, но хеширование обходится дорого. Лучший подход известен как стохастическое усреднение . Вместо того, чтобы использовать несколько хеш-функций, мы используем только одну хеш-функцию, но используем часть ее вывода для разделения значений в одно из множества сегментов. Предположим, что мы хотим получить 1024 значения, мы можем взять первые 10 битов хеш-функции в качестве номера сегмента и использовать оставшуюся часть хеша для подсчета ведущих нулей. Это ничего не теряет в плане точности, но спасает нас от избыточного вычисления хэшей.
Применяя то, что мы узнали до сих пор, вот простая реализация. Это эквивалентно алгоритму LogLog в статье Durand-Flajolet; однако для удобства и ясности я считаю, что конечные (наименее значимые) 0 битов, а не лидирующие; результат в точности эквивалентен.
def trailing_zeroes(num):
"""Counts the number of trailing 0 bits in num."""
if num ==0:
return32# Assumes 32 bit integer inputs!
p =0
while(num >> p)&1==0:
p +=1
return pdef estimate_cardinality(values, k):
"""Estimates the number of unique elements in the input set values.
Arguments:
values: An iterator of hashable elements to estimate the cardinality of.
k: The number of bits of hash to use as a bucket number; there will be 2**k buckets.
"""
num_buckets =2** k
max_zeroes =[0]* num_buckets
for value in values:
h = hash(value)
bucket = h &(num_buckets -1)# Mask out the k least significant bits as bucket ID
bucket_hash = h >> k
max_zeroes[bucket]= max(max_zeroes[bucket], trailing_zeroes(bucket_hash))
return2**(float(sum(max_zeroes))/ num_buckets)* num_buckets *0.79402
Это все в значительной степени, как мы только что описали: мы сохраняем кучу подсчетов количества ведущих (или конечных) нулей; в конце мы усредняем количество; если наше среднее значение равно x, наша оценка равна 2 x , умноженному на количество сегментов. Ранее не упоминалось это магическое число 0.79402. Статистический анализ показывает, что наша процедура вносит предсказуемый уклон в сторону больших оценок; эта магическая константа выведена в статье Дюраном-Флажоле, чтобы исправить это смещение. Фактическая цифра зависит от количества используемых сегментов, но при большем количестве сегментов (не менее 64) она сходится к оценке, которую мы используем в приведенном выше алгоритме. Смотрите полную бумага для партий больше информации, в том числе при выводе этого числа.
Эта процедура дает нам довольно хорошую оценку — для m сегментов средняя ошибка составляет около 1.3/sqrt(m). Таким образом, с 1024 сегментами (для 1024 * 5 = 5120 бит или 640 байт) мы можем ожидать среднюю ошибку около 4%; 5 битов на ведро достаточно для оценки мощности до 2 27 на бумагу). Это очень хорошо для менее чем килобайта памяти!
Давайте попробуем сами на некоторых случайных данных:
>>>[100000/estimate_cardinality([random.random()for i in range(100000)],10)for j in range(10)][0.9825616152548807,0.9905752876839672,0.979241749110407,1.050662616357679,0.937090578752079,0.9878968276629505,0.9812323203117748,1.0456960262467019,0.9415413413873975,0.9608567203911741]
Неплохо! Некоторые из оценок более чем прогнозируются на 4%, но в целом они довольно хороши. Если вы сами пытаетесь hash() провести этот эксперимент, одно предостережение: встроенные в Python хэшируют целые числа. В результате, выполнение чего-то подобного estimate_cardinality(range(10000), 10) даст очень разные результаты, потому что hash() не ведет себя так, как должна делать хорошая хеш-функция. Однако использование случайных чисел, как в примере выше, работает очень хорошо.
Повышение точности: SuperLogLog и HyperLogLog
Хотя у нас есть оценка, которая уже довольно хороша, возможно, станет намного лучше. Дюран и Флажоле отмечают, что отдаленные значения сильно влияют на точность оценки; выбрасывая самые большие значения перед усреднением, точность может быть улучшена. В частности, выбрасывая 30% сегментов с наибольшими значениями и усредняя только 70% сегментов с меньшими значениями, можно повысить точность от 1.30/sqrt(m) всего до 1.05/sqrt(m)! Это означает, что наш предыдущий пример с состоянием 640 байт и средней ошибкой 4% теперь имеет среднюю ошибку около 3,2% без дополнительного увеличения требуемого пространства.
Наконец, основной вклад Flajolet et al. В статью HyperLogLog заключается в использовании другого типа усреднения, принимая среднее гармоническое значение вместо только что примененного геометрического среднего. Делая это, они могут уменьшить ошибку 1.04/sqrt(m), опять же, без необходимости увеличения состояния. Однако полный алгоритм несколько сложнее, так как требует поправок для малых и больших мощностей. Заинтересованные читатели должны — как вы уже догадались — прочитать всю статью для деталей.
Распараллеливание
Один действительно замечательный атрибут, который разделяют все эти схемы, заключается в том, что их очень легко распараллелить. Несколько машин могут независимо запускать алгоритм с одной и той же хэш-функцией и одинаковым количеством блоков; в конечном итоге результаты можно объединить, взяв максимальное значение каждого сегмента из каждого экземпляра алгоритма. Это не только тривиально, но итоговая оценка в точности совпадает с результатом, который мы получили бы на одной машине, в то время как для достижения этой цели нам потребовалось всего лишь передать менее килобайта данных на экземпляр.
Вывод
Алгоритмы оценки мощности, подобные тем, которые мы только что обсуждали, позволяют получить очень хорошую оценку — в пределах нескольких процентов — от общего числа уникальных значений в наборе данных, обычно используя менее килобайта состояния. Мы можем сделать это независимо от характера данных, и работа может быть распределена по нескольким машинам с минимальными издержками координации и передачи данных. Полученные оценки могут быть полезны для ряда вещей, таких как мониторинг трафика (сколько уникальных IP-адресов связывается с хостом?) И оптимизация запросов к базе данных (следует ли сортировать и объединять или создавать хеш-таблицу уникальных значений?).
Есть алгоритм, который вы думаете, Черт Круто? Отправьте это в комментариях, и возможно я напишу об этом в будущем сообщении!