海量隨機(jī)數(shù)碰撞率檢測(cè)的快捷方法

孟秀哲　楊棟毅

摘 要： 針對(duì)海量隨機(jī)數(shù)碰撞率實(shí)時(shí)檢測(cè)的需求，利用隨機(jī)數(shù)的隨機(jī)特性，結(jié)合文件系統(tǒng)路徑編碼的方式，提出了一種類(lèi)似于平衡B叉樹(shù)的平衡檢索森林的結(jié)構(gòu)與算法。該方法避免了平衡B叉樹(shù)的編程復(fù)雜性，檢測(cè)效率非常高，有效地解決了海量隨機(jī)數(shù)碰撞率檢測(cè)因耗時(shí)量過(guò)大而難以在工程上快速實(shí)現(xiàn)的問(wèn)題。

關(guān)鍵詞： 隨機(jī)數(shù)； 海量隨機(jī)數(shù)； 碰撞率檢測(cè)； 路徑編碼； 平衡檢索森林

中圖分類(lèi)號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2016）08-44-03

Abstract： For the demand of real-time detection of massive random number collision rate， by using the stochastic properties of the random number and the file system path coding， a method of balanced search forest similar to the balanced B search tree is proposed. This method avoids the programming complexity of the balanced B search tree， and the detection efficiency is very high. It can effectively solve the problem that the collision rate detection of massive random number is too much time consuming to be quickly realized in engineering.

Key words： random number； massive random number； collision rate detection； path coding； balanced search forest

0 引言

隨機(jī)數(shù)對(duì)于系統(tǒng)仿真[1]、信息通訊[2]、計(jì)算機(jī)隨機(jī)模擬[3]、隨機(jī)局部搜索[4]、密碼研究[5]、隨機(jī)驗(yàn)證碼、彩票博弈、實(shí)驗(yàn)設(shè)計(jì)和隨機(jī)抽樣等領(lǐng)域或方面都有著十分重要的作用。隨機(jī)序列的隨機(jī)性，主要體現(xiàn)在兩個(gè)方面，一是這個(gè)序列的產(chǎn)生是無(wú)法確定的，而且是不可以復(fù)現(xiàn)的；二是這個(gè)序列具有統(tǒng)計(jì)特性，當(dāng)序列足夠長(zhǎng)時(shí)，其中的0和1的個(gè)數(shù)趨于相等，即具有0、1的均勻性。前者可以用碰撞率來(lái)測(cè)度，后者可以用均勻性來(lái)測(cè)度。碰撞率就是讀取或產(chǎn)生一系列的32位隨機(jī)數(shù)，統(tǒng)計(jì)隨機(jī)雙字的重復(fù)次數(shù)，最理想的結(jié)果就是碰撞次數(shù)為0。

海量隨機(jī)數(shù)的數(shù)據(jù)量非常大，常常是邊產(chǎn)生邊檢驗(yàn)，這就需要維持一張表，不斷登記檢測(cè)過(guò)的隨機(jī)數(shù)，統(tǒng)計(jì)鍵值重復(fù)的次數(shù)。隨著檢測(cè)過(guò)程的不斷加長(zhǎng)，這張記錄表會(huì)越來(lái)越大。如果采用順序查找，則編程簡(jiǎn)單，但效率低下，平均查找次數(shù)約為（N+1）/2[6]，N為表中記錄數(shù)。如果采用二分查找，則需要對(duì)順序表進(jìn)行排序，開(kāi)銷(xiāo)可能超過(guò)二分查找所節(jié)省的時(shí)間?！笆褂枚鏄?shù)結(jié)構(gòu)，不僅能有效地查表，而且還能迅速地插入和刪除記錄”[7]，二叉樹(shù)結(jié)構(gòu)因?yàn)閺?fù)雜而使得編程變得困難。為此，我們提出了用于海量隨機(jī)數(shù)碰撞率實(shí)時(shí)檢測(cè)的平衡檢索森林的巧妙思想與簡(jiǎn)捷方法。

1 平衡檢索森林的基本原理

1.1 基本思想

