Hlavní navigace

ENT - Program pro testování sekvencí pseudonáhodných čísel

17. 1. 2005
Doba čtení: 6 minut

Sdílet

Určitě jste již někdy v životě potřebovali otestovat náhodnost řady čísel, byť o tom třeba ještě nevíte. Možná se zeptáte, k čemu to může být dobré, a já se vaší otázce upřímně řečeno moc nedivím. Ale nebojte se - pár možností pro inspiraci zmíním hned v úvodu. V článku se mimo jiné také dozvíte, jak si stojí některé běžné generátory pseudonáhodných čísel, a vězte, že chválit se nebude..

Rozumná otázka vyžaduje rozumnou odpověď: Předně, testování náhodnosti je nezbytností pro každého, kdo tvoří generátor náhodných čísel – ať už pro účely šifrování, či pro statistický výzkum. Tím samozřejmě neskončíme – podle míry náhodnosti můžete například usoudit například, zda (a jak hodně) je možné teoreticky zkomprimovat soubor, aniž byste to zkoušeli skutečně provádět. S výsledky takového zkoumání bude rozumné porovnat účinnost kompresního algoritmu, který právě vyvíjíte či používáte. Zkoumáním entropie poznáte, jak hodně plýtvají místem různé datové formáty. A hlavně – užijete si při tom spoustu zábavy ;-)

Testy

Ve všech těchto případech vám přijde vhod pseudorandom number sequence test, zkráceně ENT. Program provádí rozličné testy souboru udaného jako parametr anebo datového proudu, který do něj nasměrujete ze standardního vstupu. Dozvíte se především tyto informace:

Entropie

Vyjadřuje informační hustotu souboru v bitech na znak. Čím vyšších hodnot dosahuje, tím je soubor informačně hustší. Hodnoty pro komprimované soubory (téměř maximálně husté, téměř náhodný vzorek) se blíží 8, naopak entropie psaného textu se může pohybovat okolo 5.

Možnost komprese

Udává, o kolik procent bude soubor menší, pokud se optimálně zkomprimuje. Vychází se přitom z testu entropie. Počítá se zde s kousky dat o velikosti jednoho bytu, výsledky je proto třeba brát s rezervou – algoritmy pracující s většími rámci (např. LZW) mohou dosahovat lepších výsledků, pokud jsou v datech opakující se sekvence více bytů.

Chí kvadrát test dobré shody

Důležitý statistický test, používá se k porovnání dvou rozdělení. Ta mohou být zadána nějakým vzorcem anebo sadou konkrétních hodnot – takovému rozdělení se pak říká empirické. Vlastní testování v našem případě zahrnuje stanovení navazujících disjunktních intervalů empirického rozdělení (testovaných dat) a posčítání četností v těchto intervalech. Dále se zjistí teoretické četnosti (podle předpokládaného tvaru rozdělení) v každém z intervalů. Z rozdílů četností se nakonec odvodí testové kritérium, na základě kterého se může (porovnáním s hodnotou chí kvadrát rozdělení) rozhodnout o náhodnosti. Do detailů zabíhat nebudeme, pokud vás téma zajímá, můžete sáhnout po leckteré učebnici statistiky.

Test se používá leckde a pro leccos, mimo jiné pro testování kvality řad pseudonáhodných čísel, a je vysoce citlivý na různé běžné neduhy. Program zjistí absolutní hodnotu testu a pro srozumitelnost dopočítá, jak často by tuto hodnotu překročila skutečně náhodná data. Výsledek můžeme interpretovat jako určitý stupeň nenáhodnosti. Hodnota pro náhodná data by se měla pohybovat co nejblíže středu rozsahu, tedy kolem 50 % Jak již ale bylo řečeno, test je to docela citlivý, a tak je i oblast pravděpodobné náhodnosti dosti široká. Tabulka shrnuje, jak by měly být chápány různé výsledky:

Tabulka č. 625
Výsledek testu v % Interpretace – náhodnost dat
0 - 1 % téměř jistě nenáhodná
1 - 5 % podezředlá (asi nenáhodná)
5 - 10 % trochu podezřelá (možná nenáhodná)
10 - 90 % pravděpodobně náhodná data
90 - 95 % trochu podezřelá (možná nenáhodná)
95 - 99 % podezředlá (asi nenáhodná)
99 - 100 % téměř jistě nenáhodná

