孟秀哲　楊棟毅

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

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

中圖分類號：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號：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 引言

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

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

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

1.1 基本思想

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

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

1.2 編碼規(guī)則

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

⑹ 如此龐大數(shù)量的子文件，不論是建立，還是刪除，都需要花費一定的時間，但是，換來的好處就是每個文件都很小，檢索起來非?？臁?/p>

2.2 算法描述

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

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

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

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

Step5 打開該樹葉文件。

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

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

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

Step9 goto Step 3。

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

Step11 結(jié)束。

3 效率分析與實驗結(jié)果

3.1 效率分析

假定30位隨機數(shù)的記錄數(shù)量為N，且每一個葉子文件的碰撞率檢測采用簡單的二進(jìn)制文件順序檢索方法，則每個葉子文件的記錄數(shù)平均為：M=N/（32*32*128）=N/217。對于順序文件查找，如果每個輸入鍵碼都以相同的概率出現(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，因此，平衡檢索森林中隨機數(shù)的平均檢索效率約為N/218。

3.2 實驗結(jié)果

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

4 結(jié)束語

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

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

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

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

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

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

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

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

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

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

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

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