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

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

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

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

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

算法HS使用二個數(shù)組，data數(shù)組的元素data[0]～data[N-1]中存放按升序排列的N個數(shù)據(jù),address數(shù)組的元素address[1]～address[N]中用來存貯經(jīng)HASH函數(shù)轉(zhuǎn)換后得到相同地址的數(shù)據(jù)個數(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[輸入一個被檢索的數(shù)據(jù)X]

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

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

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

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

三、平均檢索長度的分析

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

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

(m=1,2,…，N)

參考文獻[1]的附錄中已證明：（1）

所以本檢索算法的平均檢索長度為（2）

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

四、算法分析與實驗結(jié)果

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

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

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

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

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

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

VB6.0程序二種檢索算法平均檢索長度對比表

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

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

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