Небольшая предыстория. Этот пост я написал для двух целей. Во-первых, обкатать конвертор разметки Markdown + в хабрачитаемый вид. Во-вторых, рассказать об интересной задаче из data streaming. К концу написания, я обнаружил пост про LogLog четырехлетней давности. На мою удачу автор предыдущего поста делал упор на реализацию. Я же, полагаясь на , расскажу больше о математике.

Давайте представим, что у нас есть роутер. Через роутер проходит много пакетов по разным адресам. Нам интересно получить статистику, как много адресов задействовано в коммуникации. Есть пара проблем.

• Пакетов так много, что запомнить их все нельзя. Сказать ушедшему пакету «Вернись! Я все прощу,» — тоже.
• Всех возможных адресов . Столько памяти на роутере нет.

Задача. Есть последовательность целых чисел , все числа принимают значения от до . Требуется в один проход посчитать количество различных чисел, используя памяти.

Я расскажу вероятностный приближенный алгоритм Флажолета-Мартина. ТТХ алгоритма:

• использует памяти!
• работает на любом входе;
• находит ответ, который отличается от точного не более чем в 3 раза с вероятностью :
  
  
  
  
  вероятность берется по случайным битам алгоритма.

В конце поста я расскажу, почему точные детерминированные алгоритмы требуют памяти.

Алгоритм Флажолета-Мартина

Представим, что у нас есть отрезок действительных чисел . На отрезок мы независимо случайно кидаем точек согласно равномерному распределению. Какое будет расстояние между крайней левой точкой и нулем?

Можно предположить, что точки разделят отрезок на меньших подотрезков примерно одинаковой длины. Если аккуратно записать матожидание расстояния и взять интеграл, мы получим


Пусть кто-то кинул случайно несколько точек на отрезок, и — расстояние от нуля до крайней левой точки. Можно прикинуть, что всего точек порядка .

Идея алгоритма Флажолета-Мартина — случайно бросить все числа последовательности на отрезок , а затем найти расстояние от нуля до крайней левой точки. Если одинаковые числа будут всегда отображаться в одну точку, а разные независимо распределяться по отрезку, мы сможем прикинуть ответ.

2-независимые хэш-функции

Бросать числа на отрезок мы будем с помощью случайной хэш-функции.

Определение. Семейство хэш-функций называется 2-независимым, если для любых и


Смысл определения в следующем. Зафиксируем два каких угодно ключа и .
Ключи — различные. Посмотрим на случайные величины и . Случайность задается выбором функции . Тогда, по определению, величины и будут вести себя как независимые.

Как следствие, если взять всего один ключ , то величина будет равномерна распределена по .

Для примера возьмем простое число . Пусть . — это семейство всех линейных отображений по модулю :


для . Тогда


Поскольку , система имеет ровно одно решение среди возможных:


Поймем два важных момента. Во-первых, хранение такой функции обходится в памяти, что очень немного. Во-вторых, если внимательно приглядеться, то можно понять, что вычисления проходят в поле , и могут быть обобщены для любого конечного поля.

В тестовом коде я буду использовать поле Галуа . В описании далее можно считать, что у нас есть семейство хэш-функций , где — степень двойки. Хранение одной функции занимает памяти.

Алгоритм

Пусть — степень двойки.
Перед стартом, алгоритм случайно выбирает хэш-функцию из 2-независимого семейства.

Будем бросать элементы последовательности на отрезок . Берем очередное значение и записываем: ноль, точка, в двоичном виде. Например, если , то получится число .

Обозначим через число лидирующих нулей в двоичной записи . Пусть . Мы знаем, что минимальное значение лежит между и .

Ответ алгоритма: .

def init():
	h = H.sample()
	z = 0
	
def process(a):
	z = max(z, zero(h(a))
	
def answer():
	return 2**(z + 0.5)

Анализ

Я планирую показать, что ответ алгоритма будет в 3 раза больше верного с вероятностью меньшей . Аналогично, алгоритм вернет ответ в 3 раза меньше верного вероятностью меньшей . Если вы не планируете углубляться в математику, смело переходите к следующей части.

Обозначим через множество всех различных чисел последовательности , а — их количество.

Для анализа алгоритма, нам потребуются два набора случайных величин.

• . Принимает значение 1, если количество лидирующих нулей в двоичной записи хотя бы ; иначе — .
• . Величина больше нуля, если переменная по завершении алгоритма оказалась не меньше .

Заметим, что вероятность : величина равномерно распределена по отрезку ; — степень двойки; есть всего чисел с лидирующими нулями.

Значит, матожидание . Ограничим сверху дисперсию


Заметим, что дисперсия по величинам линейна. Для любых двух и




Поскольку и независимы, то . Значит,


Более того, , поскольку величины — 2-независимы.

Теперь рассмотрим величину .

• по линейности матожидания.
• по линейности дисперсии для 2-независимых величин.

Пусть — минимальное число такое, что . Событие «алгоритм выдал ответ в 3 раза больше нужного» равносильно событию и равносильно событию . Применяя неравенство Маркова, ограничим вероятность


Пусть — максимальное число такое, что . Аналогично, событие «алгоритм выдал ответ в 3 раза меньше нужного» равносильно событию и равносильно событию . Применяя неравенство Чебышёва, получим

Финальный аккорд: медиана

Осталось понять как понизить ошибку. Возьмем случай, когда алгоритм выдает слишком большой ответ. Запустим алгоритм параллельно раз и вернем медиану среди ответов. Я утверждаю, что если , то алгоритм ошибется с вероятностью не больше . Аналогично, ограничив ошибку в другую сторону, получим


Почему медиана так работает? По неравенству Чернова. Заведем случайную величину . Величина равна единице, если ответ алгоритма на запуске меньше . Вероятность этого события не меньше 0.52.

Если медиана запусков алгоритма больше , то это значит, что алгоритм хотя бы половину раз выдал ответ больший и . Тогда по неравенству Хефдинга-Чернова


где — некоторая константа. Другой случай показывается аналогично.

Нижняя оценка для точного алгоритма

Давайте представим, что кто-то действительно придумал детерминированный алгоритм, который в один проход находит точное число различных элементов в один проход. Мы покажем, что такой алгоритм должен использовать памяти.

Возьмем множество размера и положим его в качестве начала последовательности. Скормим эту часть алгоритму и посмотрим на его память.

Из одной только памяти алгоритма можно извлечь все множество . Если скормить в текущем состоянии число , ответ алгоритма не изменится; если , то увеличится на 1. Значит, каждому множеству должно соответствовать свое уникальное состояние памяти.

Различных подмножеств из размера примерно . Если мы хотим каждому множеству сопоставить битовую строку, нам потребуется

Что почитать

1. «Probabilistic Counting Algorithms for Data Base Applications», Flajolet, Martin, 1983, link.
2. «The space complexity of approximating the frequency moments», Alon, Matias, Szegedy, 1999, link.