導(dǎo)語(yǔ)：信息檢索分析論文一文來(lái)源于網(wǎng)友上傳，不代表本站觀點(diǎn)，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

一、HASH函數(shù)的構(gòu)造

桶排序法，先把被排數(shù)據(jù)所分布的區(qū)間[Dmin,Dmax](在這里Dmax,Dmin分別為被排數(shù)據(jù)的最大，最小值)劃分成N個(gè)大小相等的子區(qū)間，稱子為“桶”，然后將N個(gè)數(shù)據(jù)根據(jù)其大小分配入相應(yīng)的“桶”內(nèi)（桶[1]，桶[2]，…，桶[N]）。借簽桶排序中將數(shù)據(jù)根據(jù)其大小分配入相應(yīng)“桶”的思想，我們?cè)跈z索時(shí)將已排好序的數(shù)據(jù)也根據(jù)其大小將其分配入相應(yīng)的“桶”內(nèi)，然后再在“桶”內(nèi)進(jìn)行二分檢索。假設(shè)按升序排列的N個(gè)數(shù)據(jù)已存放在data數(shù)組的元素data[0]～data[N-1]中，構(gòu)造一個(gè)HASH函數(shù)為:

（式中Dmax=data[N-1],Dmin=data[0],N為數(shù)據(jù)個(gè)數(shù)）

二、基于HASH函數(shù)的二分檢索算法HS

算法HS使用二個(gè)數(shù)組，data數(shù)組的元素data[0]～data[N-1]中存放按升序排列的N個(gè)數(shù)據(jù),address數(shù)組的元素address[1]～address[N]中用來(lái)存貯經(jīng)HASH函數(shù)轉(zhuǎn)換后得到相同地址的數(shù)據(jù)個(gè)數(shù)。

算法HS

HS1[清address數(shù)組]將ddress[1]～address[N]都置0

HS2[Dmax中置最大值、Dmin中置最小值]Dmax←data[N-1],Dmin←data[0]

HS3[i置初始值]i←0

HS4[求數(shù)據(jù)data[i]的HASH變換后的地址ad]ad

HS5[地址“碰撞”記數(shù)器address[ad]加1]address[ad]←address[ad]+1

HS6[修改i]i←i+1

HS7[比較i與N-1]若i<=N-1，則轉(zhuǎn)HS4，否則轉(zhuǎn)HS8。

HS8[address[0]置初值1]address[0]←1

HS9[j置初始值]j←1

HS10[求地址發(fā)生“碰撞”的數(shù)據(jù)在DATA數(shù)組中的首地址]address[j]=address[j]+address[j-1]

HS11[修改j]j←j+1

HS12[比較j與N]若j<=N則轉(zhuǎn)HS10，否則轉(zhuǎn)HS13。

HS13[輸入一個(gè)被檢索的數(shù)據(jù)X]

HS14[對(duì)被檢索數(shù)據(jù)X用HASH函數(shù)得地址ad]

HS15[確定“塊”的下界low,上界high的值]low←address[ad-1],high←address[ad]-1

HS16[在“塊”內(nèi)進(jìn)行二分檢索]在給定的下界與上界之間進(jìn)行二分檢索，若找到，則返“檢索成功”信息，否則返加回“檢索失敗”信息。

HS17[本算法結(jié)束]

三、平均檢索長(zhǎng)度的分析

在本檢索算法中，首先將被檢索數(shù)據(jù)X經(jīng)HASH函數(shù)轉(zhuǎn)換出一個(gè)地址，根據(jù)這個(gè)地址將被檢索的數(shù)據(jù)直接定位到相應(yīng)的“塊”中，然后在“塊”中進(jìn)行二分檢索。因此通過(guò)對(duì)所有“塊”內(nèi)二分檢索法的平均檢索長(zhǎng)度的計(jì)算就可求出本算法的平均檢索長(zhǎng)度。二分檢索法的平均檢索長(zhǎng)度為：

下面我們來(lái)求本算法的平均檢索長(zhǎng)度。假設(shè)在N個(gè)數(shù)據(jù)均勻分布的情況下，經(jīng)過(guò)本檢索算法中HASH函數(shù)轉(zhuǎn)換，每一個(gè)地址出現(xiàn)的概率相同，都等于1/N，因此，有m個(gè)數(shù)據(jù)轉(zhuǎn)換得到相同地址的概率為：

(m=1,2,…，N)

