Резюме Мисры – Гриса - Misra–Gries summary
 | Эта статья нужны дополнительные цитаты для проверка. (Март 2018 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
В области алгоритмы потоковой передачи, Резюме Мисра – Грис используются для решения проблема с частыми элементами в модель потока данных. То есть, учитывая длинный поток ввода, который может быть исследован только один раз (и в некотором произвольном порядке), алгоритм Мисра-Гриса может использоваться для вычисления, какое (если оно есть) значение составляет большую часть потока или, в более общем смысле, , набор элементов, составляющих фиксированную часть потока.
Резюме Мисры – Гриса
Как и для всех алгоритмов в модели потока данных, входом является конечный последовательность из целые числа из конечной области. Алгоритм выдает ассоциативный массив который имеет значения из потока в качестве ключей и оценки их частоты в качестве соответствующих значений. Требуется параметр k который определяет размер массива, который влияет как на качество оценок, так и на объем используемой памяти.
алгоритм misra-gries:[1] Вход: Положительное целое число k Конечная последовательность s принимает значения в диапазоне 1,2, ...,м выход: Ассоциативный массив А с оценками частоты для каждого элемента в s А : = новый (пустой) ассоциативный массив пока s не пусто: брать ценность я из s если я находится в ключах (А): А[я] := А[i] +1 иначе если | ключи (А)| < k - 1: А[я] := 1 еще: для каждого K в ключах (А): А[K] := А[K] - 1 если А[K] = 0: удалить K от ключей (А) возвращаться А
Характеристики
Алгоритм Мисры – Гриса использует O (k(бревно(м) + журнал (п))) Космос, куда м - количество различных значений в потоке и п - длина потока.
Каждый элемент, который встречается как минимум п/k раз гарантированно появится в выходном массиве.[1] Следовательно, при втором проходе по данным точные частоты для k−1 элемент может быть вычислен для решения проблемы частых элементов, или в случае k= 2, проблема большинства. Этот второй проход занимает O (kбревно(м)) Космос.[нужна цитата ]
Резюме (массивы), выводимые алгоритмом: сливаемый, в том смысле, что объединение сводок двух потоков s и р добавляя их массивы по ключам, а затем уменьшая каждый счетчик в результирующем массиве до тех пор, пока k остается результат в виде сводки того же (или лучшего) качества по сравнению с запуском алгоритма Misra-Gries по конкатенация из s с р.
Пример
![[значок]](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png){kind=small} | Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Ноябрь 2017 г.) |
Пусть k = 2 и поток данных 1,4,5,4,4,5,4,4 (n = 8, m = 5). Обратите внимание, что 4 появляется 5 раз в потоке данных, что больше, чем n / k = 4 раза, и, следовательно, должно появиться на выходе алгоритма.
Поскольку k = 2 и | keys (A) | = k − 1 = 1, алгоритм может иметь только один ключ с соответствующим ему значением. Затем алгоритм будет выполняться следующим образом (- означает, что ключ отсутствует):
| Потоковая ценность | Ключ | Ценить |
|---|---|---|
| 1 | 1 | 1 |
| 4 | — | 0 |
| 5 | 5 | 1 |
| 4 | — | 0 |
| 4 | 4 | 1 |
| 5 | — | 0 |
| 4 | 4 | 1 |
| 4 | 4 | 2 |
Выход: 4
Рекомендации
- ^ а б Кормод 2014.
- Misra, J .; Грис, Дэвид (1982). «Поиск повторяющихся элементов». Наука компьютерного программирования. 2 (2): 143–152. Дои:10.1016/0167-6423(82)90012-0. HDL:1813/6345.
- Кормод, Грэм (2014). «Сводки Мисра-Гриса». Ин Као, Мин-Ян (ред.). Энциклопедия алгоритмов. Springer США. С. 1–5. Дои:10.1007/978-3-642-27848-8_572-1. ISBN 9783642278488.