3
时空权衡中几种方法简介: 时空权衡中几种方法简介 按照一种更一般的表述,这个 （1）输入增强 按照一种更一般的表述 这个 ）输入增强:按照一种更一般的表述 思想是对问题的部分或全部输入做预处理,然 思想是对问题的部分或全部输入做预处理 然 后对获得的额外信息进行存储,以加速后面问 后对获得的额外信息进行存储 以加速后面问 题的求解. (计数法排序、串匹配算法 计数法排序、 题的求解 计数法排序 串匹配算法) （2）预构造 采用空间换时间权衡思想的技 ）预构造:采用空间换时间权衡思想的技 术简单地使用额外空间来实现更快和更方便 的数据存取. 散列法、 树作索引） 的数据存取 （散列法、以B树作索引） 树作索引 （3）还有一些和空间换时间权衡思想相关 ） 的算法设计技术： 的算法设计技术：动态规则
© School of Computer Science and Technology, SWUST
17
Horspool算法
Horspool算法的最差效率Θ(mn) 对于随机文本，它的效率为Θ(n)
/ © School of Computer Science and Technology, SWUST 18
MER ...
LEADER LEADER
sn-1 sn-1
移动幅度等于模式长度
OR ...
REORDER REORDER
把模式中前m-1个字符 中的c和文本中的c对齐
13
情况4 如果C正好是模式中的最后一个字符， 情况4：如果C正好是模式中的最后一个字符，而且 在模式的前m 个字符中也包含C 在模式的前m-1个字符中也包含C，移动的情况类 似于2 移动的时候应该把模式中前m 似于2：移动的时候应该把模式中前m-1个字符中 和文本中的C对齐。 的C和文本中的C对齐。 总结： 总结：如果预先算出每次移动的距离并把它们存在 表中，每个字符C 表中，每个字符C，可以用这个公式算出移动的 距离： 距离： t(C)=模式的长度为m，如果C不包含在模式的前m-1 t(C)=模式的长度为m 如果C不包含在模式的前m 模式的长度为 个字符；模式前m 个字符中最右边的C 个字符；模式前m-1个字符中最右边的C到模式最 后一个字符的距离， 后一个字符的距离，在其他情况下
for(j 0 to m-2 ) do Table[P[j]] m-1-j; return Table;
/ © School of Computer Science and Technology, SWUST 16
Horspool算法
/
Horspool算法中模式的移动距离
对于每一个字符c，移动距离t(c)为：
模式的长度m ,如果c不包含在模式的前m-1个字符中 ,其他
t(c)=
模式前m-1个字符中最右边的c到模式最后一个字符的距离 算法 ShiftTable(P[0..m-1])
例如：对于模式 //用Horspool算法和Boyer-Moore算法填充移动表 BAEBER，E,B,R,A的 //输入：模式p[0..m-1]以及一个可能出现字符的字符表 移动距离分别为1,2,3,4， //输出：以字母表中字符为索引的数组table[0..size-1] 其他的为6 把Table中的所有元素初始化为m；
如果不匹配字符c出现在模式中, (c)-k>0的 如果不匹配字符c出现在模式中,而且t1(c)-k>0的
这个公式也是可用的. 话,这个公式也是可用的.例: SnS0 …… AER ……Sn-1 Sn BARBER BARBER BARBER 如果t (c)-k≤0,则向右移动一个字符 则向右移动一个字符（ 如果t1(c)-k≤0,则向右移动一个字符（不再遵 守原有法则） 守原有法则）. 总之,该算法是这样计算坏符号移动d1的:如果这 总之,该算法是这样计算坏符号移动d1的 d1 个数值是正数,它等于t (c)-k;如果是 如果是0 个数值是正数,它等于t1(c)-k;如果是0或者负 则为1.公式表示为:d1=max{t (c)1.公式表示为 数,则为1.公式表示为:d1=max{t1(c)-k,1}
2
时空权衡
时空权衡是指在算法的设计中，对算法的 时间和空间作出权衡。 常见的以空间换取时间的方法有：
输入增强
计数排序，串匹配算法的改进
预构造
散列法，B树
动态规划
/
© School of Computer Science and Technology, SWUST
/ © School of Computer Science and Technology, SWUST 8
计数排序算法分析实例
13 11 12 13 12 12
数组值 频率 分布值
算法 DistributionCountingt(A[0..n-1]) for(j 0 to u-l) D[j] 0; for(i 0 to n-1) D[A[i]-l] D[A[i]-l]+1; for(j i+1 to u-l) D[j] D[j-1]+D[j]; for(i n-1 downto 0){ j A[j]-l; S[D[j]-1] A[i]; D[j] D[j]-1; } return S;
计数排序
思路：针对待排序列表中的每一个元素， 算出列表中小于该元素的元素个数，把结 果记录在一张表中。
/
© School of Computer Science and Technology, SWUST
6
计数排序算法
算法 ComparisonCountingSort(A[0..n-1]) for(i 0 to n-1) Count[i] 0; for(i 0 to n-1) for(j i+1 to n-1) if(A[i]<A[j]) Count[j] Count[j]+1; else Count[i] Count[i]+1; for(i 0 to n-1) S{Count[i]] A[i]; return S;
/
© School of Computer Science and Technology, SWUST
7
计数排序算法分析
技术排序算法在一种情况下还是卓有成效 的，即待排序元素的值都来自一个已知的 小集合。 如果元素的值是来自位于[l,u]之间的整数， 我们可以计算出这些值出现的频率，然后 把它们存在数组F[0..u-l]中。 然后把有序列表的前F[0]个位置填l，接下来 的F[1]个位置填入l+1.
11 1 1
12 3 4
13 2 6
/
© School of Computer Science and Technology, SWUST
9
串匹配中的输入增强技术
串匹配中的输入增强思想
对模式进行预处理，得到它的一些信息，然后在 查找的过程中使用这些信息。
两种著名算法
Horspool算法
考虑在某些文本中查找模式BARBER
s0s1 ... s0s1 ... c ...
BARBER
sn-1 sn-1
S ...
BARBER BARBER
移动幅度等于模式长度
s0s1 ...
B ...
BARBER BARBER
sn-1
模式中最右边的字符c和 文本中的c对齐
s0s1 ... s0s1 ...
MER ...
LEADER LEADER
sn-1 sn-1
移动幅度等于模式长度
OR ...
REORDER REORDER
把模式中前m-1个字符 中的c和文本中的c对齐
15
/
© School of Computer Science and Technology, SWUST
Boyer-Moore算法 7.2.2 Boyer-Moore算法
1)坏符号移动和移动表 1)坏符号移动和移动表 坏符号移动:由文本中的一个字符C 坏符号移动:由文本中的一个字符C所确定 的,它导致了模式中的相应字符和它不匹配 用公式t (c)- 来计算移动的距离, .用公式t1(c)-k来计算移动的距离,其中 (c)是Horspool算法用到的预先算好的表 t1(c)是Horspool算法用到的预先算好的表 中的单元, 是成功匹配的字符个数. 中的单元,而k是成功匹配的字符个数. 例如:S0 Sn例如:S0 …… SER …… Sn-1 BARBER BARBER 移动距离:t (s)BARBER 移动距离:t1(s)2=4
算法分析与设计
Analysis and Design of Computer Algorithms
第七章 时空权衡
Space and Time Tradeoffs
教学内容
时空权衡的方法 计数排序 串匹配中的输入增强技术 散列法 B树 要求
掌握时空权衡的概念及基本方法，掌握时空权衡 的方法在常见问题中的应用。
Horspool算法
考虑在某些文本中查找模式BARBER
s0s1 ... s0s1 ... c ...
BARBER
sn-1 sn-1
S 0s1 ...
B ...
BARBER BARBER
sn-1
模式中最右边的字符c和 文本中的c对齐
s0s1 ... s0s1 ...
Knuth-Morris-Part Boyer-Moore
我们从Boyer-Moore的简化版本 Horspool算法开始。
/ © School of Computer Science and Technology, SWUST 10
Horspool算法思路简介 Horspool算法思路简介 思路：从模式的最后一个R 1）思路：从模式的最后一个R开始从右向左 移动，比较模式和文本中的相应字符对。 移动，比较模式和文本中的相应字符对。如 果模式中所有的字符都匹配成功， 果模式中所有的字符都匹配成功，就找到了 一个匹配的子串。 一个匹配的子串。如果遇到一对不匹配字符 需要把模式右移。假设文本中， ，需要把模式右移。假设文本中，对齐模式 最后一个字符的元素是字符C Horspool算法 最后一个字符的元素是字符C，Horspool算法 根据C的不同情况来确定移动的距离。 根据C的不同情况来确定移动的距离。一般来 说考虑4种情况。 说考虑4种情况。