一種高效率的信息檢索算法

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

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

信息時代如何提高信息檢索的效率一直是信息管理人員關(guān)注的問題。提高信息檢索效率的有效途徑是構(gòu)建被檢索信息與其存放地址之間的關(guān)系(HASH)。到目前為止，構(gòu)造HASH函數(shù)的方法很多，常用的方法有:直接定址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法、隨機(jī)數(shù)法等轉(zhuǎn)換算法。但是不論哪種算法都會出現(xiàn)“碰撞” 現(xiàn)象 ， 因而就限制了上述方法的普遍使用。為了解決或減少“碰撞”，我們把HASH的思想和索引順序表檢索的思想，以及二分檢索法的思想結(jié)合起來提出一種基于HASH表的二分檢索法，通過理論分析和實驗證明，該算法檢索效率極高。

一、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)進(jìn)行二分檢索。假設(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]

ad←

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

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

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

三、平均檢索長度的分析

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

（其中N為數(shù)據(jù)量）

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

(m=1，2，…，N)

參考文獻(xià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ū)間）中，再在“塊”中進(jìn)行二分檢索。從而不再需要建立索引順?biāo)鞅頇z索算法中的索引表，也就省去了索引順?biāo)鞅頇z索算法中查找索引表確定所在“塊”的平均檢索長度。

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

3.在理想情況下，即數(shù)據(jù)完全是均勻分布的情況下 ，本算法的平均檢索長度可達(dá)理論極限值 ASL=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é)果。為了對本檢索算法的檢索效率進(jìn)行驗證，我們用VB6.0編寫了本算法以及二分檢索法的程序，將二種檢索算法的平均檢索長度進(jìn)行實際測定，實驗中所用的數(shù)據(jù)由VB6.0的隨時函數(shù)產(chǎn)生，數(shù)據(jù)的范圍為（0～10000），實驗結(jié)果如下表所示：

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

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