文档介绍：一种高效率的信息检索算法
[摘要]构造一个新的HASH函数,结合索引顺序表和二分检索法的思想,提出了,通过理论计算和实验证明此算法的平均检索长度小于(N>100)。
[关键词]HASH函数检索平均检索长度
信息时代如何提高信息检索的效率一直是信息管理人员关注的问题。提高信息检索效率的有效途径是构建被检索信息与其存放地址之间的关系(HASH)。到目前为止,构造HASH函数的方法很多徙,常用的方法有:直接定址法、数字分析氅法、平方取中法、折叠法、除留余数法、甬随机数法等转换算法。但是不论哪种算法撬都会出现“碰撞”现象,因而就限制了上Ⅵ述方法的普遍使用。为了解决或减少“碰茯撞”,我们把HASH的思想和索引顺序弹表检索的思想,以及二分检索法的思想结饯合起来提出一种基于HASH表的二分检效索法,通过理论分析和实验证明,该算法尝检索效率极高。
一、HASH函数的构悄造
桶排序法,先把被排数据所分布的区藐间[Dmin,Dmax](在这里Dm喱ax,Dmin分别为被排数据的最大,岵最小值)划分成N个大小相等的子区间,撵称子为“桶”,然后将N个数据根据其大裳小分配入相应的“桶”内。借签桶排序中
勰将数据根据其大小分配入相应“桶”的思约想,我们在检索时将已排好序的数据也根觏据其大小将其分配入相应的“桶”内,然⌒后再在“桶”内进行二分检索。假设按升⒍序排列的N个数据已存放在data数组┇的元素data[0]~data[N-a1]中,构造一个HASH函数为:
二啐、基于HASH函数的二分检索算法HS
算法HS使用二个数组,data数组的薮元素data[0]~data[N-1整]中存放按升序排列的N个数据,add仞ress数组的元素address[1愿]~address[N]中用来存贮经褙HASH函数转换后得到相同地址的数据荞个数。
算法HS
HS1[清addr渺ess数组]将ddress[1]~a镪ddress[N]都置0
HS2[D^max中置最大值、Dmin中置最小值宣]Dmax←data[N-1],Dm纱in←data[0]
HS3[i置初征始值]i←0
HS4[求数据data[i]的HASH变换后的地址ad]a籴d
HS5[地址“碰撞”记数器address[ad]加1]address杓[ad]←address[ad]+1
HS6[修改i]i←i+1
HS7[砌比较i与N-1]若i100时)。
四宜、算法分析与实验结果
“块”中,再在“块”中进行二分检索。从而不再裎需要建立索引顺索表检索算法中的索引表,也就省去了索引顺索表检索算法中查找索引表确定所在“块”的平均检索长度。
长度是装填因子(=(表中填人的记录数墙)/(哈希表的长度)的函数,而不是N骰的函数的弱点。
,即弘数据完全是均匀分布的情况下,本算法的拯平均检索长度可达理论极限值ASL=1闷。即使是在