Алгоритм Флажолета – Мартина - Flajolet–Martin algorithm

В Алгоритм Флажоле – Мартина является алгоритм для аппроксимации количества различных элементов в потоке с помощью одного прохода и логарифмического использования пространства в максимальном количестве возможных различных элементов в потоке ( проблема с подсчетом ). Алгоритм был представлен Филипп Флажоле и Дж. Найджел Мартин в своей статье 1984 года «Вероятностные алгоритмы подсчета для приложений баз данных».^[1] Позже он был доработан в «LogLog подсчет больших мощностей» Марианна Дюран и Филипп Флажоле,^[2] и "HyperLogLog: Анализ алгоритма оценки мощности, близкого к оптимальному »по Филипп Флажоле и другие.^[3]

В своей статье 2010 года «Оптимальный алгоритм для решения проблемы с отдельными элементами»,^[4] Дэниел М. Кейн, Джелани Нельсон и Дэвид П. Вудрафф предлагают улучшенный алгоритм, который использует почти оптимальное пространство и имеет оптимальные О(1) время обновления и отчетности.

Алгоритм

Предположим, что нам дан хэш-функция ${\displaystyle \mathrm {hash} (x)}$ что отображает ввод ${\displaystyle x}$ к целым числам в диапазоне ${\displaystyle [0;2^{L}-1]}$, и где выходы достаточно равномерно распределены. Обратите внимание, что набор целых чисел от 0 до ${\displaystyle 2^{L}-1}$ соответствует набору двоичных строк длины ${\displaystyle L}$. Для любого неотрицательного целого числа ${\displaystyle y}$, определять ${\displaystyle \mathrm {bit} (y,k)}$ быть ${\displaystyle k}$-й бит в двоичном представлении ${\displaystyle y}$, такое, что:

${\displaystyle y=\sum _{k\geq 0}\mathrm {bit} (y,k)2^{k}.}$

Затем мы определяем функцию ${\displaystyle \rho (y)}$ который выводит позицию младшего разряда набора в двоичном представлении ${\displaystyle y}$:

${\displaystyle \rho (y)=\min\{k\geq 0\mid \mathrm {bit} (y,k)\neq 0\}}$

куда ${\displaystyle \rho (0)=L}$. Обратите внимание, что в приведенном выше определении мы используем 0-индексацию для позиций. Например, ${\displaystyle \rho (13)=\rho (1101_{2})=0}$, так как младший бит равен 1 (0-я позиция), и ${\displaystyle \rho (8)=\rho (1000_{2})=3}$, так как младший бит находится на 3-й позиции. На этом этапе обратите внимание, что в предположении, что выход нашей хеш-функции равномерно распределен, тогда вероятность наблюдения хеш-выхода, заканчивающегося на ${\displaystyle 2^{k}}$ (один, за которым следует ${\displaystyle k}$ нулей) ${\displaystyle 2^{-(k+1)}}$, поскольку это соответствует переворачиванию ${\displaystyle k}$ орла, а затем хвост с честной монетой.

Теперь алгоритм Флажоле – Мартина для оценки мощности мультимножество ${\displaystyle M}$ как следует:

1. Инициализировать битовый вектор BITMAP, чтобы иметь длину ${\displaystyle L}$ и содержать все нули.
2. Для каждого элемента ${\displaystyle x}$ в ${\displaystyle M}$:
   1. Рассчитать индекс ${\displaystyle i=\rho (\mathrm {hash} (x))}$.
   2. Набор ${\displaystyle \mathrm {BITMAP} [i]=1}$.
3. Позволять ${\displaystyle R}$ обозначают наименьший индекс ${\displaystyle i}$ такой, что ${\displaystyle \mathrm {BITMAP} [i]=0}$.
4. Оцените мощность ${\displaystyle M}$ в качестве ${\displaystyle 2^{R}/\phi }$, куда ${\displaystyle \phi \approx 0.77351}$.

