Page 266 - Bkhargava_-_Grokaem_algoritmy

Hyperloglog 265

Вот только этот хеш получится просто огромным. Google индексирует трил­
лионы веб-страниц. Если хеш содержит все URL-aдpeca, индексируемые
Google, он займет слишком много места. У Reddit и Ьit.ly возникает ана­
логичная проблема. Сталкиваясь с такими объемами данных, приходится
действовать более изобретательно!

Фильтры Блума

Для решения проблемы можно воспользоваться вероятностными струк­
турами данных, которые называются фильтрами Блума. Они дают ответ,
который может оказаться ложным, но с большой вероятностью является
правильным. Вместо того чтобы обращаться к хешу, вы спрашиваете
у фильтра Блума, обрабатывался ли этот URL-aдpec ранее. Хеш-таблица
даст точный ответ. Фильтр Блума дает ответ, правильный с высокой ве­
роятностью:

c:J возможны ложно-положительные срабатывания. Фильтр скажет: ~этот
сайт уже обрабатывался», хотя этого не было;

c:J ложно-отрицательные срабатывания исключены. Если фильтр утверж-
дает, что сайт не обрабатывался, вы можете быть в этом уверены.

Фильтры Блума хороши тем, что занимают очень мало места. Хеш-таблице
пришлось бы хранить все URL-aдpeca, обрабатываемые Google, а фильтру
Блума это не нужно. Фильтры Блума очень удобны тогда, когда не нужно
хранить точный ответ (как во всех приведенных примерах). Например,
Ьit.ly может сказать: ~Мы полагаем, что сайт может оказаться вредоносным,
будьте особенно внимательны».

HyperLog Log

Примерно так же действует другой алгоритм, который называется
HyperLogLog. Предположим, Google хочет подсчитать количество уникалъ­
НЪLХ поисков, выполненных пользователями. Или Amazon хочет подсчитать
количество уникальных предметов, просмотренных пользователями за
сегодняшний день. Для получения ответов на эти вопросы потребуется
очень много места! Так, в примере с Google придется вести журнал всех
уникальных вариантов поиска. Когда пользователь что-то ищет, вы сначала

www.trk.kg