一种信息检索算法.doc

一种高效率的信息检索算法来源：中国论文下载中心 08-12-09 15:43:00 作者：陶明华刘秋生编辑：studa20摘要 构造一个新的HASH函数，结合索引顺序表和二分检索法的思想，提出了一种高效率的信息检索算法，通过理论计算和实验证明此算法的平均检索长度小于1.352(N100)。 关键词 HASH函数检索平均检索长度 信息时代如何提高信息检索的效率一直是信息管理人员关注的问题。提高信息检索效率的有效途径是构建被检索信息与其存放地址之间的关系(HASH)。到目前为止，构造HASH函数的方法很多,常用的方法有:直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法等转换算法。但是不论哪种算法都会出现“碰撞” 现象 , 因而就限制了上述方法的普遍使用。为了解决或减少“碰撞”,我们把HASH的思想和索引顺序表检索的思想,以及二分检索法的思想结合起来提出一种基于HASH表的二分检索法，通过理论分析和实验证明，该算法检索效率极高。 一、HASH函数的构造 桶排序法，先把被排数据所分布的区间Dmin,Dmax(在这里Dmax,Dmin分别为被排数据的最大，最小值)划分成N个大小相等的子区间，称子为“桶”，然后将N个数据根据其大小分配入相应的“桶”内（桶1，桶2，桶N）。借签桶排序中将数据根据其大小分配入相应“桶”的思想，我们在检索时将已排好序的数据也根据其大小将其分配入相应的“桶”内，然后再在“桶”内进行二分检索。假设按升序排列的N个数据已存放在data数组的元素 data0dataN-1中，构造一个HASH 函数为: （式中Dmax=dataN-1,Dmin=data0,N为数据个数） 二、基于HASH函数的二分检索算法HS 算法HS使用二个数组，data数组的元素 data0dataN-1中存放按升序排列的N个数据,address数组的元素address1addressN中用来存贮经HASH函数转换后得到相同地址的数据个数。 算法HS HS1清address数组将ddress1addressN都置0 HS2Dmax中置最大值、Dmin中置最小值DmaxdataN-1,Dmindata0 HS3i置初始值 i0 HS4求数据datai的HASH变换后的地址adadHS5地址“碰撞”记数器addressad加1 addressad addressad+1 HS6修改i ii+1 HS7比较i与N-1 若i=N-1，则转HS4，否则转HS8。 HS8address0置初值1address0 1 HS9j置初始值j1 HS10 求地址发生“碰撞”的数据在DATA数组中的首地址addressj=addressj+addressj-1 HS11修改j j j+1 HS12 比较j与N 若j100时)。 四、算法分析与实验结果 1.本算法的创新之处在于通过HASH函数可将被检索的数据X直接位置定位到相应的“块”（通过HASH函数转换后的地址相同的数据区间）中,再在“块”中进行二分检索。从而不再需要建立索引顺索表检索算法中的索引表,也就省去了索引顺索表检索算法中查找索引表确定所在“块”的平均检索长度。 2.此方法突破了 HASH 表的平均检索长度是装填因子(=( 表中填人的记录数 )/( 哈希表的长度 ) 的函数 , 而不是 N 的函数的弱点。 3.在理想情况下，即数据完全是均匀分布的情况下 ,本算法的平均检索长度可达理论极限值 ASL=1。即使是在最坏的情况下, 当 N 个数据经HASH 函数转换后的地址均相同，所有数据均落在同一个“块”中, 其平均检索长度 ASL 也只会下降到二分检索法时的平均检索长度。 4.本算法对于均匀分布的数据是极为有效的, 通过计算得出其平均检索长度小于1.352(N100时)，因此检索效率很高。 5.本算法中的步骤HS1HS12仅仅是为检索作的准备工作，相当于初始化的工作，只需在检索开始时做一次即可。 6.实验结果。为了对本检索算法的检索效率进行验证，我们用VB6.0编写了本算法以及二分检索法的程序，将二种检索算法的平均检索长度进行实际测定，实验中所用的数据由VB6.0的随时函数产生，数据的范围为（010000），实验结果如下表所示： VB6.0程序二种检索算法平均检索长度对比表 我们在实验中测定平均检索长度时，通过程序对所有数据逐个检索，统计出检索完所有数据需进行比较的总次数再除以数据总数后得出。上表中当N=100时，本算法实际测定的值（1.38）与理论计算(1.352)略有误差，原因是我们用VB6.0中的随机函数产生的随机数在数据量较小时分布不一定很均匀。从表1中可以看到:当数据量稍大一些（N100）