Test dobré shody odhalí mnohé takové zdroje a typy nenáhodnosti, na které například test entropie nestačí. Jak píše autor projektu, je jím možné odhalit nedostatečnost mnoha běžně používaných generátorů. Například standardní Unixová rand() funkce dosahuje velice hanebných hodnot – výsledek testu pro 500000 vzorků je 0,01. Náhodná data by tuto hodnotu překročila v 99,99 procentech případů, a je tedy naprosto nepřijatelná pro seriózní použití. Vylepšený generátor (Park & Miller) dosahuje hodnot o poznání lepších – testové kritérium je 212,53 a náhodný vzorek by překročil tuto hodnotu „pouze“ v 95 % případů, ovšem i to je mnohdy nedostatečné. Mnohem lepších výsledků (237,05 a 75 %) dosahuje například sada náhodných čísel HotBits. Tato čísla ale již nejsou počítačově generovaná pseudonáhodná čísla, ale skutečná, ryzí náhodná čísla „generovaná“ kvantovými procesy při radioaktivním rozpadu na subatomární úrovni. Více viz odkazy na konci článku.

Aritmetický průměr

Jednoduchá charakteristika – všechny byty (popř. bity při parametru -b) jsou sečteny a vyděleny jejich počtem v souboru. Průměr bytů úplně náhodného, dostatečně velkého vzorku dat je logicky 127,5 a průměr bitů je analogicky 0,5. Tímto testem zjistíte, zda jsou hodnoty v celém souboru spíše vysoké nebo nízké.

Hodnota Monte Carlo pro π

Každá po sobě jdoucí sekvence šesti bytů je interpretována jako 24bitové X a Y souřadnice čtverce. Pokud jsou vzdálenosti náhodně generovaného bodu menší než poloměr kružnice vepsané čtverci, považuje se tato sekvence za „zásah“. Z procenta zásahů se spočítá hodnota π. Pro opravdu velké soubory dat se takto spočítaná hodnota bude blížit skutečnému π, je-li soubor náhodný. Pro vzorek 32768 bytů již zmíněných náhodných čísel získaných pozorováním radioaktivního rozpadu vychází 3,139648438, tedy chyba 0.06 procent.

Hodnota koeficientu seriální korelace

Měří, jak hodně každý byte závisí na bytu předchozím. Pro náhodné sekvence se tato hodnota blíží nule, pokud data nejsou náhodná, může nabýt kladné či záporné hodnoty. Nenáhodné vzorky (například psaný text) dosahují hodnot kolem 0,5. Opravdu hodně předpověditelná data – nekomprimované bitmapy, text typu „aaaaaaabbbbbba­aaaaa“ a podobné se blíží hodnotě 1.

Co program neumí

ENT pár užitečných testů provede, ovšem pro definitivní přijetí či zatracení dat by stálo za to zkusit ještě některé další. Chybí mi především testy, které by odhalily konkrétní problémy – test extrémních bodů, test znamének diferencí (hledá nežádoucí trendy), test pořadové korelace (zda např. na začátku nejsou velké a na konci malé hodnoty), test seriální korelace (zda nejsou souvislosti například mezi sousedními čísly) a možná některé další.

Používání

Program ELF je klasicky řádkový, nemá žádné grafické rozhraní. Vstupní data můžete specifikovat uvedením jména souboru jako argumentu, popřípadě klasicky přesměrovat vstup. Výstup směřuje vždy na standardní výstup, pro zaznamenání výsledku do souboru se tedy přesměrování nevyhnete.

Tabulka č. 626
Parametr Význam
-b považuje vstup za bity a nikoliv za 8bitové byty
-c tiskne navíc tabulku počtů výskytů všech hodnot a jejich podíl na celkové velikosti souboru
-f před testováním převede velká písmena na malá
-t strohý výstup, hodnoty oddělené čárkami, vhodné pro import výsledků do tabulky, databáze či pro jiné počítačové zpracování
-u nápověda

