Метод Морриса

Метод Морриса — это алгоритм приближённого подсчёта количества уникальных элементов (кардинальности) в большом наборе данных, который использует минимальный объём памяти. Разработан в 1978 году французским учёным Робером Моррисом (Robert Morris) и представляет собой один из первых примеров вероятностного алгоритма в области обработки потоковых данных. Метод основан на наблюдении за случайными битами и позволяет оценить число различных элементов с фиксированной относительной погрешностью, не сохраняя сами элементы.

История

Алгоритм был предложен Робером Моррисом в 1978 году в статье «Counting Large Numbers of Events in Small Registers» (рус. «Подсчёт большого числа событий в малых регистрах»), опубликованной в журнале Communications of the ACM. Работа Морриса была мотивирована задачами сетевого мониторинга и анализа трафика, где объём данных часто превышал возможности оперативной памяти для точного хранения всех уникальных записей. В то время типичные компьютеры имели ограниченную память, и необходимость оценки количества уникальных IP-адресов или пакетов требовала компактных решений.

Метод Морриса стал предшественником целого класса вероятностных алгоритмов, таких как алгоритм Блума (Bloom filter) и HyperLogLog, которые используются для оценки кардинальности в современных системах баз данных, поисковых движках и аналитических платформах.

Основная идея

В отличие от точного подсчёта, требующего хранения всех уникальных элементов (например, в хеш-таблице), метод Морриса использует случайность для достижения компромисса между точностью и объёмом памяти. Алгоритм работает с одним регистром — целочисленным счётчиком, который хранит не само количество, а его логарифмическую оценку.

Принцип работы

Пусть требуется оценить количество уникальных элементов \( n \). Метод Морриса использует регистр \( X \), который инициализируется нулём. При поступлении каждого нового элемента выполняется вероятностное обновление:

• С вероятностью \( 2^{-X} \) значение регистра увеличивается на 1.
• С вероятностью \( 1 - 2^{-X} \) регистр остаётся неизменным.

После обработки всех элементов оценка кардинальности вычисляется как:

\[ \hat{n} = 2^X - 1 \]

где \( X \) — финальное значение регистра. Таким образом, регистр хранит приблизительный логарифм числа уникальных элементов, что позволяет экономить память: для оценки \( n \) до \( 10^9 \) достаточно регистра размером около 30 бит (вместо 4 байт для точного счётчика).

Пример

Предположим, что после обработки потока данных регистр принял значение \( X = 10 \). Тогда оценка количества уникальных элементов составит \( 2^{10} - 1 = 1023 \). Реальное число может отличаться, но в среднем оценка будет близка к истинному значению.

Математическое обоснование

Метод Морриса основан на свойствах случайных процессов. Для анализа алгоритма рассматривается случайная величина \( X \), которая моделирует количество успешных обновлений регистра. Ожидаемое значение \( E[2^X] \) связано с истинным числом \( n \) следующим образом:

\[ E[2^X] = n + 1 \]

Отсюда следует, что оценка \( \hat{n} = 2^X - 1 \) является несмещённой (среднее значение совпадает с истинным). Однако, из-за случайности, дисперсия оценки может быть значительной. Для \( n \), близких к \( 2^m \), стандартное отклонение составляет примерно \( 0.5 \cdot n \), что даёт относительную погрешность порядка 50%.

Улучшения и модификации

Метод Морриса с несколькими регистрами

Для уменьшения погрешности применяется параллельное использование нескольких независимых регистров. Каждый регистр обрабатывает свой поток данных (или один и тот же поток, но с разными начальными случайными значениями). Итоговая оценка вычисляется как среднее арифметическое или медиана оценок от каждого регистра. При использовании \( k \) регистров относительная погрешность уменьшается примерно в \( \sqrt{k} \) раз.

Алгоритм HyperLogLog

Наиболее известное развитие метода Морриса — алгоритм HyperLogLog, предложенный в 2007 году Филиппом Флажоле и его коллегами. HyperLogLog использует хеширование элементов и несколько регистров, каждый из которых хранит максимальное количество ведущих нулей в хеш-значении. Этот алгоритм позволяет оценивать кардинальность до \( 10^9 \) с погрешностью около 2% при использовании всего 1,5 КБ памяти. HyperLogLog широко применяется в базах данных (например, Redis, PostgreSQL) и системах аналитики (Google BigQuery, Apache Druid).

Применение

Метод Морриса и его модификации находят применение в различных областях, где требуется быстрая оценка уникальности больших объёмов данных:

• Сетевой мониторинг: оценка количества уникальных IP-адресов, пакетов или сессий в реальном времени.
• Анализ веб-трафика: подсчёт уникальных посетителей сайта без хранения всех идентификаторов.
• Базы данных: оценка кардинальности атрибутов для оптимизации запросов (например, в PostgreSQL используется расширение HyperLogLog).
• Поисковые системы: оценка числа уникальных документов, содержащих определённое слово, для ранжирования результатов.
• Обработка потоковых данных: в системах типа Apache Kafka, Amazon Kinesis, где объём данных превышает возможности памяти.

Ограничения

• Погрешность: метод даёт приближённую оценку, а не точное значение. Для приложений, требующих абсолютной точности (например, финансовый учёт), он неприменим.
• Зависимость от случайности: качество оценки зависит от качества генератора случайных чисел. В реализациях часто используются псевдослучайные последовательности.
• Ограниченный диапазон: для очень малых \( n \) (менее 10) оценка может быть неточной, так как логарифмическая шкала становится грубой.

Интересные факты

• Робер Моррис также известен как один из создателей операционной системы Unix и языка программирования C (вместе с Кеном Томпсоном и Деннисом Ритчи).
• Метод Морриса был вдохновлён задачами, связанными с подсчётом количества уникальных телефонных номеров в телефонной сети — в то время это было сложной вычислительной задачей.
• В 1985 году Филипп Флажоле и Г. Найджел Мартин предложили улучшенную версию алгоритма — Probabilistic Counting, которая стала основой для HyperLogLog.

Источники

• Morris, R. (1978). Counting Large Numbers of Events in Small Registers. Communications of the ACM, 21(10), 840–842.
• Flajolet, P., Fusy, É., Gandouet, O., & Meunier, F. (2007). HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. Proceedings of the 2007 Conference on Analysis of Algorithms.
• Cormode, G., & Muthukrishnan, S. (2005). An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1), 58–75.
• W. B. Langdon. (2008). A Fast High Quality Pseudo Random Number Generator for Graphics Processing Units. IEEE Transactions on Computers.