《算法第7章时空权衡(李静).ppt》由会员分享，可在线阅读，更多相关《算法第7章时空权衡(李静).ppt（47页珍藏版）》请在三一办公上搜索。
1、第7章 时空权衡,算法设计与分析基础Introduction to the Design and Analysis of Algorithms,2023/3/7,2,教学内容,时空权衡的方法计数排序串匹配中的输入增强技术散列法B树要求掌握时空权衡的概念及基本方法，掌握时空权衡的方法在常见问题中的应用。,本章主要内容,2023/3/7,3,时空权衡算法思想,时空权衡在算法设计中是一个众所周知的问题对问题的部分或全部输入做预处理，然后对获得的额外信息进行存储，以加速后面问题的求解输入增强使用额外空间来实现更快和（或）更方便的数据存取预构造,2023/3/7,4,时空权衡,输入增强计数排序字符串匹配
2、中的输入增强技术预构造散列法B树,时空权衡是指在算法的设计中，对算法的时间和空间作出权衡。常见的以空间换取时间的方法有：,2023/3/7,5,计数排序,针对待排序列表中的每个元素，算出列表中小于该元素的元素个数，并把结果记录在一张表中。这个“个数”指出了元素在有序列表中的位置可以用这个信息对列表的元素排序，这个算法称为“比较计数”,2023/3/7,6,计数排序,思路：针对待排序列表中的每一个元素，算出列表中小于该元素的元素个数，把结果记录在一张表中。,2023/3/7,7,算法 Comparison(A0n-1)/用比较计数法对数组排序for(i=0;i n;i+)Counti=0;for
3、(i=0;i n-1;i+)for(j=i+1;j n;j+)if(AiAj)Countj+;else Counti+;for(i=0;i n;i+)SCounti=Ai;return S;,2023/3/7,8,计数排序,该算法执行的键值比较次数和选择排序一样多，并且还占用了线性数量的额外空间，所以几乎不能来做实际的应用但在一种情况下还是卓有成效的待排序的元素值来自一个已知的小集合如待排序集合只有多个1，2元素（更一般：元素位于下界l 和上界u之间的整数）那么我们可以使用计数排序方法，扫描列表中1和2的数目，然后重排列就可以了（只有我们可以改写给定的元素时才成立）,2023/3/7,9,计数
4、排序,另一种更现实的情况：待排序的数组元素有一些其他信息和键值相关（不能改写列表的元素）将A数组元素复制到一个新数组S0n-1中A中元素的值如果等于最小的值l，就被复制到S的前F0个元素中，即位置0到F0-1中值等于l+1的元素被复制到位置F0至(F0+F1)-1，以此类推。因为这种频率的累积和在统计中称为分布，这个方法也称为“分布计数”。,2023/3/7,10,计数排序算法分析实例,算法 DistributionCountingt(A0.n-1,L，U)for(j0 to u-l)Dj0;for(i0 to n-1)DAi-lDAi-l+1;for(j1 to U-L)DjDj-1+Dj;
5、for(in-1 downto 0)jAi-L;SDj-1Ai;DjDj-1;return S;,2023/3/7,11,算法 DistributionCounting(A0n-1,l,u)/分布计数法对有限范围整数的数组排序for(j=0;j=0;-i)j=Ai l;SDj-1=Ai;Dj-;return S;,假设数组值的范围是固定的，那么这是一个线性效率的算法但重点是：除了空间换时间之外，分布技术排序的这种高效是因为利用了输入列表独特的自然属性！,2023/3/7,12,字符串匹配,字符串匹配问题：要求在一个较长的n个字符的串（称为文本）中，寻找一个给定的m个字符的串（称为模式）。蛮力法
6、：简单地从左到右比较模式和文本中每一个对应的字符，如果不匹配，把文本向右移动一格，再进行下一轮尝试，最差效率为O(nm)，随机文本的平均效率O(n)输入增强技术：对模式进行预处理以得到它的一些信息，把这些信息存储在表中，然后在给定文本中实际查找模式的时候使用这些信息Knuth-Morris_Pratt(KMP)算法和Boyer-Moore(BM)算法,2023/3/7,13,字符串匹配的输入增强技术,Knuth-Morris_Pratt算法和Boyer-Moore算法的主要区别在于：前者是从左到右，后者是从右到左但因为后者更简单，所以我们只考虑Boyer-Moore算法：开始的时候把模式和文本
7、的开头字符对齐。如果第一次尝试失败了，把模式向右移。只是每次尝试过程中的比较是从右向左的，即从模式的最后一个字符开始Horspool算法和Boyer-Moore算法的简化版,2023/3/7,14,Horspool算法,从模式的最后一个字符开始从右向左，比较模式和文本的相应字符如果模式中所有的字符都匹配成功，就找到了一个匹配子串，就可以停止了如果遇到一对不匹配的，把模式右移,S0csn-1 BARBER,2023/3/7,15,Horspool算法,根据对齐模式的最后一个字符c的不同情况确定移动的距离：情况1：模式中不存在c，模式安全移动的幅度就是它的全部长度情况2：模式中存在c，但它不是模式
8、的最后一个字符，移动时应该把模式中最右边的c和文本中的c对齐情况3：c正好是模式的最后一个字符，但是在模式的其他字符中不包含c，移动的情况：移动幅度等于模式长度m情况4：c正好是模式的最后一个字符，而且在模式的前m-1个字符中包含c，移动的情况：把模式中前m-1个字符中的c和文本中的c对齐,2023/3/7,16,Horspool算法,考虑在某些文本中查找模式BARBER,s0s1.c.sn-1,BARBER,移动幅度等于模式长度,移动幅度等于模式长度,模式中最右边的字符c和文本中的c对齐,把模式中前m-1个字符中的c和文本中的c对齐,情况1：模式中不存在c,2023/3/7,17,Horsp
9、ool算法,比起蛮力法每次只移动一个位置，该算法移动的更远但如果为了移动的更远就需要每次都检查模式中的每个字符，它的优势也会丧失时空权衡：预先算出每次移动的距离并把它们存在表中，将距离填入表中的单元格中这个表是以文本中所有可能遇到的字符为索引的对于每个字符c可用公式算出移动距离：,2023/3/7,18,Horspool算法,例如模式为“BARBER”，那么文本中除了E,B,R,A的单元格分别为1,2,3,4外，其他的都为6有一个简单的算法用来计算移动表中每个单元格的值：初始时，把所有的单元格都置为模式的长度m然后从左到右扫描模式，将下列步骤重复m-1次对于模式中的第j个字符，将他在表中的单元
10、格改写为m-1-j，这是该字符到模式右端的距离,2023/3/7,19,Horspool算法,第一步：对于给定的长度为m的模式和在模式及文本中用到的字母表，按照上面的描述构造移动表第二步：将模式与文本的开始处对齐第三步：重复下面的过程，直到发现了一个匹配子串或者模式到达了文本的最后一个字符以外。从模式的最后一个字符开始，比较模式和文本中的相应字符，直到：要么所有m个字符都匹配（然后停止），要么遇到了一对不匹配的字符。后者，如果c是当前文本中的和模式的最后一个字符相对齐的字符，从移动表的第c列中取出单元格t(c)的值，然后将模式沿着文本向右移动t(c)个字符的距离,2023/3/7,20,Hor
11、spool算法,算法 ShiftTable(P0.m-1)/用Horspool算法和Boyer-Moore算法填充移动表/输入：模式p0.m-1以及一个可能出现字符的字符表/输出：以字母表中字符为索引的数组table0.size-1把Table中的所有元素初始化为m；for(j0 to m-2)do TablePjm-1-j;return Table;,2023/3/7,21,Horspool算法效率分析,Horspool算法的最差效率(mn)why?习题7.2-4对于随机文本，它的效率为(n),2023/3/7,22,P202 习题7.2-4,4.用Horspool算法在一个长度为n的文本中
12、查找一个长度为m的模式,请分别给出下面两种例子.a.最差输入 b.最优输入,在n个”0”组成的文本中查找”10.0”(长度为m),查找次数C(worst)=m(n-m+1)b.在n个”0”组成的文本中查找由m个”0”组成的模式,查找次数C(best)=m,2023/3/7,23,Boyer-Moore算法,如果在遇到一个不匹配字符之前，如果已经有k(0km)个字符匹配成功，则Boyer-Moore算法与Horspool算法处理不同。,在这种情况下，Boyer-Moore算法参考两个数值来确定移动距离。第一个数值是有文本中的第一个坏字符c所确定，用公式t1(c)-k来计算其中t1(c)是Hors
13、pool算法用到的预先算好的值，k是成功匹配的字符个数,2023/3/7,24,Boyer-Moore算法,t1(A)-2=4-2=2,d1=maxt1(c)-k,1,t1(S)-2=6-2=4,坏符号移动,2023/3/7,25,Boyer-Moore算法,第二个数值是由模式中最后k0个成功匹配的字符所确定。称为好后缀移动把模式的结尾部分叫做模式的长度为k的后缀，记作suff(k)情况1：当模式中存在两个以上suff(k)的情况时，移动距离d2就是从有数到第二个suff(k)到最右边的距离。,2023/3/7,26,26,Boyer-Moore算法,情况2：当模式中存在1个suff(k)的情
14、况时：,k=3移动6,k=3移动？次,2023/3/7,27,Boyer-Moore算法,为了避免情况2的出现，我们需要找出长度为lk的最长前缀，它能够和长度同样为l的后缀完全匹配。如果存在这样的前缀，我们通过求出这样的前缀和后缀之间的距离来作为移动距离d2的值，否则移动距离就是m,2023/3/7,28,Boyer-Moore算法,2023/3/7,29,http:/www.mryang.org/,School of Computer Science and Technology,SWUST,29,Boyer-Moore算法举例,在一个由英文字母和空格构成的文本中查找BAOBAB,坏符号移动
15、表,好后缀移动表,2023/3/7,30,散列法,考虑一种非常高效的实现字典的方法字典是一种抽象数据类型，即一个在其元素上定义了查找、插入和删除操作的元素集合集合的元素可以是容易类型的，一般为记录散列法的基本思想是：把键分布在一个称为散列表的一维数组H0，m-1中。可以通过对每个键计算某些被称为“散列函数”的预定义函数h的值，来完成这种发布该函数为每个键指定一个称为“散列地址”的位于0到m-1之间的整数,2023/3/7,31,散列法,散列函数需要满足两个要求：散列函数需要把键在散列表的单元格中尽可能均匀地分布（所以m常被选定为质数，甚至必须考虑键的所有比特位）散列函数必须容易计算散列的主要版
16、本：开散列（分离链）闭散列（开式寻址）,2023/3/7,32,开散列（分离链）,键被存储在附着于散列表单元格上的链表中，散列地址相同的记录存放于同一单链表中查找时：首先根据键值求出散列地址，然后在该地址所在的单链表中搜索；,2023/3/7,33,开散列（分离链）,查找效率取决于链表的长度，而这个长度又取决于字典和散列表的长度以及散列函数的质量若散列函数大致均匀地将n个键分布在散列表的m个单元格中，每个链表的长度大约相当于n/m个比率=n/m称为散列表的负载因子一般我们希望负载因子不要和1差太远。如果太小就意味着有很多空链表；如果太大就使链表太长；如果和1相差无几的话就能到达惊人的效率：平均
17、只要一两次比较就能完成查找,成功查找和不成功查找中平均需检查的个数S和U：之所以能得到这样卓越的效率，不仅是因为这个方法本身就非常精巧，而且也是以额外的空间为代价的插入和删除在平均情况下都是属于(1),2023/3/7,34,闭散列（开式寻址）,所有的键值都存储在散列表本身中，而没有使用链表（这表示表的长度m至少必须和键的数量一样大）解决碰撞：有多种方法，例如线性探测插入和查找：简单而直接删除操作：“延迟删除”，用一个特殊的符号来标记曾被占用过的位置，以把它们和那些从未被只用过的位置区别开来,2023/3/7,35,闭散列（开式寻址）,所有键都存储在散列表本身，采用线性探查解决冲突，即碰撞发生
18、时，如果下一个单元格空，则放下一个单元格，如果不空，则继续找到下一个空的单元格，如果到了表尾，则返回到表首继续。,2023/3/7,36,http:/www.mryang.org/,School of Computer Science and Technology,SWUST,36,散列法,散列法的基本思想：把键分布在一个称为散列表的一维数组H0.m-1中。可以利用散列函数来计算每个键的值，该函数为每个键指定一个称为散列地址的值，该值是位于0到m-1之间的整数。如果键是一个非负整数，则h(K)=K mod m如果键是某个字母表中的字母，则可以把该字母在字母表中的位置指定个键，记为ord(K)如
19、果键是一个字符串c0c1.cs-1，则定义h(K)=(ord(ci)mod m或者h0;for i0 to s-1 do h(h*C+ord(ci)mod m,2023/3/7,37,http:/www.mryang.org/,School of Computer Science and Technology,SWUST,37,散列法,一个散列函数必须满足的两个要求：需要把键在散列表的单元中尽可能的均匀分布必须是容易计算的碰撞当三列表的长度m小于键的数量n时，会有两个或多个键被三列到同一个单元中即时m相对于n足够大，碰撞还是会发生散列法的两个版本开散列（分离链）闭散列（开式寻址）,2023/3
20、/7,38,http:/www.mryang.org/,School of Computer Science and Technology,SWUST,38,开散列（分离链）,在开散列中，键被存放于散列表单元的链表中。,A,FOOL,AND,HIS,MONEY,ARE,SOON,PARTED,2023/3/7,39,http:/www.mryang.org/,School of Computer Science and Technology,SWUST,39,开散列（分离链）分析,一般来说，查找的效率取决于链表的长度，而这个长度有取决于字典和散列表的长度以及散列函数的质量。如果该散列函数大致均
21、匀地将n个键分布在散列表的m个单元中，每个链表的长度大约相当于n/m，其=n/m称为散列表的负载因子。成功查找中平均需检查的指针个数S=1+/2不成功查找中平均需检查的指针个数U=通常情况下，我们希望负载因子和1不要相差太大。,2023/3/7,40,http:/www.mryang.org/,School of Computer Science and Technology,SWUST,40,闭散列（开式寻址）,所有键都存储在三列表本身，采用线性探查解决冲突，即碰撞发生时，如果下一个单元格空，则放下一个单元格，如果不空，则继续找到下一个空的单元格，如果到了表尾，则返回到表首继续。,2023/
22、3/7,41,http:/www.mryang.org/,School of Computer Science and Technology,SWUST,41,闭散列（开式寻址）分析,闭散列的查找和插入操作是简单而直接的，但是删除操作则会带来不利的后果。比起分离链，现行探查的数学分析是一复杂的多的问题。对于复杂因子为的散列表，成功查找和不成功查找必须要访问的次数分别为：S(1+1/(1-)/2U(1+1/(1-)2)/2散列表的规模越大，该近似值越精确,2023/3/7,42,7.4 B树,B树：所有的数据记录（或者键）都按照键的升序存储在叶子中；它们的父母节点作为索引每个父母节点包含n-1个
23、有序的键K1Kn-1这些键之间有n个指向子女的指针，使得子树T0中的所有键都小于K1，子树T1中的大于等于K1小于K2，以此类推,2023/3/7,43,B树,在B树中，所有的数据记录都按照键的增序存储在叶子中，它们的父节点作为索引。,2023/3/7,44,B树,一棵度为m2的B树必须满足下面这些特性：它的根要么是一个叶子，要么具有2到m个子女除了根和叶子以外的每个节点，具有m/2到m个子女这棵树是（完美）平衡的，也就是说，它的所有叶子都是在同一层上,2023/3/7,45,B树,在查找键给定的某条记录中，需要访问多少个B树的节点？,对于任何包含n各节点、次数为m、高度为h0的B树来说，有：,2023/3/7,46,应用B树：磁盘访问,当一个文件包含 1亿条记录时：,2023/3/7,47,空间换时间技术有两种主要的类型：输入增强和预构造。分布计数是一种特殊方法，用来对元素取值来自于一个小集合的列表排序。串匹配的Horspool算法是Boyer-Moore算法的简化，都以输入增强技术为基础，且从右向左比较模式中的字符。散列是一种非常高效的实现字典的方法，分为开散列和闭散列，其中必须采用碰撞解决机制。B树是一棵平衡查找树。,本章小结,
