文档介绍：一种高效率的信息检索算法
一、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]
HS15 [确定“块”的下界low,上界high的值] low←address[ad-1],high←address[ad]-1
HS16 [在“块”内进行二分检索] 在给定的下界与上界之间进行二分检索,若找到,则返“检索成功”信息,否则返加回“检索失败”信息。
HS17 [本算法结束]
(m=1,2,…,N)
参考文献[1] 的附录中已证明: (1)
所以本检索算法的平均检索长度为(2)
由上式(1)和式(2)两个公式即可求得本算法的平均检索长度,(当N>100时)。
四、算法分析与实验结果
“块”(通过HASH函数转换后的地址相同的数据区间)中,再在“块”中进行二分检索。从而不再需要建立索引顺索表检索算法中的索引表,也就省去了索引顺索表检索算法中查