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:
| 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 „aaaaaaabbbbbbaaaaaa“ 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.
| 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.
Odkazy a použitá literatura
- Domovská stránka
- Balíček pro Debian/unstable
- HotBits
- Základní informace o rozdělení chí-kvadrát
- Skalská, H.: Stochastické modelování. Skriptum. Gaudeamus, 1998
- Antoch, J., Vorlíčková, D.: Vybrané metody statistické analýzy dat. Praha, Academia 1992
- Rubinstein, R.Y.: Simulation and the Monte Carlo Method. New York, Wiley, 1981
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…:-)
