文档介绍：一种高效率的信息检索算法
[摘要] 构造一个新的HASH函数,结合索引顺序表和二分检索法的思想,提出了一种高效率的信息检索算法,(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]
HS15 [确定“块”的下界low,上界high的值] low←ad