在平衡檢索森林中，葉子文件的訪(fǎng)問(wèn)是通過(guò)隨機(jī)數(shù)位段編碼的方式均勻地進(jìn)行，葉子文件訪(fǎng)問(wèn)的均勻性源于隨機(jī)數(shù)位段的隨機(jī)性?？焖贆z索森林是靜態(tài)平衡的，而不需要像平衡B叉樹(shù)那樣，需要?jiǎng)討B(tài)維護(hù)節(jié)點(diǎn)的平衡[8]，這是快速檢索森林的一大特性與優(yōu)勢(shì)，即沒(méi)有額外的維護(hù)開(kāi)銷(xiāo)。通過(guò)對(duì)每個(gè)隨機(jī)數(shù)四個(gè)位段的編碼（詳見(jiàn)2、平衡檢索森林的編碼規(guī)則），分別形成子樹(shù)、目錄和文件的地址，以及，記錄的鍵值。路徑與鍵值兩方個(gè)面的編碼使得葉子文件均勻分布在整個(gè)檢索森林之下，巨大單一文件被分割為巨量小文件。

假定隨機(jī)數(shù)具有30比特有效信息，則不重復(fù)隨機(jī)數(shù)文件最多有230=1073741824條記錄，接近海量數(shù)據(jù)。我們不是在一個(gè)巨型文件中存儲(chǔ)或檢索這10億多條記錄，而是將這棵巨大無(wú)比的單枝樹(shù)，人為地切分成一片均勻森林，由32棵樹(shù)組成，每棵樹(shù)有32個(gè)樹(shù)杈，每個(gè)樹(shù)杈下面有128片葉子，葉子即子文件，每個(gè)葉子最多只有8192條記錄。葉子文件共有：32*32*128=25*25*27=217=131072（個(gè)）。對(duì)于一個(gè)30比特的隨機(jī)數(shù)進(jìn)行檢索的過(guò)程，實(shí)際上就是根據(jù)鍵值的四個(gè)位段來(lái)定位某棵樹(shù)、某樹(shù)杈、某文件及某條記錄的過(guò)程。其中，對(duì)樹(shù)、樹(shù)杈及文件的定位，是不需要耗費(fèi)時(shí)間的，它體現(xiàn)在文件路徑的編碼上面；對(duì)記錄的查找采用簡(jiǎn)單的順序檢索方式進(jìn)行，隨機(jī)數(shù)記錄的維護(hù)也采用尾部添加的簡(jiǎn)單方式順序存儲(chǔ)。檢索過(guò)程中，若子鍵值不存在，則將其添加于某個(gè)子文件尾部；若子鍵值存在，則碰撞次數(shù)++，子鍵值不添加于子文件尾部。

1.2 編碼規(guī)則

⑴ 對(duì)于任意一個(gè)30位的隨機(jī)數(shù)，按照四個(gè)位段編碼如下：

該森林32棵樹(shù)的編號(hào)（0到31）由隨機(jī)數(shù)的高5位（位29到25）決定，000002 到111112分別對(duì)應(yīng)子樹(shù)0到子樹(shù)31。某棵樹(shù)32樹(shù)杈的編號(hào)（0到31）由隨機(jī)數(shù)的次5位（位24到20）決定。某樹(shù)杈128個(gè)葉子文件的編號(hào)（0到127）由隨機(jī)數(shù)的次次7位（位19到13）決定。而隨機(jī)數(shù)的最后13位（位12到0）作為30位隨機(jī)數(shù)的代表儲(chǔ)存于小文件中，子文件的記錄數(shù)最多為213=8192條，這樣，一個(gè)巨型文件的海量檢索就被化簡(jiǎn)為一個(gè)小文件的小規(guī)模順序檢索。

⑵ 假定當(dāng)前隨機(jī)數(shù)的十進(jìn)制數(shù)值為123456789，則十六進(jìn)制數(shù)為0x75BCD15，二進(jìn)制數(shù)為1110101101111001101000101012，不足30位前補(bǔ)0，為（00011）（10101）（1011110）（0110100010101）2，下標(biāo)2表示二進(jìn)制。

⑶ 該隨機(jī)數(shù)對(duì)應(yīng)樹(shù)的編號(hào)由鍵值的高5位（即第一個(gè)括號(hào)里面的5比特）決定，上述鍵值所在樹(shù)的編號(hào)即為000112=3。

⑷ 該隨機(jī)數(shù)對(duì)應(yīng)樹(shù)杈的編號(hào)，由鍵值的次5位（即第二個(gè)括號(hào)里面的5比特）決定，上述鍵值所在樹(shù)杈的編號(hào)即為101012=21。

