WikiDer > Алгоритм Флажолета – Мартина

Flajolet–Martin algorithm

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

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

Алгоритм

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

Затем мы определяем функцию который выводит позицию младшего разряда набора в двоичном представлении :

куда . Обратите внимание, что в приведенном выше определении мы используем 0-индексацию для позиций. Например, , так как младший бит равен 1 (0-я позиция), и , так как младший бит находится на 3-й позиции. На этом этапе обратите внимание, что в предположении, что выход нашей хеш-функции равномерно распределен, тогда вероятность наблюдения хеш-выхода, заканчивающегося на (один, за которым следует нулей) , поскольку это соответствует переворачиванию орла, а затем хвост с честной монетой.

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

  1. Инициализировать битовый вектор BITMAP, чтобы иметь длину и содержать все нули.
  2. Для каждого элемента в :
    1. Рассчитать индекс .
    2. Набор .
  3. Позволять обозначают наименьший индекс такой, что .
  4. Оцените мощность в качестве , куда .

Идея в том, что если количество различных элементов в мультимножестве , тогда доступен примерно раз, доступен примерно раз и так далее. Следовательно, если , тогда почти наверняка 0, и если , тогда почти наверняка 1. Если , тогда можно ожидать, что оно будет равно 1 или 0.

Поправочный коэффициент находится расчетами, которые можно найти в оригинальной статье.

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

Проблема с алгоритмом Флажоле – Мартина в приведенной выше форме заключается в том, что результаты значительно различаются. Распространенным решением было запускать алгоритм несколько раз с различные хэш-функции и объединить результаты разных прогонов. Одна из идей состоит в том, чтобы усреднить получается вместе из каждой хеш-функции, получая единую оценку мощности. Проблема в том, что усреднение очень чувствительно к выбросам (которые, скорее всего, здесь). Другая идея - использовать медиана, который менее подвержен влиянию выбросов. Проблема в том, что результаты могут принимать только форму , куда целое число. Распространенное решение - объединить среднее и медиану: хэш-функции и разбить их на отдельные группы (каждая размером ). Внутри каждой группы используйте медианное значение для агрегирования результатов, и, наконец, возьмите среднее значение групповые оценки в качестве окончательной оценки.

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

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

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

  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.

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