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

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

[關鍵詞] HASH函數檢索平均檢索長度

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

一、HASH函數的構造

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

（式中Dmax=data[N-1]，Dmin=data[0]，N為數據個數）

二、基于HASH函數的二分檢索算法HS

算法HS使用二個數組，data數組的元素 data[0]～data[N-1]中存放按升序排列的N個數據，address數組的元素address[1]～address[N]中用來存貯經HASH函數轉換后得到相同地址的數據個數。

算法HS

HS1[清address數組]將ddress[1]～address[N]都置0

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

HS3[i置初始值] i←0

HS4[求數據data[i]的HASH變換后的地址ad]ad←

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

HS6[修改i] i←i+1

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

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

HS9[j置初始值]j←1

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

HS11[修改j] j ←j+1

HS12 [比較j與N] 若j<=N 則轉HS10，否則轉HS13。

HS13 [輸入一個被檢索的數據 X]

HS14[對被檢索數據X 用HASH 函數得地址ad]

ad←

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

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

HS17 [本算法結束]

三、平均檢索長度的分析

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

（其中N為數據量）

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

(m=1，2，…，N)

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

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

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

四、算法分析與實驗結果

1.本算法的創新之處在于通過HASH函數可將被檢索的數據X直接位置定位到相應的“塊”（通過HASH函數轉換后的地址相同的數據區間）中，再在“塊”中進行二分檢索。從而不再需要建立索引順索表檢索算法中的索引表，也就省去了索引順索表檢索算法中查找索引表確定所在“塊”的平均檢索長度。

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

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

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

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

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

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

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