⑸ 該隨機(jī)數(shù)對(duì)應(yīng)樹(shù)葉（即子文件）的編號(hào)，由鍵值的次次7位（即第三個(gè)括號(hào)里面的7比特）決定，上述鍵值所在樹(shù)葉的編號(hào)即為10111102=94。

⑹ 上述鍵值的末13位（即第四個(gè)括號(hào)里面的13比特），用來(lái)表示一個(gè)子文件的鍵值記錄，順序存儲(chǔ)或檢索不超過(guò)8192條的13位子鍵值，比順序存儲(chǔ)或查找1073741824條主鍵值要快得多。當(dāng)前子文件的子鍵值為01101000101012=3349。

由鍵值的四個(gè)位段，可以定位隨機(jī)數(shù)位于：子樹(shù)3、樹(shù)杈21、樹(shù)葉94、子鍵值3349，用符號(hào)表示即為：tree[3]、Branch[21]、leaf[94]、subkey[3349]。

2 平衡檢索森林的算法實(shí)現(xiàn)

2.1 數(shù)據(jù)結(jié)構(gòu)

為了便于編程實(shí)現(xiàn)，需要將上述形象的檢索森林，轉(zhuǎn)化為抽象的二級(jí)文件目錄結(jié)構(gòu)。

⑴ 檢索森林對(duì)應(yīng)的根目錄定義為：“D：＼＼SF”。

⑵ 樹(shù)0到樹(shù)31對(duì)應(yīng)的一級(jí)子目錄定義為：“D：＼＼SF＼＼T0”到“D：＼＼SF＼＼T31”。

⑶ 樹(shù)i的樹(shù)杈0到樹(shù)杈31對(duì)應(yīng)的二級(jí)子目錄定義為：“D：＼＼SF＼＼Ti＼＼B0”到“D：＼＼SF＼＼Ti＼＼B31”，i=0 to 31。

⑷ 樹(shù)i的樹(shù)杈j下的128個(gè)文件名定義為：“D：＼＼SF＼＼Ti＼＼Bj＼＼L0.bin”到“D：＼＼SF＼＼Ti＼＼Bj＼＼L127.bin”，i=0 to 31，j=0 to 31。

⑸ 整個(gè)檢索森林就有32*32*128=131072個(gè)子文件，為了查找子鍵值的簡(jiǎn)單，文件采用二進(jìn)制格式，這里，“.bin”的文件擴(kuò)展名特指二進(jìn)制格式。

⑹ 如此龐大數(shù)量的子文件，不論是建立，還是刪除，都需要花費(fèi)一定的時(shí)間，但是，換來(lái)的好處就是每個(gè)文件都很小，檢索起來(lái)非常快。

2.2 算法描述

Step1 初始化檢索森林，只生成兩級(jí)子目錄。

Step2 生成32*32*128個(gè)二進(jìn)制空文件，若原來(lái)文件中有子鍵值記錄，則自動(dòng)清空。

Step3 產(chǎn)生或讀取30位的隨機(jī)數(shù)。

Step4 依次讀取該隨機(jī)數(shù)的前三個(gè)位段，根據(jù)平衡檢索森林的編碼規(guī)則（見(jiàn)表1）拼接構(gòu)造出葉子文件的路徑名。

Step5 打開(kāi)該樹(shù)葉文件。

Step6 取該隨機(jī)數(shù)的最后13位，形成葉子文件的鍵值，順序比較該文件中的全部記錄，若鍵值存在，則碰撞次數(shù)++；若不存在，則將該鍵值添加到該葉子文件尾部。

Step7 關(guān)閉葉子文件。

Step8 終止循環(huán)嗎？if（終止） then {goto Step 10}。

Step9 goto Step 3。

Step10 碰撞率=碰撞次數(shù)/隨機(jī)數(shù)的總數(shù)。

Step11 結(jié)束。

3 效率分析與實(shí)驗(yàn)結(jié)果

3.1 效率分析

假定30位隨機(jī)數(shù)的記錄數(shù)量為N，且每一個(gè)葉子文件的碰撞率檢測(cè)采用簡(jiǎn)單的二進(jìn)制文件順序檢索方法，則每個(gè)葉子文件的記錄數(shù)平均為：M=N/（32*32*128）=N/217。對(duì)于順序文件查找，如果每個(gè)輸入鍵碼都以相同的概率出現(xiàn)，則在一次成功的查找中，鍵碼與順序表中記錄的比較次數(shù)：

C=（1+2+3+4+…+M）/M[9]=（M（M+1）/2）/M

