九章节检索.ppt
《九章节检索.ppt》由会员分享,可在线阅读,更多相关《九章节检索.ppt(138页珍藏版)》请在三一文库上搜索。
1、第九章 检索,任课教员:张 铭 http:/ 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究,北京大学信息学院 版权所有,转载或翻印必究 Page 2,9.1 基本概念 9.2 线性表的检索 9.3 散列表的检索,北京大学信息学院 版权所有,转载或翻印必究 Page 3,基本概念,检索:在一组记录集合中找到关键码值等于给定值的某个记录,或者找到关键码值符合特定条件的某些记录的过程 检索的效率非常重要 尤其对于大数据量 需要对数据进行特殊的存储处理,北京大学信息学院 版权所有,转载或翻印必究 Page 4,基本概念(续),预排序 排序算法本身比较费时 只是预处理(在
2、检索之前已经完成) 建立索引 检索时充分利用辅助索引信息 牺牲一定的空间 从而提高检索效率,北京大学信息学院 版权所有,转载或翻印必究 Page 5,基本概念(续),散列技术 把数据组织到一个表中 根据关键码的值来确定表中每个记录的位置 缺点: 不适合进行范围查询 一般也不允许出现重复关键码 当散列方法不适合于基于磁盘的应用程序时,我们可以选择B树方法,北京大学信息学院 版权所有,转载或翻印必究 Page 6,平均检索长度(ASL),关键码的比较 检索运算的主要操作 平均检索长度(Average Search Length) 检索过程中对关键码需要执行的平均比较次数 是衡量检索算法优劣的时间标
3、准,北京大学信息学院 版权所有,转载或翻印必究 Page 7,平均检索长度,ASL是存储结构中对象总数n的函数,其定义为: Pi 为检索第i个元素的概率 Ci 为找到第i个元素所需的关键码值与给定值的比较次数,北京大学信息学院 版权所有,转载或翻印必究 Page 8,平均检索长度,假设线性表为(a, b, c)检索a、b、c的概率分别为0.4、0.1、0.5 顺序检索算法的平均检索长度为0.41+0.12+0.53 = 2.1 即平均需要2.1次给定值与表中关键码值的比较才能找到待查元素,北京大学信息学院 版权所有,转载或翻印必究 Page 9,衡量一个检索算法还需要考虑 算法所需的存储量 算
4、法的复杂性 .,北京大学信息学院 版权所有,转载或翻印必究 Page 10,9.1 基于线性表的检索,9.1.1 顺序检索 9.1.2 二分检索 9.1.3 分块检索,北京大学信息学院 版权所有,转载或翻印必究 Page 11,9.1.1 顺序检索,针对线性表里的所有记录,逐个进行关键码和给定值的比较 。 若某个记录的关键码和给定值比较相等,则检索成功 ; 否则检索失败(找遍了仍找不到)。 存储:可以顺序、链接 排序要求:无,北京大学信息学院 版权所有,转载或翻印必究 Page 12,顺序检索算法,/代码9-1 顺序检索的存储结构类型定义 template class Item public:
5、 Item(Type value):key(value) Type getKey() return key; /获取关键码值; void setKey(Type k) key=k; /设置关键码 private: Type key; /关键码域 string other; /其它域 ; vector* dataList;,北京大学信息学院 版权所有,转载或翻印必究 Page 13,“监视哨”顺序检索算法,位置0用来做监视哨,位置1到length用来存储实际元素 检索成功时返回元素位置,检索失败时统一返回0; /代码9-2 顺序检索算法 template int SeqSearch(vector
6、* /返回元素位置 ,北京大学信息学院 版权所有,转载或翻印必究 Page 14,顺序检索性能分析,检索成功 假设检索每个关键码是等概率的,Pi = 1/n 检索失败 假设检索失败时都需要比较n+1次(设置了一个监视哨),北京大学信息学院 版权所有,转载或翻印必究 Page 15,顺序检索性能分析(续),平均检索长度 假设检索成功的概率为p,检索失败的概率为q=(1-p),则平均检索长度为 (n+1)/2 ASL (n+1) 优缺点 优点:插入元素可以直接加在表尾(1) 缺点:检索时间太长(n),北京大学信息学院 版权所有,转载或翻印必究 Page 16,9.1.2 二分检索法,有序表:线性表
7、中所有数据元素按关键码值递增(或递减)的次序排列 在有序表的存储表示下,检索可以用效率更高的二分检索法实现。,北京大学信息学院 版权所有,转载或翻印必究 Page 17,9.1.2 二分法检索,有序表中所有元素按关键码值递增(或递减)的次序排列 将表中任一元素dataListi的关键码值Key与给定值K比较, 可根据三种比较结果区分出三种情况(以递增为例): (1) Key = K,检索成功,dataListi即为待查元素 (2) Key K,说明待查元素若在表中,且一定排在dataListi之前 (3) Key K,说明待查元素若在表中,且一定排在dataListi之后 因此,在一次比较之后
8、,若没有找到待查元素(即情况1未出现),则可根据比较结果缩小进一步检索的区间,北京大学信息学院 版权所有,转载或翻印必究 Page 18,二分法检索算法,/代码9-3 二分检索算法 template int BinSearch (vector* /检索失败,返回0 ,北京大学信息学院 版权所有,转载或翻印必究 Page 19,检索关键码18。low=1; high=9; K=18 第一次:mid=5; array5=3518 high=4; (low=1) 第二次:mid=2; array2=1718 low=3; (high=4) 第三次:mid=3; array3=18=18 mid=3;
9、return 8,二分法检索图示,北京大学信息学院 版权所有,转载或翻印必究 Page 20,二分法检索性能分析,最大检索长度为 失败的检索长度是 或,北京大学信息学院 版权所有,转载或翻印必究 Page 21,二分法检索性能分析(续),成功的平均检索长度为: (n 50) 优缺点 优点:平均检索长度与最大检索长度相近,检索速度快 缺点:要排序、顺序存储,不易更新(插/删),北京大学信息学院 版权所有,转载或翻印必究 Page 22,9.1.3 分块检索,顺序与二分法的折衷 既有较快的检索 又有较灵活的更改,北京大学信息学院 版权所有,转载或翻印必究 Page 23,分块检索思想,“按块有序”
10、 设线性表中共有n个数据元素,将表分成b块 不需要均匀 每一块可能不满 每一块中的关键码不一定有序 但前一块中的最大关键码必须小于后一块中的最小关键码,北京大学信息学院 版权所有,转载或翻印必究 Page 24,索引表 各块中的最大关键码 及各块起始位置 可能还需要块中元素个数(每一块可能不满) 索引表是一个递增有序表 由于表是分块有序的,北京大学信息学院 版权所有,转载或翻印必究 Page 25,分块检索分两个阶段,(1)确定待查元素所在的块 (2)在块内检索待查的元素,北京大学信息学院 版权所有,转载或翻印必究 Page 26,分块检索索引顺序结构,索引表中每个索引项有两个域 块内最大关键
11、码 块起始位置,北京大学信息学院 版权所有,转载或翻印必究 Page 27,分块检索性能分析,分块检索为两级检索 先在索引表中确定待查元素所在的块; 设在索引表中确定块号的时间开销是ASLb 然后在块内检索待查的元素。 在块中查找记录的时间开销为ASLw ASL(n) = ASLb + ASLw,北京大学信息学院 版权所有,转载或翻印必究 Page 28,分块检索性能分析(续1),索引表是按块内最大关键码有序的,且长度也不大,可以二分检索,也可以顺序检索 各子表内各个记录不是按记录关键码有序,只能顺序检索,北京大学信息学院 版权所有,转载或翻印必究 Page 29,分块检索性能分析(续2),假
12、设在索引表中用顺序检索,在块内也用顺序检索 当s= 时,ASL取最小值, ASL = +1 ,北京大学信息学院 版权所有,转载或翻印必究 Page 30,分块检索性能分析(续3),当n=10,000时 顺序检索5,000次 二分法检索14次 分块检索100次 如果数据块(子表)存放在外存时,还会受到页块大小的制约 此时往往以外存一个/读取的数据(一页)作为一块,北京大学信息学院 版权所有,转载或翻印必究 Page 31,分块检索性能分析(续4),若采用二分法检索确定记录所在的子表,则检索成功时的平均检索长度为 ASL= ASLb + ASLw log2 (b+1)-1 + (s+1)/2 lo
13、g2(1+n / s ) + s/2,北京大学信息学院 版权所有,转载或翻印必究 Page 32,分块检索的优缺点,优点: 插入、删除相对较易 没有大量记录移动 缺点: 增加一个辅助数组的存储空间 初始线性表分块排序 当大量插入/删除时,或结点分布不均匀时,速度下降,北京大学信息学院 版权所有,转载或翻印必究 Page 33,9.2 散列检索,基于关键码比较的检索 顺序检索,=, != 二分法、树型 , = , 检索是直接面向用户的操作 当问题规模n很大时,上述检索的时间效率可能使得用户无法忍受 最理想的情况 根据关键码值,直接找到记录的存储地址 不需要把待查关键码与候选记录集合的某些记录进行
14、逐个比较,北京大学信息学院 版权所有,转载或翻印必究 Page 34,例如,读取指定下标的数组元素 根据数组的起始存储地址、以及数组下标值而直接计算出来的,所花费的时间是O(1) 与数组元素个数的规模n无关 受此启发,计算机科学家发明了散列方法 散列是一种重要的存储方法 也是一种常见的检索方法,北京大学信息学院 版权所有,转载或翻印必究 Page 35,散列基本思想,一个确定的函数关系h 以结点的关键码K为自变量 函数值h(K)作为结点的存储地址 检索时也是根据这个函数计算其存储位置 通常散列表的存储空间是一个一维数组 散列地址是数组的下标,北京大学信息学院 版权所有,转载或翻印必究 Page
15、 36,例9.1:已知线性表关键码集合为: S = and, begin, do, end, for, go, if, repeat, then, until, while 可设散列表为: char HT2268; 散列函数H(key)的值,取为关键码key中的第一个字母在字母表a, b, c, ., z中的序号,即: H(key)=key0 a,北京大学信息学院 版权所有,转载或翻印必究 Page 37,北京大学信息学院 版权所有,转载或翻印必究 Page 38,例9.2:在集合S中增加4个关键码,集合S1 = S + else, array, with, up 要修改散列函数:散列函数的值
16、为key中首尾字母在字母表中序号的平均值,即: int H3(key) char key; int i; i = 0; while (i8) return(key0 + key(i-1) 2*a) /2 ) ,北京大学信息学院 版权所有,转载或翻印必究 Page 39,北京大学信息学院 版权所有,转载或翻印必究 Page 40,负载因子=n/m 散列表的空间大小为m 填入表中的结点数为n 冲突 某个散列函数对于不相等的关键码计算出了相同的散列地址 在实际应用中,不产生冲突的散列函数极少存在 同义词 发生冲突的两个关键码,北京大学信息学院 版权所有,转载或翻印必究 Page 41,采用散列技术时
17、需要考虑的两个首要问题是: (1)如何构造(选择)使结点“分布均匀”的散列函数? (2)一旦发生冲突,用什么方法来解决? 还需考虑散列表本身的组织方法,北京大学信息学院 版权所有,转载或翻印必究 Page 42,9.2.1 散列函数,散列函数:把关键码值映射到存储位置的函数,通常用h来表示 Address Hash ( key ),北京大学信息学院 版权所有,转载或翻印必究 Page 43,散列函数的选取原则,运算尽可能简单 函数的值域必须在表长的范围内 尽可能使得关键码不同时,其散列函数值亦不相同,北京大学信息学院 版权所有,转载或翻印必究 Page 44,需要考虑各种因素,关键码长度 散列
18、表大小 关键码分布情况 记录的检索频率 ,北京大学信息学院 版权所有,转载或翻印必究 Page 45,常用散列函数选取方法,除余法 乘余取整法 平方取中法 数字分析法 基数转换法 折叠法 ELFhash字符串散列函数,北京大学信息学院 版权所有,转载或翻印必究 Page 46,9.2.1.1 除余法,除余法:用关键码x除以M(往往取散列表长度),并取余数作为散列地址。散列函数为: h(x) x mod M 通常选择一个质数作为M值 函数值依赖于自变量x的所有位,而不仅仅是最右边k个低位 增大了均匀分布的可能性,北京大学信息学院 版权所有,转载或翻印必究 Page 47,若把M设置为偶数 x是偶
19、数,h(x)也是偶数 x是奇数,h(x)也是奇数 缺点:分布不均匀 如果偶数关键码比奇数关键码出现的概率大,那么函数值就不能均匀分布 反之亦然,北京大学信息学院 版权所有,转载或翻印必究 Page 48,若把M设置为2的幂 那么,h(x)x mod 2k 仅仅是x(用二进制表示)最右边的k个位(bit) 若把M设置为10的幂 那么,h(x)x mod 10k 仅仅是x(用十进制表示)最右边的k个十进制位(digital) 缺点:散列值不依赖于x的全部比特位,北京大学信息学院 版权所有,转载或翻印必究 Page 49,除余法的潜在缺点 连续的关键码映射成连续的散列值 虽然能保证连续的关键码不发生
20、冲突 但也意味着要占据连续的数组单元 可能导致程序性能的降低,北京大学信息学院 版权所有,转载或翻印必究 Page 50,9.2.1.2 乘余取整法,先让关键码 key 乘上一个常数A (0A 1),提取乘积的小数部分 然后,再用整数 n 乘以这个值,对结果向下取整,把它做为散列的地址 散列函数为: hash ( key ) = n * ( A * key % 1 ) “A * key % 1”表示取 A * key 小数部分: A * key % 1 = A * key - A * key ,北京大学信息学院 版权所有,转载或翻印必究 Page 51,乘余取整法示例,设关键码 key = 1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 章节 检索
链接地址:https://www.31doc.com/p-3161293.html