Omtrentlig tællealgoritme - Approximate counting algorithm
Den omtrentlige tællealgoritme tillader optælling af et stort antal begivenheder ved hjælp af en lille mængde hukommelse. Opfundet i 1977 af Robert Morris (kryptograf) fra Bell Labs bruger den sandsynlige teknikker til at øge tælleren . Det blev analyseret fuldt ud i begyndelsen af 1980'erne af Philippe Flajolet fra INRIA Rocquencourt, der opfandt navnet omtrentlig optælling og bidrog stærkt til dets anerkendelse blandt forskersamfundet. Når de fokuserede på høj tilnærmelseskvalitet og lav sandsynlighed for fiasko, viste Nelson og Yu, at en meget lille ændring af Morris-tælleren er asymptotisk optimal blandt alle algoritmer til problemet. Algoritmen betragtes som en af forløberne for streamingalgoritmer , og det mere generelle problem med at bestemme frekvensmomenterne for en datastrøm har været centralt i feltet.
Teori om drift
Ved hjælp af Morris 'algoritme repræsenterer tælleren et " estimat af størrelsesorden " af det aktuelle antal. Tilnærmelsen er matematisk upartisk .
For at øge tælleren bruges en pseudo-tilfældig begivenhed, således at inkrementeringen er en sandsynlig begivenhed. For at spare plads holdes kun eksponenten. For eksempel i tælleren 2 kan tælleren estimere tællingen til at være 1, 2, 4, 8, 16, 32 og alle kræfterne i to . Hukommelseskravet er simpelthen at holde eksponenten .
Som et eksempel genereres et pseudotilfældigt tal for at øge fra 4 til 8, således at sandsynligheden for .25 genererer en positiv ændring i tælleren. Ellers forbliver tælleren på 4.
Tabellen nedenfor illustrerer nogle af tællerens potentielle værdier:
| Lagret binær værdi af tælleren | Tilnærmelse | Område af mulige værdier til det faktiske antal | Forventning (tilstrækkelig stor n, ensartet fordeling) |
|---|---|---|---|
| 0 | 1 | 0 eller startværdi | 0 |
| 1 | 2 | 1 eller flere | 2 |
| 10 | 4 | 2 eller flere | 6 |
| 11 | 8 | 3 eller flere | 14 |
| 100 | 16 | 4 eller mere | 30 |
| 101 | 32 | 5 eller mere | 62 |
Hvis tælleren har værdien 101, der svarer til en eksponent på 5 (decimalækvivalenten 101), er det estimerede antal 2 ^ 5 eller 32. Der er en ret lav sandsynlighed for, at den faktiske optælling af inkrementhændelser var 5 ( ). Det faktiske antal optællingshændelser er sandsynligvis "omkring 32", men det kan være vilkårligt højt (med faldende sandsynligheder for faktiske antal over 39).
Valg af tællerværdier
Mens anvendelse af kræfter på 2 som modværdier er hukommelseseffektiv, har vilkårlige værdier tendens til at skabe et dynamisk fejlområde, og de mindre værdier vil have et større fejlforhold end større værdier. Andre metoder til valg af tællerværdier overvejer parametre såsom hukommelsestilgængelighed, ønsket fejlforhold eller tælleområde for at tilvejebringe et optimalt sæt værdier.
Men når flere tællere deler de samme værdier, optimeres værdierne i henhold til tælleren med det største tælleområde og producerer suboptimal nøjagtighed for mindre tællere. Afbødning opnås ved at opretholde Independent Counter Estimation-skovle, som begrænser effekten af en større tæller til de andre tællere i skovlen.
Algoritme
Når du forøger tælleren, skal du "vende en mønt" antallet af gange for tællerens aktuelle værdi. Hvis det kommer op "Heads" hver gang, skal du øge tælleren. Ellers øges det ikke.
Dette kan gøres programmatisk ved at generere "c" pseudo-tilfældige bits (hvor "c" er tællerens aktuelle værdi) og bruge den logiske AND-funktion på alle disse bits. Resultatet er et nul, hvis nogen af disse pseudo-tilfældige bits er nul, og et, hvis de alle er. Du skal blot tilføje resultatet til tælleren. Denne procedure udføres hver gang anmodningen fremsættes om at øge tælleren.
Ansøgninger
Algoritmen er nyttig til at undersøge store datastrømme for mønstre. Dette er især nyttigt i applikationer af datakomprimering , syn og lydgenkendelse og andre applikationer med kunstig intelligens .
