Algoritmus přibližného počítání - Approximate counting algorithm
Přibližné počítání algoritmus umožňuje počítání velkého počtu akcí pomocí malého množství paměti. Vynalezl ji v roce 1977 Robert Morris (kryptograf) z laboratoří Bell Labs a využívá pravděpodobnostní techniky ke zvýšení počitadla . Začátkem 80. let to plně analyzoval Philippe Flajolet ze společnosti INRIA Rocquencourt, který vytvořil název přibližné počítání a výrazně přispěl k jeho uznání mezi výzkumnou komunitou. Když se Nelson a Yu zaměřili na vysokou kvalitu aproximace a nízkou pravděpodobnost selhání, ukázali, že velmi malá modifikace Morrisova čítače je asymptoticky optimální mezi všemi algoritmy pro daný problém. Algoritmus je považován za jeden z předchůdců streamovacích algoritmů a obecnější problém stanovení frekvenčních momentů datového proudu byl pro pole ústředním bodem.
Teorie provozu
Pomocí Morrisova algoritmu představuje čítač „ odhad velikosti řádu “ skutečného počtu. Aproximace je matematicky nestranná .
Pro zvýšení počitadla se používá pseudonáhodná událost, takže přírůstek je pravděpodobnostní událostí. Z důvodu úspory místa je ponechán pouze exponent. Například v základně 2 může počítadlo odhadnout počet na 1, 2, 4, 8, 16, 32 a všechny síly dvou . Požadavek na paměť je jednoduše držet exponent .
Jako příklad by se při přírůstku od 4 do 8 vygenerovalo pseudonáhodné číslo tak, aby pravděpodobnost 0,25 generovala pozitivní změnu v čítači. Jinak zůstane počitadlo na 4.
Níže uvedená tabulka ilustruje některé potenciální hodnoty čítače:
| Uložená binární hodnota čítače | Přiblížení | Rozsah možných hodnot pro skutečný počet | Očekávání (dostatečně velké n, rovnoměrné rozdělení) |
|---|---|---|---|
| 0 | 1 | 0 nebo počáteční hodnota | 0 |
| 1 | 2 | 1 nebo více | 2 |
| 10 | 4 | 2 nebo více | 6 |
| 11 | 8 | 3 nebo více | 14 |
| 100 | 16 | 4 nebo více | 30 |
| 101 | 32 | 5 nebo více | 62 |
Pokud počítadlo obsahuje hodnotu 101, což se rovná exponentu 5 (desetinný ekvivalent 101), pak je odhadovaný počet 2 ^ 5 nebo 32. Existuje poměrně nízká pravděpodobnost, že skutečný počet přírůstkových událostí byl 5 ( ). Skutečný počet přírůstkových událostí bude pravděpodobně „kolem 32“, ale může být libovolně vysoký (s klesající pravděpodobností skutečných počtů nad 39).
Výběr hodnot čítače
Zatímco použití pravomocí 2 jako hodnot čítače je efektivní z hlediska paměti, libovolné hodnoty mají tendenci vytvářet rozsah dynamických chyb a menší hodnoty budou mít větší poměr chyb než větší hodnoty. Jiné metody výběru hodnot čítače berou v úvahu parametry, jako je dostupnost paměti, požadovaný poměr chyb nebo rozsah počítání, aby poskytly optimální sadu hodnot.
Když však několik čítačů sdílí stejné hodnoty, hodnoty jsou optimalizovány podle čítače s největším rozsahem počítání a vytvářejí suboptimální přesnost pro menší čítače. Zmírnění je dosaženo udržováním segmentů nezávislého počítadla odhadů, které omezují účinek většího počítadla na ostatní čítače v segmentu.
Algoritmus
Při zvyšování počitadla „otočte mincí“ počet opakování aktuální hodnoty počitadla. Pokud se to pokaždé objeví „Hlavy“, zvyšte počítadlo. Jinak jej nezvyšujte.
To lze provést programově generováním pseudonáhodných bitů „c“ (kde „c“ je aktuální hodnota čítače) a pomocí logické funkce AND na všech těchto bitech. Výsledkem je nula, pokud jsou některé z těchto pseudonáhodných bitů nulové, a jedna, pokud jsou všechny. Jednoduše přidejte výsledek do počítadla. Tento postup se provede pokaždé, když je zadán požadavek na zvýšení čítače.
Aplikace
Algoritmus je užitečný při zkoumání vzorů velkých datových toků. To je zvláště užitečné v aplikacích komprese dat , rozpoznávání zraku a zvuku a dalších aplikacích umělé inteligence .
