Алгоритм поиска ТОП N наиболее частых элементов в потоке данных с использованием небольшого количества памяти
В публикации http://dimacs.rutgers.edu/~graham/pubs/papers/freqcacm.pdf описан Space Saving (под 3 номером) алгоритм поиска ТОП N наиболее частых элементов в потоке данных, или, в моем случае, а файле, значительно большем, чем объем доступной памяти. Так же есть презентация на тему этого алгоритма https://imoumoulidou.github.io/SpaceSaving_Presentation.pdf Я попытался его реализовать этот алгоритм, но столкнулся с тем, что не до конца его понимаю. В презентации присутствует переменная overestimation, которая используется для корректировки счетчиков. Похожие манипуляции со счетчиком описаны в последней секции алгоритма в freqcacm.pdf.
Моя проблема в том, что я не могу сообразить, как это реализовать эту корректировку, без которой, естественно, ничего не работает.
Мои наработки - https://github.com/sltrs1/space_saving_alg_data_stream
Ответы (1 шт):
Алгоритм использует ограниченное количество счетчиков (m пар (ключ/количество)). Его отличие от "честного" подсчета - особый случай: если m счетчиков (разных ключей) уже заняты (содержат ненулевые количества) и на входе есть новый ключ, то он заменяет ключ с минимальным количеством и при этом "наследует" это минимальное количество и увеличивает его на 1. При этом счетчик помечается (overestimated): по сути в нем суммируются несколько счетчиков (текущий и унаследованный(-ые)). Если далее окажется, что этот счетчик попадет в искомый результат, то достоверность не 100%, а с некоей поправкой. А если нет, то этот счетчик просто отслужит "тихую" службу. Где и как именно overestimation используется в корректировке счетчиков? В алгоритмах этого не видно. В программе (Мои наработки, main.c) overest используется, видимо, только для вывода all_vars_size. Возможно, я бы начал с небольших, но достаточно наглядных наборов данных с наглядным отображением: что происходит со счетчиками? И еще интересный вопрос: А что, если минимальному количеству соответствуют разные счетчики, один из которых уже помечен как overest, а другой нет? Можно выбрать и протестировать разные варианты...