參考文獻(xiàn)[1]的附錄中已證明：（1）

所以本檢索算法的平均檢索長(zhǎng)度為（2）

由上式(1)和式(2)兩個(gè)公式即可求得本算法的平均檢索長(zhǎng)度，其平均檢索長(zhǎng)度小于1.352(當(dāng)N>100時(shí))。

四、算法分析與實(shí)驗(yàn)結(jié)果

1.本算法的創(chuàng)新之處在于通過(guò)HASH函數(shù)可將被檢索的數(shù)據(jù)X直接位置定位到相應(yīng)的“塊”（通過(guò)HASH函數(shù)轉(zhuǎn)換后的地址相同的數(shù)據(jù)區(qū)間）中,再在“塊”中進(jìn)行二分檢索。從而不再需要建立索引順?biāo)鞅頇z索算法中的索引表,也就省去了索引順?biāo)鞅頇z索算法中查找索引表確定所在“塊”的平均檢索長(zhǎng)度。

2.此方法突破了HASH表的平均檢索長(zhǎng)度是裝填因子(=(表中填人的記錄數(shù))/(哈希表的長(zhǎng)度)的函數(shù),而不是N的函數(shù)的弱點(diǎn)。

3.在理想情況下，即數(shù)據(jù)完全是均勻分布的情況下,本算法的平均檢索長(zhǎng)度可達(dá)理論極限值A(chǔ)SL=1。即使是在最壞的情況下,當(dāng)N個(gè)數(shù)據(jù)經(jīng)HASH函數(shù)轉(zhuǎn)換后的地址均相同，所有數(shù)據(jù)均落在同一個(gè)“塊”中,其平均檢索長(zhǎng)度ASL也只會(huì)下降到二分檢索法時(shí)的平均檢索長(zhǎng)度。

4.本算法對(duì)于均勻分布的數(shù)據(jù)是極為有效的,通過(guò)計(jì)算得出其平均檢索長(zhǎng)度小于1.352(N>100時(shí))，因此檢索效率很高。

5.本算法中的步驟HS1～HS12僅僅是為檢索作的準(zhǔn)備工作，相當(dāng)于初始化的工作，只需在檢索開始時(shí)做一次即可。

6.實(shí)驗(yàn)結(jié)果。為了對(duì)本檢索算法的檢索效率進(jìn)行驗(yàn)證，我們用VB6.0編寫了本算法以及二分檢索法的程序，將二種檢索算法的平均檢索長(zhǎng)度進(jìn)行實(shí)際測(cè)定，實(shí)驗(yàn)中所用的數(shù)據(jù)由VB6.0的隨時(shí)函數(shù)產(chǎn)生，數(shù)據(jù)的范圍為（0～10000），實(shí)驗(yàn)結(jié)果如下表所示：

VB6.0程序二種檢索算法平均檢索長(zhǎng)度對(duì)比表

我們?cè)趯?shí)驗(yàn)中測(cè)定平均檢索長(zhǎng)度時(shí)，通過(guò)程序?qū)λ袛?shù)據(jù)逐個(gè)檢索，統(tǒng)計(jì)出檢索完所有數(shù)據(jù)需進(jìn)行比較的總次數(shù)再除以數(shù)據(jù)總數(shù)后得出。上表中當(dāng)N=100時(shí)，本算法實(shí)際測(cè)定的值（1.38）與理論計(jì)算(1.352)略有誤差，原因是我們用VB6.0中的隨機(jī)函數(shù)產(chǎn)生的隨機(jī)數(shù)在數(shù)據(jù)量較小時(shí)分布不一定很均勻。從表1中可以看到:當(dāng)數(shù)據(jù)量稍大一些（N>100）,本算法的平均檢索長(zhǎng)度的實(shí)測(cè)結(jié)果完全與理論分析一對(duì)致，并且遠(yuǎn)小于二分檢索法的平均檢索長(zhǎng)度。本算法的平均檢索長(zhǎng)度隨著數(shù)據(jù)量N的增加幾乎不變。

[摘要]構(gòu)造一個(gè)新的HASH函數(shù)，結(jié)合索引順序表和二分檢索法的思想，提出了一種高效率的信息檢索算法，通過(guò)理論計(jì)算和實(shí)驗(yàn)證明此算法的平均檢索長(zhǎng)度小于1.352(N>100)。

[關(guān)鍵詞]HASH函數(shù)檢索平均檢索長(zhǎng)度