Misra–Gries heavy hitters-algoritm
Misra och Gries definierade heavy-hitters-problemet (även om de inte introducerade termen heavy-hitters ) och beskrev den första algoritmen för det i tidningen Finding repeated elements . Deras algoritm utökar Boyer-Moores majoritetssökningsalgoritm på ett betydande sätt.
En version av heavy-hitters-problemet är följande: Givet är en påse b med n element och ett heltal k ≥ 2 . Hitta de värden som förekommer mer än n ÷ k gånger i b . Misra-Gries-algoritmen löser problemet genom att göra två övergångar över värdena i b , samtidigt som den lagrar högst k värden från b och deras antal förekomster under algoritmens gång.
Misra-Gries är en av de tidigaste streamingalgoritmerna , och den beskrivs nedan med de termerna i avsnittet #Sammanfattningar .
Misra–Gries algoritm
En väska är en liknande uppsättning där samma värde kan förekomma flera gånger. Antag att en påse är tillgänglig som en array b[0:n – 1] med n element. I den abstrakta beskrivningen av algoritmen behandlar vi b och dess segment också som påsar. I fortsättningen är ett tungt slag av påse b ett värde som förekommer mer än n ÷ k gånger i den, för något heltal k , k≥2 .
En k -reducerad påse för påse b härleds från b genom att upprepa följande operation tills det inte längre är möjligt: Ta bort k distinkta element från b . Från dess definition innehåller en k -reducerad påse färre än k olika värden. Följande teorem är lätt att bevisa:
Sats 1. Varje heavy-hitter av b är ett element i en k -reducerad påse för b .
Det första passet av heavy-hitters-beräkningen konstruerar en k -reducerad påse t . Det andra passet förklarar att ett element av t är en tung-hitter om det förekommer mer än n ÷ k gånger i b . Enligt sats 1 bestämmer denna procedur alla och bara de som slår tunga. Det andra passet är lätt att programmera, så vi beskriver endast det första passet.
För att konstruera t , skanna värdena i b i godtycklig ordning, för specificitet skannar följande algoritm dem i ordningen med ökande index. Invariant P för algoritmen är att t är en k -reducerad påse för de skannade värdena och d är antalet distinkta värden i t . Initialt har inget värde skannats, t är den tomma påsen och d är noll.
P: 0 ≤ i ≤ n t är en k -reducerad påse för b[0:i – 1] d är antalet distinkta värden i t 0 ≤ d < k
Närhelst element b[i] skannas, för att bevara invarianten: (1) om b[i] inte är i t , lägg till det till t och öka d med 1, (2) om b[i] är i t , lägg till det i t men ändra inte d , och (3) om d blir lika med k , reducera t genom att ta bort k distinkta värden från det och uppdatera d på lämpligt sätt.
0
algoritm Misra–Gries är 1 = t, d := { }, 0; för i från till n-1 gör om b[i] t då t, d:= t ∪ {b[i]}, d+1 annars t, d:= t ∪ {b[ i]} endif om d = k så Ta bort k distinkta värden från t; uppdatera d endif endfor
En möjlig implementering av t är som en uppsättning par av formen (vi , c i ) där varje v i är ett distinkt värde i t och c i är antalet förekomster av v i in t . Då d storleken på denna uppsättning. Steget "Ta bort k distinkta värden från t " innebär att reducera varje c i med 1 och sedan ta bort valfritt par ( v i , c i ) från uppsättningen om c i blir 0.
Genom att använda en AVL-trädimplementering av t har algoritmen en körtid på O(n log k) . För att bedöma utrymmesbehovet, antag att elementen i b kan ha m möjliga värden, så lagringen av ett värde v i behöver O(log m) bitar. Eftersom varje räknare ci bitar kan ha ett värde så högt som n behöver dess lagring O(log n) . Därför, för O(k) -värderäknarpar är utrymmeskravet O(k (log n + log m)) .
Sammanfattningar
Inom området för strömmande algoritmer kan utdata från Misra-Gries-algoritmen i det första passet kallas en sammanfattning , och sådana sammanfattningar används för att lösa problemet med frekventa element i dataströmsmodellen . En strömningsalgoritm gör ett litet, begränsat antal passeringar över en lista med dataobjekt som kallas en ström . Den bearbetar elementen med som mest logaritmisk mängd extra utrymme i storleken på listan för att producera ett svar.
Termen Misra–Gries sammanfattning verkar ha myntats av Graham Cormode.