Приблизительный алгоритм подсчета
-
Основы алгоритма Морриса
- Алгоритм был разработан в 1977 году и использует вероятностные методы для подсчета событий.
- Он был проанализирован Филиппом Флайоле в начале 1980-х и получил название «приблизительный подсчет».
- Алгоритм фокусируется на качестве аппроксимации и минимизации вероятности ошибки.
-
Математическая основа
- Счетчик представляет собой «оценку порядка величины» реального количества событий.
- Счетчик использует псевдослучайные события для увеличения с вероятностью 0,25.
- Для экономии памяти сохраняется только показатель степени.
-
Выбор значений счетчика
- Использование степеней 2 для значений счетчика экономит память, но может привести к динамическому диапазону ошибок.
- Другие методы выбора значений учитывают доступность памяти, желаемый коэффициент погрешности и диапазон подсчета.
-
Реализация алгоритма
- Алгоритм может быть реализован вручную, подбрасывая монетку для каждого значения счетчика.
- В компьютере счетчик увеличивается путем генерации псевдослучайных битов и их логического И.
-
Приложения алгоритма
- Алгоритм полезен для анализа больших потоков данных и сжатия данных.
- Он также применяется в распознавании изображений и звуков, а также в других приложениях искусственного интеллекта.
-
Ссылки
- Статья Морриса о подсчете событий в небольших регистрах.
- Статья Флайоле с подробным анализом алгоритма.
- Статья Фушса и других о приближенном подсчете методом Пуассона-Лапласа-Меллина.