Алгоритм Флажоле–Мартіна — алгоритм розрахунку наближеної оцінки кількості унікальних елементів у потоці за один прохід із споживанням пам'яті, логарифмічним відносно максимально можливої кількості унікальних елементів у потоці. Алгоритм був запропонований Філіпом Флажоле та Дж. Найджелом Мартіном у 1984 році. Згодом він був покращений у роботі «LogLog counting of large cardinalities» Маріанн Дюран та Філіпа Флажоле, а також у «HyperLogLog: The analysis of a near-optimal cardinality estimation algorithm» Філіпа Флажоле та співавторів.
У статті 2010 року «An optimal algorithm for the distinct elements problem» Деніел М. Кейн, Джелані Нельсон та Девід П. Вудрафф пропонують покращений алгоритм, який використовує майже оптимальний обсяг пам'яті та має оптимальний час оновлення і звітування O(1).
Алгоритм Нехай — хеш-функція, що відображає аргумент на цілі числа у діапазоні , при чому результат функції розподілений досить рівномірно. Зауважимо, що множина цілих чисел від 0 до відповідає множині бінарних векторів довжини . Для будь-якого невід'ємного цілого числа визначимо як -й біт у двійковому представленні , такий що:
Далі визначимо функцію , що повертає позицію молодшого встановленого біта у двійковому представленні , інакше — , якщо такого біта не існує (всі біти нульові):
Зауважимо, що в наведеному визначенні використовується індексація з нуля, починаючи з молодшого біта. Наприклад, , оскільки молодший біт дорівнює 1 (позиція 0), і , оскільки молодший встановлений біт знаходиться на позиції 3. Зауважимо, що за умови рівномірного розподілу результату хеш-функції ймовірність отримати хеш-значення, що закінчується на (одиниця, за якою йдуть нулів), дорівнює , що відповідає випаданню орлів, а потім решки при підкиданні «ідеальної монети».
Алгоритм Флажоле–Мартіна для оцінки потужності мультимножини складається з наступних кроків: Ініціалізувати бітовий вектор BITMAP довжиною , заповнений нулями. Для кожного елемента у : Обчислити індекс . Встановити . Нехай позначає найменший індекс , для якого . Тоді оцінка потужності складає , де .
Ідея полягає в тому, що якщо — кількість унікальних елементів у мультимножині , то до звертаються приблизно разів, до — приблизно разів тощо. Відповідно, якщо , то майже напевно дорівнює 0, а якщо , то майже напевно дорівнює 1. Якщо , то може бути як 1, так і 0.
Поправний коефіцієнт () знаходиться за допомогою обчислень, які наведені в оригінальній статті.
Підвищення точності Проблема алгоритму Флажоле–Мартіна у наведеній формі полягає в тому, що результати суттєво варіюються. Поширеним рішенням є багаторазовий запуск алгоритму з різними хеш-функціями та об'єднання результатів різних запусків. Один підхід — обчислити середнє арифметичне результатів, отримавши єдину оцінку потужності. Недолік цього підходу в тому, що середнє значення дуже чутливе до викидів (які тут цілком імовірні). Інший підхід — використовувати медіану, яка менш схильна до впливу викидів. Недолік цього підходу в тому, що результати можуть набувати лише значень виду , де — ціле число. Поширеним рішенням є поєднання середнього та медіани: створити хеш-функцій і розбити їх на окремих груп (кожна розміром ). У межах кожної групи використовувати середнє для агрегування результатів, а потім взяти медіану групових оцінок як кінцеву оцінку.
Алгоритм HyperLogLog 2007 року розбиває мультимножину на підмножини та оцінює їхні потужності, а потім використовує середнє гармонійне для об'єднання їх в остаточну оцінку потужності.
Дивіться також Потоковий алгоритм HyperLogLog
Посилання
Додаткові джерела