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

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

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

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

一、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]

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)度為：

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

下面我們來(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á)理論極限值 ASL=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)于初始化的工作，只需在檢索開(kāi)始時(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的增加幾乎不變。