Program je pod public domain open source licencí k dispozici na domovské stránce jako zip archiv. Ten obsahuje zdrojový kód v C++, Makefile pro kompilaci pod Unixem a pro vyšší pohodlí uživatelů systémů DOS a Windows (kteří asi nejsou zvyklí běžně si programy kompilovat) spustitelný exe soubor. Většinu informací pro článek jsem čerpal rovněž odtamtud.

UX DAy - tip 2

Odkazy a použitá literatura

Příloha: Ukázkový výstup

Tak takhle nějak vypadá výsledek testu náhodnosti tohoto článku (s parametrem -c pro statistiku jednotlivých znaků):

Value Char Occurrences Fraction
  9              387   0.031162
 10              303   0.024398
 13              303   0.024398
 32             1160   0.093405
 33   !            2   0.000161
 34   "          102   0.008213
 37   %           41   0.003301
 38   &           29   0.002335
 40   (           21   0.001691
 41   )           23   0.001852
 42   *            4   0.000322
 43   +            2   0.000161
 44   ,           72   0.005798
 45   -           56   0.004509
 46   .           91   0.007327
 47   /          179   0.014413
 48   0           77   0.006200
 49   1           38   0.003060
 50   2           21   0.001691
 51   3           28   0.002255
 52   4           21   0.001691
 53   5           35   0.002818
 54   6            3   0.000242
 55   7            6   0.000483
 56   8           11   0.000886
 57   9           32   0.002577
 58   :           40   0.003221
 59   ;           35   0.002818
 60   <          313   0.025203
 61   =          111   0.008938
 62   >          313   0.025203
 64   @            1   0.000081
 65   A           90   0.007247
 66   B           21   0.001691
 67   C           44   0.003543
 68   D          125   0.010065
 69   E          104   0.008374
 70   F           23   0.001852
 71   G           30   0.002416
 72   H           98   0.007891
 73   I           74   0.005959
 74   J            5   0.000403
 75   K            2   0.000161
 76   L           83   0.006683
 77   M           25   0.002013
 78   N           75   0.006039
 79   O           59   0.004751
 80   P          151   0.012159
 81   Q            1   0.000081
 82   R           68   0.005475
 83   S           41   0.003301
 84   T          239   0.019245
 85   U           10   0.000805
 86   V           42   0.003382
 87   W           39   0.003140
 88   X            1   0.000081
 89   Y           38   0.003060
 90   Z           11   0.000886
 95   _            1   0.000081
 97   a          463   0.037282
 98   b          151   0.012159
 99   c          173   0.013930
100   d          330   0.026572
101   e          533   0.042918
102   f           22   0.001771
103   g           50   0.004026
104   h          211   0.016990
105   i          276   0.022224
106   j          103   0.008294
107   k          213   0.017151
108   l          184   0.014816
109   m          270   0.021741
110   n          497   0.040019
111   o          662   0.053305
112   p          228   0.018359
113   q            9   0.000725
114   r          300   0.024157
115   s          323   0.026009
116   t          530   0.042677
117   u          220   0.017715
118   v          203   0.016346
119   w           13   0.001047
120   x            9   0.000725
121   y          109   0.008777
122   z          111   0.008938
123   {            1   0.000081
125   }            1   0.000081
154               32   0.002577
157                2   0.000161
158               56   0.004509
200   Č            1   0.000081
225   á          169   0.013608
232   č           69   0.005556
233   é           88   0.007086
236   ě           81   0.006522
237   í          191   0.015380
239   ď            2   0.000161
242   ň            1   0.000081
243   ó            2   0.000161
248   ř           63   0.005073
249   ů           41   0.003301
250   ú            5   0.000403
253   ý           61   0.004912

Total:         12419   1.000000

Entropy = 5.661359 bits per byte.

Optimum compression would reduce the size
of this 12419 byte file by 29 percent.

Chi square distribution for 12419 samples is
80262.42, and randomly would exceed this value
0.01 percent of the times.

Arithmetic mean value of data bytes is 90.2712
(127.5 = random).
Monte Carlo value for Pi is 3.717738038
(error 18.34 percent).
Serial correlation coefficient is 0.277645
(totally uncorrelated = 0.0).

Článek na 99,99 % není náhodný shluk písmen, což mě potěšilo…:-)

Byl pro vás článek přínosný?

Autor článku