AA-chapter7时空权衡20134-18.ppt

* * 是属于平方级的，并且还占用了额外的线性数量的空间。该算法执行的键值比较次数和选择排序一样多。 * 但是，考虑一种特殊情况：在某种情形下，待排序元素的值是属于一个已知的小集合的。那么我们可以改造上面的比较方法，变成直接对数组元素进行一次扫描，然后记录每种元素出现的次数。容易发现，这些出现次数的记录，直接影响到最终元素在数组当中排列的位置。 这种方式称为分布计数！ * 分布计数排序的效率应该很容易分析，假设数组值的范围是固定的（考虑一个实例：我们学校学生的年龄），这显然是一个线性效率的算法，因为它仅仅需要对输入数组从头到尾扫描处理两遍。从这一点上而言，它是我们目前为止遇到过的时间效率最高的排序算法。 然而，分布计数排序的这种高效率是因为利用了输入列表独特的自然属性的。作为一个思考题：你是否可以估计对于这样的算法比起其它排序来讲，需要多少额外的空间？！ ? School of Computer Science and Technology, SWUST * * 模式匹配中的好算法大都使用了输入增强技术，最著名的算法有： KMP算法：Knuth-Morris-Pratt BM算法： Boyer-Moore * * * * * 1977年,Robert?Boyer和L.Moore发表了一种新的精确字符串匹配算法,这种算法在逻辑上相对于现有的算法有了很大的超越.它对要有哪些信誉好的足球投注网站的字符串实施逆序字符比较,而且有一种找到了不匹配就不需要对整个字符串进行有哪些信誉好的足球投注网站的方法.这种算法还有最初在PDP-10汇编器上实现的奇迹. * * * * * * * * * * * * * * * * 7.2.1 Horspool算法 算法分析与设计 兰州大学信息学院 * Horspool算法的最差效率Θ(mn) 对于随机文本，它的效率为Θ(n) 7.2.1 Horspool算法 算法分析与设计 兰州大学信息学院 * 7.2.2 Boyer-Moore算法 如果在遇到一个不匹配字符之前，如果已经有k(0km)个字符匹配成功，则Boyer-Moore算法与Horspool算法处理不同。 在这种情况下，Boyer-Moore算法参考两个数值来确定移动距离。 第一个数值是有文本中的第一个字符c所确定，用公式t1(c)-k来计算 其中t1(c)是Horspool算法用到的预先算好的值，k是成功匹配的字符个数 算法分析与设计 兰州大学信息学院 * t1(A)-2=4-2=2 d1=max{t1(c)-k,1} t1(S)-2=6-2=4 坏符号移动 用i表示不匹配的位置,i=i+patlen 用i表示不匹配的位置,i=i+t(‘A’) 7.2.2 Boyer-Moore算法 算法分析与设计 兰州大学信息学院 * 第二个数值是由模式中最后k0个成功匹配的字符所确定。称为好后缀移动 把模式的结尾部分叫做模式的长度为k的后缀，记作suff(k) 情况1：当模式中存在两个以上suff(k)的情况时，移动距离d2就是从第一个后缀的最右元素位置数到第二个suff(k) 最右边的距离。 7.2.2 Boyer-Moore算法 算法分析与设计 兰州大学信息学院 * 情况2：当模式中存在1个suff(k)的情况时： k=3 移动6 k=3 移动？次 7.2.2 Boyer-Moore算法 算法分析与设计 兰州大学信息学院 * 为了避免情况2的出现，我们需要找出长度为lk的最长前缀，它能够和长度同样为l的后缀完全匹配。 如果存在这样的前缀，我们通过求出这样的前缀和后缀之间的距离来作为移动距离d2的值，否则移动距离就是m 7.2.2 Boyer-Moore算法 算法分析与设计 兰州大学信息学院 * 7.2.2 Boyer-Moore算法：流程图 * 算法分析与设计 兰州大学信息学院 7.2.2 Boyer-Moore算法 算法分析与设计 兰州大学信息学院 * 在一个由英文字母和空格构成的文本中查找BAOBAB c A B C D ... O ... Z - t1(c) 1 2 6 6 6 3 6 6 6 坏符号移动表 好后缀移动表 7.2.2 Boyer-Moore算法：举例 7.3 散列法 散列法的基本思想： 把键分布在一个称为散列表的一维数组H[0..m-1]中。 可以利用散列函数来计算每个键的值，该函数为每个键指定一个称为散列地址的值，该值是位于0到m-1之间的整数。 如果键是一个非负整数，则h(K)=K mod m 如果键是某个字母表中的字母，则可以把该字母在字母表中的位置指定个键，记为ord(K) 如果键是一个字符串c0c1...cs-1，则定义 h(K)=(∑ord(ci)) mod m 或者h?0; for i?0 to s-1 do h?(h*C+