北大数据结构与算法课件09检索

数据结构与算法第九章检索信息科学与技术学院网络与信息系统研究所北京大学信息学院张铭编写©版权所有，转载或翻印必究Page2第九章检索„基本概念„9.1线性表的检索„9.2集合的检索„9.3散列表的检索„9.4总结北京大学信息学院张铭编写©版权所有，转载或翻印必究Page3基本概念„检索：在一组记录集合中找到关键码值等于给定值的某个记录，或者找到关键码值符合特定条件的某些记录的过程„检索的效率非常重要„尤其对于大数据量„需要对数据进行特殊的存储处理北京大学信息学院张铭编写©版权所有，转载或翻印必究Page4基本概念（续）„预排序„排序算法本身比较费时„只是预处理（在检索之前已经完成）„建立索引„检索时充分利用辅助索引信息„牺牲一定的空间„从而提高检索效率北京大学信息学院张铭编写©版权所有，转载或翻印必究Page5基本概念（续）„散列技术„把数据组织到一个表中„根据关键码的值来确定表中每个记录的位置„缺点：„不适合进行范围查询„一般也不允许出现重复关键码„当散列方法不适合于基于磁盘的应用程序时，我们可以选择B树方法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page6平均检索长度（ASL）„关键码的比较：检索运算的主要操作„平均检索长度(AverageSearchLength)„检索过程中对关键码的平均比较次数„衡量检索算法优劣的时间标准1niiiASLPC==∑Pi为检索第i个元素的概率Ci为找到第i个元素所需的关键码值与给定值的比较次数北京大学信息学院张铭编写©版权所有，转载或翻印必究Page7平均检索长度的例子„假设线性表为（a,b,c）检索a、b、c的概率分别为0.4、0.1、0.5„顺序检索算法的平均检索长度为0.4×1+0.1×2+0.5×3=2.1„即平均需要2.1次给定值与表中关键码值的比较才能找到待查元素北京大学信息学院张铭编写©版权所有，转载或翻印必究Page8检索算法评估的几个问题„衡量一个检索算法还需要考虑„算法所需的存储量„算法的复杂性„...北京大学信息学院张铭编写©版权所有，转载或翻印必究Page99.1基于线性表的检索„9.1.1顺序检索„9.1.2二分检索„9.1.3分块检索北京大学信息学院张铭编写©版权所有，转载或翻印必究Page109.1.19.1.1顺序检索顺序检索„针对线性表里的所有记录，逐个进行关键码和给定值的比较。„若某个记录的关键码和给定值比较相等，则检索成功；„否则检索失败(找遍了仍找不到)。„存储：可以顺序、链接„排序要求：无北京大学信息学院张铭编写©版权所有，转载或翻印必究Page11顺序检索算法templateclassTypeclassItem{public:Item(Typevalue):key(value){}TypegetKey(){returnkey;}//取关键码值;voidsetKey(Typek){key=k;}//置关键码private:Typekey;//关键码域stringother;//其它域};vectorItemType*dataList;北京大学信息学院张铭编写©版权所有，转载或翻印必究Page12“监视哨”顺序检索算法„检索成功返回元素位置，检索失败统一返回0;templateclassTypeintSeqSearch(vectorItemType*&dataList,intlength,Typek){inti=length;//将第0个元素设为待检索值dataList[0]-setKey(k);//设监视哨while(dataList[i]-getKey()!=k)i--;returni;//返回元素位置}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page13顺序检索性能分析„检索成功假设检索每个关键码是等概率的，Pi=1/n„检索失败假设检索失败时都需要比较n+1次（设置了一个监视哨）Piniinnniininin·()()−=−∑=−=−∑==+=∑01101121北京大学信息学院张铭编写©版权所有，转载或翻印必究Page14顺序检索平均检索长度„假设检索成功的概率为p，检索失败的概率为q=(1-p)„（n+1)/2ASL(n+1)1ASL(1)21(1)(1)2(1)(1/2)npqnnppnnp+=⋅+⋅++=⋅+−+=+−北京大学信息学院张铭编写©版权所有，转载或翻印必究Page15顺序检索优缺点„优点：插入元素可以直接加在表尾Θ(1)„缺点：检索时间太长Θ(n)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page169.1.2二分检索法„将任一元素dataList[i].Key与给定值K比较„三种情况：（1）Key=K，检索成功，返回dataList[i]（2）KeyK，若有则一定排在dataList[i]]前（3）KeyK，若右则一定排在dataList[i]后„缩小进一步检索的区间北京大学信息学院张铭编写©版权所有，转载或翻印必究Page17二分法检索算法templateclassTypeintBinSearch(vectorItemType*&dataList,intlength,Typek){intlow=1,high=length,mid;while(low=high){mid=(low+high)/2;if(kdataList[mid]-getKey())high=mid-1;//右缩检索区间elseif(kdataList[mid]-getKey())low=mid+1;//左缩检索区间elsereturnmid;//成功返回位置}return0;//检索失败，返回0}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page18检索关键码18low=1high=9K=18第一次：mid=5;array[5]=3518high=4;(low=1)第二次：mid=2;array[2]=1718low=3;(high=4)第三次：mid=3;array[3]=18=18mid=3；return8二分法检索图示35123456789152251608893lowmidhigh1817北京大学信息学院张铭编写©版权所有，转载或翻印必究Page19二分法检索性能分析„昀大检索长度为„失败的检索长度是„停止在内部叶结点或„停止在外部空结点，则加1⎣⎦）（1log2+n⎡⎤）（1log2+n15182251789213488609335175⎡⎤）（1log2+n北京大学信息学院张铭编写©版权所有，转载或翻印必究Page20二分法检索性能分析（续）„成功的平均检索长度为：(n50)„优缺点„优点：平均与昀大检索长度相近，检索速度快„缺点：要排序、顺序存储，不易更新(插/删)11ASL(2)11log(1)12log(1)12jiininnnn−=⋅∑=+=+−≈+−北京大学信息学院张铭编写©版权所有，转载或翻印必究Page219.1.3分块检索„顺序与二分法的折衷„既有较快的检索„又有较灵活的更改北京大学信息学院张铭编写©版权所有，转载或翻印必究Page22分块检索思想„“按块有序”„设线性表中共有n个数据元素，将表分成b块„不需要均匀„每一块可能不满„每一块中的关键码不一定有序„但前一块中的昀大关键码必须小于后一块中的昀小关键码北京大学信息学院张铭编写©版权所有，转载或翻印必究Page23索引表„索引表„各块中的昀大关键码„及各块起始位置„可能还需要块中元素个数（每一块可能不满）„索引表是一个递增有序表„由于表是分块有序的北京大学信息学院张铭编写©版权所有，转载或翻印必究Page24分块检索分两个阶段„（1）确定待查元素所在的块„（2）在块内检索待查的元素分块检索——索引顺序结构北京大学信息学院张铭编写©版权所有，转载或翻印必究Page25link:Key:0123456789101112131415161786497480604824384442331312228648221260分块检索——索引顺序结构„块内昀大关键码„块起始位置„块内有效元素个数563Size:北京大学信息学院张铭编写©版权所有，转载或翻印必究Page26分块检索性能分析„分块检索为两级检索„先在索引表中确定待查元素所在的块；„设在索引表中确定块号的时间开销是ASLb„然后在块内检索待查的元素。„在块中查找记录的时间开销为ASLw„ASL(n)=ASLb+ASLw北京大学信息学院张铭编写©版权所有，转载或翻印必究Page27分块检索性能分析(续1)„„索引表是按索引表是按块内昀大关键码有序有序的，且长度也不大，可以二分检的，且长度也不大，可以二分检索，也可以顺序检索索，也可以顺序检索„„各子表内各个记录不是按记录关键各子表内各个记录不是按记录关键码有序，只能顺序检索码有序，只能顺序检索北京大学信息学院张铭编写©版权所有，转载或翻印必究Page28分块检索性能分析(续2)„假设在索引表中用顺序检索，在块内也用顺序检索„当s=时，ASL取昀小值，ASL=+1≈1ASL2bb+=nnn1ASL2sw+=211ASL122212bsbsnss+++=+=++=+北京大学信息学院张铭编写©版权所有，转载或翻印必究Page29分块检索性能分析(续3)„当n=10,000时„顺序检索5,000次„二分法检索14次„分块检索100次„如果数据块（子表）存放在外存时，还会受到页块大小的制约„此时往往以外存一个Ｉ/Ｏ读取的数据（一页）作为一块北京大学信息学院张铭编写©版权所有，转载或翻印必究Page30分块检索性能分析(续4)„„若采用二分法检索确定记录所在若采用二分法检索确定记录所在的子表，则检索成功时的平均检的子表，则检索成功时的平均检索长度为索长度为ASLASL==ASLASLbb++ASLASLww≈≈loglog22((bb+1)+1)--1+(1+(ss+1)/2+1)/2≈≈loglog22(1+(1+nn//ss)+)+ss/2/2北京大学信息学院张铭编写©版权所有，转载或翻印必究Page31分块检索的优缺点„优点：„插入、删除相对较易„没有大量记录移动„缺点：„增加一个辅助数组的存储空间„初始线性表分块排序„当大量插入/删除时，或结点分布不均匀时，速度下降北京大学信息学院张铭编写©版权所有，转载或翻印必究Page329.2集合的检索„用位向量来表示集合„对于密集型集合（数据范围小，而集合中有效元素个数比较多）00101000101011001514131211109876543210北京大学信息学院张铭编写©版权所有，转载或翻印必究Page33例：计算0到15之间所有的奇素数奇数：素数：奇素数：11111111000000001111110000000000011101100000000013579111315024681012143571113219150468101214357111319150246810121413579111315357111323571113&=北京大学信息学院张铭编写©版权所有，转载或翻印必究Page34实际实现用无符合长整数数组„全集元素个数N=40的集合，集合{35,9,7,5,3,1}表示为0000000000000000000000000000100000000000000000000000001010101010不够一个usignedlong,左补0北京大学信息学院张铭编写©版权所有，转载或翻印必究Page359.3散列检索„9.3.0散列中的基本问题„9.3.1散列函数„碰撞的处理„9.3.2开散列方法„9.3.3闭散列方法„9.3.4闭散列表的算法实现„9.3.5散列方法的效率分析北京大学信息学院张铭编写©版权所有，转载或翻印必究Page369.3.0散列中的基本问题„基于关键码比较的检索„顺序检索，==,!=„二分法、树型,==,„检索是直接面向用户的操作„当问题规模n很大时，上述检索的时间效率可能使得用户无