资源描述：
《一种高效率的信息检索算法 》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一种高效率的信息检索算法 [摘要]构造一个新的HASH函数，结合索引顺序表和二分检索法的思想，提出了一种高效率的信息检索算法，通过理论计算和实验证明此算法的平均检索长度小于1.352(N>100)。 [关键词]HASH函数检索平均检索长度 信息时代如何提高信息检索的效率一直是信息管理人员关注的问题。提高信息检索效率的有效途径是构建被检索信息与其存放地址之间的关系(HASH)。到目前为止，构造HASH函数的方法很多,常用的方法有:直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法等转换算法。但是不论哪种算法都会出现“碰撞”现象,因
2、而就限制了上述方法的普遍使用。为了解决或减少“碰撞”,我们把HASH的思想和索引顺序表检索的思想,以及二分检索法的思想结合起来提出一种基于HASH表的二分检索法，通过理论分析和实验证明，该算法检索效率极高。 一、HASH函数的构造 桶排序法，先把被排数据所分布的区间[Dmin,Dmax](在这里Dmax,Dmin分别为被排数据的最大，最小值)划分成N个大小相等的子区间，称子为“桶”，然后将N个数据根据其大小分配入相应的“桶”内（桶[1]，桶[2]，…，桶[N]）。借签桶排序中将数据根据其大小分配入相应“桶”的思想，我们在检索时将已排好序的数
3、据也根据其大小将其分配入相应的“桶”内，然后再在“桶”内进行二分检索。假设按升序排列的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 HS
4、1[清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
5、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[确定“块”的下界lo个数据转换得到相同地址的概率为： (m=1,2,…，N) 四、算法分析与实验结果 1.本算法的创新之处在于通过HASH函数可将被检索的数据X直接位置
6、定位到相应的“块”（通过HASH函数转换后的地址相同的数据区间）中,再在“块”中进行二分检索。从而不再需要建立索引顺索表检索算法中的索引表,也就省去了索引顺索表检索算法中查找索引表确定所在“块”的平均检索长度。 2.此方法突破了HASH表的平均检索长度是装填因子(=(表中填人的记录数)/(哈希表的长度)的函数,而不是N的函数的弱点。 3.在理想情况下，即数据完全是均匀分布的情况下,本算法的平均检索长度可达理论极限值ASL=1。即使是在最坏的情况下,当N个数据经HASH函数转换后的地址均相同，所有数据均落在同一个“块”中,其平均检索长度ASL也只会下
7、降到二分检索法时的平均检索长度。 4.本算法对于均匀分布的数据是极为有效的,通过计算得出其平均检索长度小于1.352(N>100时)，因此检索效率很高。 5.本算法中的步骤HS1～HS12仅仅是为检索作的准备工作，相当于初始化的工作，只需在检索开始时做一次即可。 6.实验结果。为了对本检索算法的检索效率进行验证，我们用VB6.0编写了本算法以及二分检索法的程序，将二种检索算法的平均检索长度进行实际测定，实验中所用的数据由VB6.0的随时函数产生，数据的范围为（0～10000），实验结果如下表所示： VB6.0程序二种检索算法平均检索长度对
8、比表 我们在实验中测定平均检索长度时，通过程序对所有数据逐个检索，统计出检索完所有数据需进行