Идея в том, что если ${\displaystyle n}$ количество различных элементов в мультимножестве ${\displaystyle M}$, тогда ${\displaystyle \mathrm {BITMAP} [0]}$ доступен примерно ${\displaystyle n/2}$ раз, ${\displaystyle \mathrm {BITMAP} [1]}$ доступен примерно ${\displaystyle n/4}$ раз и так далее. Следовательно, если ${\displaystyle i\gg \log _{2}n}$, тогда ${\displaystyle \mathrm {BITMAP} [i]}$ почти наверняка 0, и если ${\displaystyle i\ll \log _{2}n}$, тогда ${\displaystyle \mathrm {BITMAP} [i]}$ почти наверняка 1. Если ${\displaystyle i\approx \log _{2}n}$, тогда ${\displaystyle \mathrm {BITMAP} [i]}$ можно ожидать, что оно будет равно 1 или 0.

Поправочный коэффициент ${\displaystyle \phi \approx 0.77351}$ находится расчетами, которые можно найти в оригинальной статье.

Повышение точности

Проблема с алгоритмом Флажоле – Мартина в приведенной выше форме заключается в том, что результаты значительно различаются. Распространенным решением было запускать алгоритм несколько раз с ${\displaystyle k}$ различные хэш-функции и объединить результаты разных прогонов. Одна из идей состоит в том, чтобы усреднить ${\displaystyle k}$ получается вместе из каждой хеш-функции, получая единую оценку мощности. Проблема в том, что усреднение очень чувствительно к выбросам (которые, скорее всего, здесь). Другая идея - использовать медиана, который менее подвержен влиянию выбросов. Проблема в том, что результаты могут принимать только форму ${\displaystyle 2^{R}/\phi }$, куда ${\displaystyle R}$ целое число. Распространенное решение - объединить среднее и медиану: ${\displaystyle k\cdot l}$ хэш-функции и разбить их на ${\displaystyle k}$ отдельные группы (каждая размером ${\displaystyle l}$). Внутри каждой группы используйте медианное значение для агрегирования ${\displaystyle l}$ результатов, и, наконец, возьмите среднее значение ${\displaystyle k}$ групповые оценки в качестве окончательной оценки.

2007 год HyperLogLog алгоритм разбивает мультимножество на подмножества и оценивает их мощности, затем он использует гармоническое среднее чтобы объединить их в оценку исходной мощности.^[3]

Смотрите также

• Алгоритм потоковой передачи
• HyperLogLog

Рекомендации

1. Флажолет, Филипп; Мартин, Дж. Найджел (1985). «Вероятностные алгоритмы подсчета для приложений баз данных» (PDF). Журнал компьютерных и системных наук. 31 (2): 182–209. Дои:10.1016/0022-0000(85)90041-8. Получено 2016-12-11.
2. Дюран, Марианна; Флажолет, Филипп (2003). «Логлог-подсчет больших мощностей» (PDF). Алгоритмы - ESA 2003. Конспект лекций по информатике. 2832. п. 605. Дои:10.1007/978-3-540-39658-1_55. ISBN  978-3-540-20064-2. Получено 2016-12-11.
3. Флажолет, Филипп; Фузи, Эрик; Гандуэ, Оливье; Менье, Фредерик (2007). «Hyperloglog: анализ алгоритма почти оптимальной оценки мощности» (PDF). Дискретная математика и теоретическая информатика. Нанси, Франция. AH: 127–146. CiteSeerX  10.1.1.76.4286. Получено 2016-12-11.
4. Кейн, Дэниел М .; Нельсон, Джелани; Вудрафф, Дэвид П. (2010). «Оптимальный алгоритм решения проблемы с отдельными элементами» (PDF). Материалы двадцать девятого симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных данных - PODS '10. п. 41. Дои:10.1145/1807085.1807094. ISBN  978-1-4503-0033-9. Получено 2016-12-11.

Дополнительные источники

• Раджараман, Ананд; Ульман, Джеффри Дэвид (27.10.2011). Майнинг массивных наборов данных. Издательство Кембриджского университета. п. 119. ISBN  9781139505345. Получено 2014-11-09.