Примерный алгоритм подсчета - Approximate counting algorithm
В примерный алгоритм подсчета позволяет подсчитывать большое количество событий, используя небольшой объем памяти. Изобретен в 1977 г. Роберт Моррис (криптограф) из Bell Labs, оно использует вероятностные методы увеличить прилавок. Он был полностью проанализирован в начале 1980-х гг. Филипп Флажоле из INRIA Роккенкур, придумавший название приблизительный подсчет, и во многом способствовал его признанию среди исследовательского сообщества. Если ориентироваться на высокое качество приближения и низкую вероятность отказа, Нельсон и Ю показали, что очень небольшая модификация счетчика Морриса является асимптотически оптимальной среди всех алгоритмов для этой задачи.[1] Алгоритм считается одним из предшественников потоковых алгоритмов, и более общая проблема определения частотных моментов потока данных была центральной в этой области.
Теория Операции
Используя алгоритм Морриса, счетчик представляет собой "порядок величины оценка »фактического количества. Приближение математически беспристрастный.
Чтобы увеличить счетчик, псевдослучайный событие используется, так что увеличение является вероятным событием. Для экономии места сохраняется только экспонента. Например, в базе 2 счетчик может оценить счет как 1, 2, 4, 8, 16, 32 и все силы двух. Требование к памяти - просто держать показатель степени.
Например, для увеличения от 4 до 8 псевдослучайное число будет сгенерировано так, что вероятность 0,25 генерирует положительное изменение счетчика. В противном случае счетчик останется на 4.
В таблице ниже показаны некоторые возможные значения счетчика:
| Сохраненное двоичное значение счетчика | Приближение | Диапазон возможных значений фактического счета | Ожидание (достаточно большое n, равномерное распределение) |
|---|---|---|---|
| 0 | 1 | 0 или начальное значение | 0 |
| 1 | 2 | 1 или более | 2 |
| 10 | 4 | 2 и более | 6 |
| 11 | 8 | 3 и более | 14 |
| 100 | 16 | 4 и более | 30 |
| 101 | 32 | 5 или больше | 62 |
Если счетчик имеет значение 101, что соответствует показателю 5 (десятичный эквивалент 101), то расчетное количество составляет 2 ^ 5, или 32. Существует довольно низкая вероятность того, что фактическое количество событий приращения было 5 (). Фактическое количество событий приращения, вероятно, будет «около 32», но оно может быть произвольно большим (с уменьшающейся вероятностью для фактических подсчетов выше 39).
Выбор значений счетчика
Хотя использование степени 2 в качестве значений счетчика эффективно с точки зрения памяти, произвольные значения имеют тенденцию создавать динамический диапазон ошибок, а меньшие значения будут иметь больший коэффициент ошибок, чем большие значения. Другие методы выбора значений счетчика учитывают такие параметры, как доступность памяти, желаемый коэффициент ошибок или диапазон счета, чтобы обеспечить оптимальный набор значений.[2]
Однако, когда несколько счетчиков имеют одинаковые значения, значения оптимизируются в соответствии со счетчиком с наибольшим диапазоном счета и обеспечивают неоптимальную точность для счетчиков меньшего размера. Снижение риска достигается за счет поддержки сегментов независимой счетной оценки,[3] которые ограничивают действие большего счетчика на другие счетчики в ведре.
Алгоритм
При увеличении счетчика «подбросьте монетку» количество раз, превышающее текущее значение счетчика. Если каждый раз появляется «Головы», увеличьте счетчик. В противном случае не увеличивайте его.
Это можно сделать программно, генерируя псевдослучайные биты «c» (где «c» - текущее значение счетчика) и используя функцию логического И для всех этих битов. Результатом будет ноль, если любой из этих псевдослучайных битов равен нулю, и единицу, если все они равны единице. Просто добавьте результат на счетчик. Эта процедура выполняется каждый раз, когда делается запрос на увеличение счетчика.
Приложения
Алгоритм полезен при исследовании больших потоков данных на наличие шаблонов. Это особенно полезно в приложениях Сжатие данных, распознавание звука и звука и др. искусственный интеллект Приложения.
Смотрите также
Рекомендации
- ^ Нельсон, Джелани; Ю, Хуачэн (2020). «Оптимальные оценки для приближенного счета». arXiv:2010.02116. Цитировать журнал требует
| журнал =(помощь) - ^ Цидон, Эрез, Иддо Ханниэль и Исаак Кесласси. «Оценщикам также нужны общие ценности, чтобы расти вместе». ИНФОКОМ, 2012 Труды IEEE. IEEE, 2012 г.
- ^ Einziger, G .; Fellman, B .; Касснер, Ю. (апрель 2015 г.). «Ковши независимой счетной оценки». Конференция IEEE по компьютерным коммуникациям, 2015 г. (INFOCOM): 2560–2568. Дои:10.1109 / INFOCOM.2015.7218646. ISBN 978-1-4799-8381-0.