=（M+1）/2=（N/217+1）/2=（N/218+0.5）≈N/218

標(biāo)準(zhǔn)差約為0.289M[10]=0.289*N/217，因此，平衡檢索森林中隨機(jī)數(shù)的平均檢索效率約為N/218。

3.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)條件為個(gè)人臺(tái)式機(jī)，操作系統(tǒng)為Microsoft Windows XP SP3，CPU為Genuine Intel（R） 1.60GHZ，2GB內(nèi)存。對(duì)于平衡檢索森林中龐大數(shù)量的子文件，首次建立過(guò)程需要4分鐘，非首次建立過(guò)程需要3分10秒，刪除過(guò)程需要3分50秒。對(duì)于2560Kbyte的二進(jìn)制隨機(jī)數(shù)文件，需要3小時(shí)45分檢測(cè)完畢。2560Kbyte的二進(jìn)制隨機(jī)數(shù)的檢測(cè)結(jié)果如下：記錄數(shù)=655360，碰撞數(shù)=47，碰撞率=0.000072，合格閾值=0.0001，本次碰撞率測(cè)試合格。

4 結(jié)束語(yǔ)

在海量隨機(jī)數(shù)碰撞率的實(shí)時(shí)檢測(cè)項(xiàng)目中，我們提出了平衡檢索森林的結(jié)構(gòu)與方法，不僅為開(kāi)發(fā)與測(cè)試帶來(lái)了高度的簡(jiǎn)便性與可靠性，而且，為海量隨機(jī)數(shù)碰撞率的檢測(cè)帶來(lái)了極高的效率。但這種結(jié)構(gòu)與方法也存在著一定的問(wèn)題，就是當(dāng)隨機(jī)數(shù)的隨機(jī)性能不是很好的時(shí)候，這個(gè)檢索森林的平衡性會(huì)受到一定程度的影響。下一步的研究重點(diǎn)是將葉子文件記錄查找方法與雜湊（HASH）技術(shù)相結(jié)合，進(jìn)一步提高檢索森林在隨機(jī)數(shù)的隨機(jī)性不是很好狀況下的檢索效率。

參考文獻(xiàn)（References）：

[1] 楊睿.論偽隨機(jī)序列及其應(yīng)用[J].沈陽(yáng)工程學(xué)院學(xué)報(bào)（自然科學(xué)版），2009.5（2）：168

[2] 江裕劍等.計(jì)算機(jī)模擬隨機(jī)數(shù)發(fā)生器的產(chǎn)生、檢驗(yàn)及應(yīng)用[J].成都電訊工程學(xué)院學(xué)報(bào)，1983.1：117

[3] 張廣強(qiáng).均勻隨機(jī)數(shù)發(fā)生器的研究和統(tǒng)計(jì)檢驗(yàn)[D].大連理工大學(xué)碩士學(xué)位論文，2005.

[4] 欒忠蘭等.偽隨機(jī)數(shù)發(fā)生器的統(tǒng)計(jì)性質(zhì)檢驗(yàn)及其應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件，2010.27（10）：168

[5] 盧開(kāi)澄.計(jì)算機(jī)密碼學(xué)（第2版）[M].清華大學(xué)出版社，1998.

[6] （美）Donald E. Knuth著，蘇運(yùn)霖譯.計(jì)算機(jī)程序設(shè)計(jì)藝術(shù) 第3卷排序與查找（第2版）[M].國(guó)防工業(yè)出版社，2003.

[7] （美）Donald E. Knuth著，蘇運(yùn)霖譯.計(jì)算機(jī)程序設(shè)計(jì)藝術(shù) 第3卷排序與查找第2版[M].國(guó)防工業(yè)出版社，2003.

[8] （美）Donald E. Knuth著，蘇運(yùn)霖譯.計(jì)算機(jī)程序設(shè)計(jì)藝術(shù) 第3卷排序與查找（第2版）[M].國(guó)防工業(yè)出版社，2003.

[9] （美）Donald E. Knuth著，蘇運(yùn)霖譯.計(jì)算機(jī)程序設(shè)計(jì)藝術(shù) 第3卷排序與查找（第2版）[M].國(guó)防工業(yè)出版社，2003.

[10] （美）Donald E. Knuth著，蘇運(yùn)霖譯.計(jì)算機(jī)程序設(shè)計(jì)藝術(shù) 第3卷排序與查找（第2版）[M].國(guó)防工業(yè)出版社，2003.