Souhrn Misra – Gries - Misra–Gries summary
 | tento článek potřebuje další citace pro ověření. (Březen 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) |
V oblasti streamovací algoritmy, Souhrny Misra – Gries se používají k řešení problém častých prvků v model datového proudu. To znamená, že vzhledem k dlouhému proudu vstupu, který lze zkoumat pouze jednou (a v libovolném pořadí), lze použít algoritmus Misra-Gries k výpočtu, která (pokud existuje) tvoří většinu proudu, nebo obecněji , sada položek, které tvoří určitý pevný zlomek streamu.
Souhrn Misra – Gries
Stejně jako u všech algoritmů v modelu datového proudu je vstup konečný sekvence z celá čísla z konečné domény. Algoritmus vydává a asociativní pole který má hodnoty ze streamu jako klíče a odhady jejich frekvence jako odpovídající hodnoty. Trvá to parametr k což určuje velikost pole, což má dopad jak na kvalitu odhadů, tak na velikost použité paměti.
algoritmus misra-gries:[1] vstup: Kladné celé číslo k Konečná posloupnost s převzetí hodnot v rozsahu 1,2, ...,m výstup: Asociativní pole A s odhady frekvence pro každou položku v s A : = nové (prázdné) asociativní pole zatímco s není prázdný: vzít hodnota i z s -li i je v klíčích (A): A[i] := A[i] + 1 jinak pokud | klíče (A)| < k - 1: A[i] := 1 jiný: pro každého K. v klíčích (A): A[K.] := A[K.] - 1 -li A[K.] = 0: odebrat K. z klíčů (A) vrátit se A
Vlastnosti
Algoritmus Misra – Gries používá O (k(log (m) + protokol (n))) prostor, kde m je počet odlišných hodnot ve streamu a n je délka proudu.
Každá položka, která se vyskytuje alespoň n/k časy se zaručeně objeví ve výstupním poli.[1] Proto v druhém průchodu dat, přesné frekvence pro k−1 položek lze vypočítat k vyřešení problému s častými položkami nebo v případě k= 2, většinový problém. Tento druhý průchod trvá O (klog (m)) prostor.[Citace je zapotřebí ]
Souhrny (pole) výstupem algoritmu jsou slučitelné, v tom smyslu, že kombinuje souhrny dvou proudů s a r přidáním jejich polí klíčem a následným snížením každého čítače ve výsledném poli, dokud pouze k klíče zůstanou výsledkem souhrnu stejné (nebo lepší) kvality ve srovnání s spuštěním algoritmu Misra-Gries přes zřetězení z s s r.
Příklad
![[ikona]](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png){kind=small} | Tato sekce potřebuje expanzi. Můžete pomoci přidávat k tomu. (Listopad 2017) |
Nechť k = 2 a datový tok je 1,4,5,4,4,5,4,4 (n = 8, m = 5). Všimněte si, že 4 se v datovém proudu objevuje 5krát, což je více než n / k = 4krát, a proto by se měl objevit jako výstup algoritmu.
Protože k = 2 a | klíče (A) | = k − 1 = 1, může mít algoritmus pouze jeden klíč s odpovídající hodnotou. Algoritmus se poté provede následujícím způsobem (- znamená, že není k dispozici žádný klíč):
| Hodnota streamu | Klíč | Hodnota |
|---|---|---|
| 1 | 1 | 1 |
| 4 | — | 0 |
| 5 | 5 | 1 |
| 4 | — | 0 |
| 4 | 4 | 1 |
| 5 | — | 0 |
| 4 | 4 | 1 |
| 4 | 4 | 2 |
Výstup: 4
Reference
- ^ A b Cormode 2014.
- Misra, J .; Gries, David (1982). Msgstr "Hledání opakovaných prvků". Věda o počítačovém programování. 2 (2): 143–152. doi:10.1016/0167-6423(82)90012-0. hdl:1813/6345.
- Cormode, Graham (2014). „Misra-Gries Summaries“. V Kao, Ming-Yang (ed.). Encyclopedia of Algorithms. Springer USA. s. 1–5. doi:10.1007/978-3-642-27848-8_572-1. ISBN 9783642278488.