9.3.3 快速排序
快速排序将原数组划分为两个子数组，第一个子数组中元素小于等于某个边界值，第二个子数组中的元素大于某个边界值，实现方式是从数组两端向中间变量元素如果不满足左侧元素小于边界值，右侧数据大于边界值条件时，则交换元素，直至两段遍历到同一个索引时，再将左右两段作为两个子数组继续重复上述操作，直到子数组仅包含一个元素时候停止，这样得到一个有序的数组。
template<class T>
void quicksort(T data[], int first, int last) {
int lower = first+1,upper = last;
swap(data[first],data[(first+last)/2]);
T bound = data[first];
while (lower <= upper) {
while (data[lower] < bound) {
lower++;
}
while (bound < data[upper]) {
upper--;
}
if (lower < upper) {
swap(data[lower++],data[upper--]);
} else {
lower++;
}
}
swap (data[upper],data[first]);
if (first < upper-1) {
quicksort(data,first,upper-1);
}
if (upper+1 < last) {
quicksort(data,upper+1,last);
}
}
template<class T>
void quicksort (T data[], int n) {
int i,max;
if (n < 2) {
return;
}
for (i = 1, max = 0; i < n; i++) {
if (data[max] < data[i]) {
max = i;
}
}
swap(data[n-1],data[max]);
quicksort(data,0,n-2);
}
快速排序算法在最坏情况下，即每次分裂的两个子数组其中一个数组只包含一个元素，此时比较次数的时间复杂度为O(n2)。最好情况下每次将数组平均分配，此时比较次数的时间复杂度为O(nlgn)。平均情况下的比较次数也为O(nlgn)。为了避免最坏的情况，在选取边界值时可以选取头尾和中间三个元素，再选其中中间值作为边界元素。通常情况下快速排序的算法效率最高。对于小型数组，快速排序算法能不能发挥优势，如当n小于30时，插入排序反而效率更高。
9.3.4 归并排序
归并排序的实现策略是将数组划分为多个子数组，指导子数组只有一个元素，然后再合并所有的子数组，在合并数组的过程中对元素排序，最后就能得到一个有序的数组，这里划分子数组只是逻辑上的划分，实际上还是只有一个数组。
merge (array[], first, last) {
mid = (first+last)/2;
j = first;
k = mid + 1;
将array中first之前的元素放在temp中，i=first;
while (通过jk值判断array在first和last区间内的两个子数组都有元素) {
if (array[j]<array[k]) {
temp[i++] = array1[j++];
} else {
temp[i++] = array1[k++];
}
}
将array中的first后还未处理的元素放在temp末尾；
}
mergesort (data[], first, last) {
if (first < last) {
mid = (first+last)/2;
mergesort(data,first,mid);
mergesort(data,mid+1,last);
merge(data,first,last);
}
}
归并排序的移动次数为O(nlgn)。最坏情况下的比较次数也是O(nlgn)。使用迭代替换递归可以使算法效率更高。普通的归并排序在合并数组时要使用大量的内存空间，可以通过链表的方法减少内存的使用。
9.3.5 基数排序
基数排序可以用于快速的对字符串和数字排序，在对数字排序时，找到元素的最大位数i，对集合中所有位数小于i的元素前面用0补齐，并把每个元素当字符串处理。将数组中元素依次做处理，即从元素的最右位开始，根据当前位上的值将元素放入09代表的堆中，将堆010的元素取出组合成新的数组，重复上述操作，知道比较位递减到第0位位置。最后得到的数组就是有序的，其中堆用队列方式实现。
基数排序中涉及到的取模等数学运算的次数为O(n)，数据的移动次数为O(n)，但是该算法需要额外的内存空间实现各个堆。
基数排序还可以将数字转化为二进制位来进行排序，但是这样会使队列的数量剧增，并且数据的移动次数剧增。因此基数排序的性能很大程度上取决于队列实现的效率。一个很好的解决方法是使用一个大小为n的整数数组queues和大小为10的整数数组queueHeads及queueTails。d表示当前判断的位数，queueHeads中每个元素表示以第d位是当前元素索引的数据被保存在queues中的索引，queues中每个元素同时表示在原始数据中的索引，这样queueHeads可以通过queues查找到原始数据，同时它也表示第d位和要查找的元素相同的下一个元素保存在queues自己内部的索引。queueTails包含data中第d位是i的最后一个数字的位置。每一次查找时更新上述三个数组，再根据这三个数组得到新的数组，直至查找到最左一位。
9.3.5 计数排序
计数排序实现方式为，1）准备待排序数组，找出最大元素；2）初始化count数组，容量为原始数据中最大的数，并根据每个数据出现的次数更新count数组；3）将count数组中从第一个元素开始更新数组，每个元素等于原count数组中对应序号下的左侧包含自己的元素的和；4）根据tmp[count [data(n-1)]-1] = data[n-1]策略，将data中的数据全部放在temp中，最后得到有序数组。
10 散列
如果能找到一个函数h，将特定的关键字K（可以是字符串、记录或者数字）转换成一张表中的一个索引，表中储存与K相同的项。这个函数h成为散列函数，这张表称为删列表。当不同的关键字生成了同样的索引时会发生冲突，而评价一个散列函数的好坏是根据其避免冲突的能力。如果函数h能将所以键值转换为不同的索引，则称为理想散列函数。
10.1 散列函数
对于一张具有m个位置的表，n个待分配的项而言，散列函数和理想散列函数的数量非常庞大。对于构建散列函数，我们有几种基本的方法。
10.1.1 除余法
对于保存数字的散列表，h(k) = k mod Tsize，Tsize最好为素数，否则使用h(K) = (K mod p) mod Tsize，p是一个大于Tsize的素数。
10.1.2 折叠法
将关键字分割为几个部分，这些部分组合或者折叠在一起，产生新的目标地址。根据其变化的方式进一步分为移位折叠法和边界折叠法。对于k=123 456 789，移位折叠法将123+456+789的结果对Tsize求模。边界折叠法将 123 456 789转换为 123 654 789，并将123+654+789的结果求模。
10.1.3 平方取中法
对于关键字3121，对其平方后得到 97 406 41，对于1000个单元散列表而言，取其中关键部分406，一种更有效的方式是将关键字的平方转换为二进制数据再取其中间部分。
10.1.4 提取法
对于拥有大量相同前缀的关键字，如ISBN10，ISBN23，ISBN45...，我们可以只提取不同，部分即去除ISBN部分，当然在使用提取法是必须小心的设计提取策略。
10.1.5 基数转换法
通常我们使用的键值是十进制的，我们可以将其转换为9进制或其他进制然后再对Tsize取模，这种方法不能完全避免冲突，因为十进制的345和264使用这种方法都对Tsize=100的表，得到的都是23。
10.1.5 全域散列法
在一组精心准备的散列函数H中，随机选择一个作为当前键值的散列函数，并且对于每一对x和y，满足h(x)=h(y)的散列函数最多为|H|/Tsize。这样的方法为全域散列法。
10.2 冲突解决方法
直接对关键字进行散列操作存在问题，极有可能出现冲突。仔细选择散列函数和表的长度可以减少冲突，但是冲突还是无法完全消除。以下谈论当遇到这些冲突时的解决办法。
10.2.1 开放定址法
发生冲突时，在表中向后线性的找到一个可用的地址，对于关键字k，确定可用地址的策略是norm(h(K) + p(1))，norm(h(K) + p(2))，... ... ，norm(h(K) + p(i))，其中p是探查函数，其中i是探查指针，norm是规范化函数，通常对表的大小取模。i从1递增直到找到合适位置，或者表中无剩余空间时停止。
1）最简单的方法是线性探查，p(i)=i，如果找到表结尾还没找到可用位置则返回表头直到找到刚开始探查的位置。这种方式会造成数据聚集，而聚集块的形成会造成恶性循环，通常可以仔细的选择探查函数来避免这个问题。
2）一种改良方法是选择一个二次函数作为探查函数，p(i)=(-1)i-1((i+1)/2)2，i=1,2,...,Tsize-1，当i值取到最大时还未找到合适位置则结束探查。表的长度不应为偶数，这样探查只会在奇地址或者偶地址中进行。了理想的情况下表的长度应为素数4j+3，其中j为整数。二次探查尽管比线性探查更优，但并不能完全避免几块的形成。因为对散列到相同位置的关键字都采用一样的探查序列，会造成二次聚集，但危害相比之前更小。
3）另外一种改良方法是探查函数使用随机数发生器，这样不会对表的长度有过多的要求。对于具有相同位置的键值K必须使用相同的随机数种子。保证相同的关键字具有相同的探查序列。
4）另外一种改良方法是使用双散列探查函数。对于关键字k，其探查序列表示为h(k)，h(k)+hp(k)，...，h(k)+i×hp(k)，...。表的长度需要取素数。由于双散列函数会耗时，因此第二个函数最好根据第一个函数来取值，如hp(k) = i×h(k)+1。
线性探查法查找时间会随着表中元素的增加而增加。通常要求有35%的可用空间，才能保证良好的执行性能。对非常大的文件来说，这样很浪费空间。二次探查法要求的可用空间为25%，双散列函数探查法要求的空间是20%。因此当允许多个项存储在一个给定的位置上或关联的区域内，这是一个很好的解决办法。
10.2.2 链接法
在链接法中，表中的每个地址并不保存关键字，只保存一个链表的指针，引用指针的这张表成为分类表。通常可以使用自组织链表来提升性能。
链接法的一种扩展是聚结结果，这种方法中表不仅保存关键字，还保存当冲突发生时指向下一个关键字的索引。这种方法用的空间更少，但是表的长度限制了散列到表中的关键字个数，可以为溢出分配一个溢出存储区，用来存储不能放在表中的关键字。
10.2.3 桶地址
为表中的每个地址关联一个可以放置多个项的桶，当发生冲突时将关键字放在通中，当桶满了使用线性查找法查找下一个桶中，如使用二次查找法则放入算出的某个桶中。当桶满时也可以不放在其他通中，而是放在溢出区内，这种情况下每个桶包含一个标记指示是否需要到溢出区中继续查找。
10.3 删除
在散列表中删除元素，如果是用链接法实现的散列表，直接删除对应元素即可，对应其他方法而言要考虑冲突问题。如果使用
线性探查法，删除元素时只需要将其标记为无效元素，当插入新关键字时覆盖无效元素。但是对于大量删除操作和少量操作，尽管元素已经标记为无效，但是探查法也会对这些无效元素进行遍历导致效率降低，因此当删除的记录达到一定量时对表清理。
10.4 理想散列函数
前面解决冲突的方法主要是因为键值集合我们并不知道，因此只能先建立散列表解决冲突，但是当键值已知时，应该尽量找到一个理想的散列函数。当表的数量和键值的数量相同时，这个理想散列函数称为最小理想散列函数。
10.4.1 Cichelli方法
Cichelli方法的散列函数可以表示为h(word) = (length(word) + g(firstletter(word))) + g(lastletter(word))) mod Tsize。其中等式的三项分别是单词的长度，单词首字母的g值，单词尾字母的g值。该方法有三个部分，1）统计每个键值首字母，得到一个字母集合，统计这些字母在每个单词首尾出现的个数。2）对键值数组排序，根据首尾字母各自出现的频率和降序排列。3）最后搜索可能的最小理想散列函数。g值需要指定一个最大值max，在算法处理时g值可能会从0一直递增到max。
第三步是该算法的核心，从第一个键值开始处理，将首尾字母g值初始化为0，计算该键值的h值，再判断第二个单词，此时将未出现的首尾字母g值赋值为0，计算键值h值，如果这个h值可用则进行下一步，如果不可用则调整最后一个赋值字母的g值直到max，如果还没有找到可用的地址则回溯到上一个赋值g值的字母，再将其g值递增，再将其晚于这个字母赋值的g值从0开始重新赋值，直到找到一个可用的g值或者初次赋值g值的单词尝试完所有的可能。
这个算法的过程是指数级的，因为其用了穷举搜索，因此对于n很大的键值集合并不适用，并且它并不能报账找到一个理想的散列函数，但是对于小规模的键值集合还是很高效。
第一种改良方法是使散列函数除了考虑首尾字母外再考虑其他的字母。第二种改良方式是将数据分割到不同的桶中寻找理想的散列函数，但是这种方法很难找到一个理想的分组函数。但是这两种改良方法都不是很理想，因此需要考虑其他更有效的搜索算法。
10.4.2 FHCD算法
FHCD算法是对Cichelli算法的一种扩展，其散列函数表示为h(word) = h0(word) + g(h1(word)) + g(h2(word)) mod Tsize。其中h0(word) = (T0(c1) + ... + T0(cm)) mod n，h1(word) = (T1(c1) + ... + T1(cm)) mod r，h2(word) = ((T2(c1) + ... + T2(cm)) mod r) + r，T0、T1、T2为rand()为每个字符产出的随机数表，确保同一个字符在同一张表中能得到相同的值，并且不同的单词具有唯一的h0、h1和h2组合。n为单词的个数，r 为一个参数，通常小于等于n/2。c1~cm是将单词拆成m个单字符。FHCD算法主要分三个步骤。
第一步是映射，创建T0、T1和T2三张随机表，然后计算出所以键值的h0、h1和h2，将h1值作为上部分顶点，h2值作为下方顶点，将每个单词映射到图中成为图的一条边。
第二步是排序，根据上一步的图中每个顶点的度来建立一个表，第一列代表层，第二列代表节点编号，第三列代表边，第0层为度最高的节点，这一层不含边，其后每一层都的顶点都选和上一层顶点相连并具有最高度的顶点，如无相连顶点则在剩下的顶点中选中度最高的顶点。每一层的边为当前顶点与前面所有层顶点相连接并且还未被放入表中的边。这样得到一个排序表。
第三步是搜索，所有键值都具有h1和h2值，并且他们都是数字，为每个数字设置一个g值的方法是随机生成的。查找过程从第二步中排序表的第0层开始，为第0层的顶点代表的数字随机生成一个g值，再进入第1层，为当前层的顶点代表的数字随机生成一个g值，这是会发现此时两个g值分别是该排序表层中单词对应的h1和h2值，再从第一步中取出h0值，这样算出一个散列值，重复上述操作得到所有键值的散列值，同时保存g值表。
10.5 再散列
如果一个表满了，或者达到饱和状态，必须找到解决办法找到空槽来放置元素。其中一种办法就是再散列。将所有元素散列到新表中，丢弃旧表。新表的大小一般是接近旧表大小两倍的素数。再散列有几种方式可以实现。
其中一种为布谷鸟散列使用两个表T1和T2，分别对应两个散列函数h1和h2。再散列运算时将键值k使用T1和h1散列，如果位置被占，将该元素替换，将替换出的元素用T2h2散列，如果被占则替换，被替换的元素再用T1h1散列，这样不断循环，直至找到可用位置。
由于前面的不断在两个表中探查，以及表已经满了都会造成无限循环的发生，因此必须限制最大探查次数。
10.6 可扩展文件的散列函数
再散列会操作所有的元素，因此非常耗时，可以通过对旧表进行扩展，对局部进行再散列的操作来提高效率。根据实现的方式，这类技术分为基于目录的和非目录的两类。
基于目录的有可扩充散列，动态散列和可扩展散列三种方式，它们都是讲关键字分散到桶中，主要区别于目录的结构，在可扩充散列和动态散列中使用二叉树作为桶的索引，在可扩展索引中用表来保存目录。
非目录的一个方法是线性散列，主要通过动态的改变其散列函数来实现，它也具有和普通散列表不同的结构。
10.6.1 可扩展散列
可扩展散列维护两个结构，目录表和桶，其中目录表中每个元素都指向了一个桶的地址，桶的容量是固定的，当插入第一个元素时目录表中只有1个元素，指向了唯一的桶。随着散列元素的增加，目录表成倍不断加长，通常散列函数将关键字散列成一个数字并用二进制位表示，目录表中只存储能够区分所有地址的前缀，这个前缀的长度成为目录深度。每个桶中存储完整的地址或者字符串的二进制形式，其中能够无歧义区分某个桶中各个地址的前缀的长度成为局部深度，每个桶的局部深度都可能不一致。
extendibleHashingInsert (k) {
bitPattern = h(k);
p = directory [bitPattern左边的depth(directory)位];
if (p指向的桶bd中有可用空间) {
将k放入桶中;
} else {
将桶bd分裂为bd0和bd1;
将桶bd0和bd1的局部深度设置为depath(bd) + 1;
把bd的记录分布到bd0和bd1中;
if (depth(bd) < depth(directory)) {
将指向桶bd的一半指针更新为指向bd1;
} else {
directory增长一倍并增加其深度;
在directory的各个位置中放入合适的指针;
}
}
}
该方法能避免对文件的重新组织，但是其目录增长的方式是成倍增长的，这意味着目录中可能会出现大量的冗余。一种处理方法是当目录超过主存后成倍增加桶的大小。
10.6.2 线性散列
线性散列中已有的桶分裂总是以相同的方式线性加入，不需要保存索引。线性散列需要一个层级level标识，标识当前是第几轮分裂，初始level=0，当桶发生分裂时，新的桶level等于当前桶的level+1，另外需要维护指针Split指向下一个要被分裂的桶，当Split指向的同一个level的所以桶完成分裂时，Split重新置为表头的索引。另外同一时刻表中桶最多属于两个不同level，他们分别用不同的hlevel维护。其中hlevel(K) = K mod (Tsize × 2level)。另外该算法需要准备溢出取，如果对应索引位置的桶中元素已满时，则将键值放入溢出区。并且在运行前需设置装填因子临界值，当装填因子大于临界值时或者溢出区满时会重新分裂桶，每一次的桶分裂都会重新处理溢出区的键值，其中充填因此要考虑溢出区。
初始化：Split = 0；level = 0；
linearHashingInsert(k) {
if (h^level^(k) < split) {
hashAddress = h^level+1^(k);
} else {
hashAddress = h^level^(k);
}
将k插入一个对应的桶或者溢出区;
white (装填因子很高或者k尚未插入) {
建立一个编号为Split + Tsize + 2^level 的新桶；
将桶Split中的关键字在桶Split和Split + Tsize + 2^level之间重新分布；
Split++；
if (split == Tsize * 2^level) {
level++；
Split = 0；
如果k尚未插入则尝试插入
}
}
}
11 数据压缩
11.1 数据压缩的条件
假定集合M所有的符号mi可以单独选择，其出现的概率P(mi)是已知的，这些符号都可以用一串0和1编码，则其理论最优平均编码长度为Lave = P(m1)L(m1)+...+P(mn)L(mn)，其中L(mi) = -lg(P(mi))。当数据压缩算法越接近这个值时，其压缩率越高。压缩率用百分数表示，定义为 (输入长度-输出长度)/输出长度。
对于编码方式必须满足1）每个编码字只对应一个符号，2）任意一个编码字都不是其他编码字的前缀。对于一个优化的编码算法还应满足一下条件3）字符出现概率越低，其编码字越长，4）不应出现比已有编码字更短并且不会导致歧义的未使用编码字。
11.2 Huffman编码
11.2.1 基本Huffman编码
Huffman编码算法以一定的规律将根据出现概率排好序的字符集合以二叉树的形式组织起来，最后生成一个编码表。
当我们已知所有符号的概率时采用基本Huffman编码。获取符号概率的方式有两种，第一种是在相当大的文本范例中统计，一个应用是自然语言可以找一本文献来统计。第二种方法是使用要发送的文本来统计，例如计算机科学论文。
Huffman () {
for 每个符号创建一棵树，其中只有一个根节点，并根据符号出现的概率对所有的树排序；
while 剩下多棵树；
提取概率最低的p1，p2(p1 < p2)的两棵树t1，t2，创建一个树，将t1、t2作为它的子树，新树中根节点的概率等于p1+p2；
把每个左子树与0关联，右子树与1关联；
把树从根到该符号对应的概率的叶上所有出现的0和1组合在一起，就为这个符号创建了唯一的编码字
}
Huffman编码算法中将第一步将所有字符根据概率排序并用优先队列的方式实现，因此其具体实现的方式有很多，至少与优先队列实现的方式一样多。
第一种使用单链，每次选取最小两个子树合并树后，删除原来的两个节点，将新节点放在合适位置，直至队列中只有一个节点。
第二种使用双向链，每次选取最小两个子树合并后，删除原来两个节点，将新节点放在队列末尾。
第三种方式，通过递归调用的方式从顶向下创建Huffman树。
createHuffmanTree(prob) {
声明概率p1，p2和Huffman树Htree，
if 在prob上只剩两个概率
return 一个树，其叶节点是p1，p2，根的概率是p1+p2；
else 从prob上删除两个最小概率，将他们赋值给p1，p2；
给prob插入p1+p2；
Htree = createHuffmanTree（prob）；
在Htree中，使叶节点的概率为p1和p2，两个叶节点的父节点概率是p1+p2；
return Htree
}
第四种方式，可以通过最小堆的方式实现。主要步骤为：1）准备三个数组，分别是保存原始的每个元素概率以及再更新堆工程中新建节点概率的probabilites数组；保存有效最小堆的数组indexes，其中的每个元素都是在probabilites中的索引；保存probabilites中每个节点的父节点在probabilites中的索引的一个数组parent，其中元素为负值时表示是右子节点，正值是左子节点。2）删除最小节点，恢复堆属性。3）用刚刚删除的节点加上当前最小节点的值代替当前最小节点，并把其加入probabilites中。4）恢复堆属性。5）更新indexes。6）根据2和3步骤中处理的节点更新parents数组。7）重复2~6直至indexes中只剩一个元素。8）通过probabilites和parents素组，对关键字逆向查找即可得到其对应编码字。
只有当解码器和编码器有相同Huffman树时才能成功解码，解码器确定Huffman树的方法有三个。1）编码器和解码器事先同意使用某一Huffman树，并且都用它来发消息。2）每次发送消息时，编译器都构建一次Huffman树，并将转码表发出。3）解码器和编码器在传输和解码的过程中构建Huffman树。其中第二种方式用得更多。
上述的Huffman树还有提高压缩率的空间，对应X，Y，Z三个符号，我们可以将其所有的出现一定次数以上的符号组合，如xx或者xy或者xyz也看作为一个基本符号，并计算器编码字。
11.2.2 自适应Huffman编码
当我们不确定要发送的文件内容时我们需要采用自适应Huffman编码，这类编码方式对于Huffman树有如下要求，用广度优先法从右向左遍历得到的频率序列必须是降序排列的。
编码开始时此时Huffman树只有一个根节点，其频率为0，其中包含所有会用到的有序符号集合，通常根据大小排序，当输入第一个元素后开始修改树，如果是输入从未出现的元素，则将次元素的编码值表示为n个1接1个0，其中n等于其在未使用字符节点中的索引值+1，并为其创建新节点，将其频率设置为1，并从0节点中删除，在0节点位置用一个新节点替代，其频率为1，并将这个新节点的子节点设置为0节点和新建的1节点。再向上更新各个节点频率，并恢复降序排列的基本要求。如果是输入已输入的元素，则按常规编码方法得到其变字，并更新节点频率，并恢复降序排列的基本要求。
FGKDynamicHuffmanEcoding(symbol s) {
p = 包含符号s的叶节点；
c = s的Huffman编码字；
if p 是 0节点
c = c 与表示0节点中s内存位置的1和0的链接；
在这个节点中编写除s之外的0节点的最后一个符号；
为符号s创建一个新节点q，并把它的计数器设置为1；
p = 新节点，这个节点成为0节点和节点q的父节点；
counter(p) = 1；
在nodes列表中包含两个新节点；
else 递增counter(p);
while p不是根节点
if p改变了同级属性
if 仍包含p的块i的首节点不是parent(p)；
p与首节点交换；
p = parent(p);
递增 counter(p);
return 编码字c；
}
使用自适应Huffman编码法时，同一个符号的编码字是不段变化的，因此单传一个编码表是不现实的，因此当要发送未使用符号的时候，需要将编码字和符号一同发出，解码器在解码时需要对这个符号进行处理，并正确建立Huffman树，即可完成解码。
对于可执行文件来讲，因为其符号本身足够统一，因此其压缩率较低，一般在10%~20%，对于文本文件来讲，其压缩率常常更大。
11.3 Run-Length编码方式
run定义为一组相同出现的字符，其结构是<cm,ch,n>，其中cm是压缩标志，通常选择不常用符号，如果要传送的数据确实包含这个符号，则将这个符号传送两次，ch是压缩的字符，n代表其重复个数。因为run会出现一组三个字符，因此最好用于至少有4个字符的压缩。
Run-length编码的一个列子是关系型数据库，因为部分记录中字段的长度比储存在其中的信息更长，会用一些字符填充，生成很大的run集合。其另外一个例子是图像的压缩。
Run-length编码的确定是对于ABABABABABAB这类数据尽管只有两个符号，但是该编码方式并不能压缩，此时用Huffman是更好的方法，因此因将它们结合使用。
11.4 Ziv-Lempel编码方式
不依赖事先对源数据的了解，而是在数据传输的过程中直接编码，这种方式称为统一编码模式，自适应Huffman树是其中的一种，Ziv-Lempel编码方式也是其中的一种。Ziv-Lempel编码方式有很多版本。
11.4.1 LZ77
在LZ77中，我们维护两个相邻缓存区l1和l2，他们位数相等，大小通常取4，当输入一个元素时，将其中的第一个符号填满l1，同时将其填充在l2的第一个，以后每次输入的元素都填充到l2末尾，当l2满了的时候，查找一个从l1中开始的子字符串，并且这个子字符串正好是l2的一个前缀，同事这个子字符串需要尽量靠近l2，此时记录下子字符串的其实位置i，长度n，及l2中去掉这个前缀后的首字母c，这样就得到一个编码字inc，同时将l2中的元素向前移动n+1位，这时l2可以接收新的输入，最后将每次得到的编码字拼接在一起就是需要传输的编码字。
11.4.2 LZW
在LZW中，我们先对所有的三个字符建立一个转码表，当输入第一个字符时，初始化一个字符串s等于这个字符，在以后的每次输入新字符c时，首先检查s+c是否在表中，如果在则将s更新为S+C，并进行一次输入，如果不在则输出s的转码字，并令s=c，继续下一次输入，直到不再输入时再将s的转码字输出，这些所有的输出就构成了最后需要传输的转码字表。解码时对于数字需要不断地查询这张转码表将其转换为字符，最后就可以成功的解码。
该算法的效率主要取决于1）表的实现方式，2）表的大小，表的大小可以考虑在表中只存缩略字符串，即在之前出现过的字符串前缀用其索引替代。
压缩算法被广泛运用于计算机中。UNIX中三个压缩程序，pack使用Huffman算法，compact使用自适应Huffman算法，compress使用LZW方式编码。根据系统手册，pack压缩文本文件压缩率是25%40%，compact是40%，compress是40%50%。
12 内存管理
程序在运行时，会不断的在堆内存中分配空间和释放空间，必须对内存设计有效的管理方案。多次请求和释放后，堆会裂解为很多小块，当程序请求大小为n的内存空间时，尽管程序中每个可使用小块的总空间远大于n，但是也不能分配内存，这些碎片称为外部碎片。当分配的内存块中大于n时，其中剩余的部分称为内部碎片。一个好的内存管理方法应该在兼顾时间效率的时候尽量避免上述问题。
12.1 sequential-fit方法
sequential-fit方法将所有可用的内存块都链接在一起，搜索列表，查出尺寸大于等于请求的尺寸大小的块。根据其查找顺序分为从整个堆区域头部开始搜索的first-fit，从当前位置开始搜索的next-fit和找出最大快的worst-fit三个方法。找到快过后，分出其中等于请求尺寸的块，剩下的空间以后使用。其中最高效的是first-fit方法。在列表上组织块的方法觉定了算法效率，其中best-fit和worst-fit应该按快的大小来组织链表，其他方法应该按照地址来组织链表。
12.2 nonsequential-fit方法
12.2.1 简单的非顺序内存管理方法
该方法中将堆分为任意尺寸的块，并维护一个尺寸列表，其中第一行为块的尺寸size，第二行为块的最近一次引用的时间标识lastref，第三行为标识该尺寸内存块链表的首地址blocks。当申请空间时，查询是否有reqSize大小的块，如无，则用sequential-fit方法搜索一个块，如果有则将该尺寸的块列表blocks中的第一个块返回，并更新其lastref值为n，n标识当前请求是程序运行以来第n次请求内存，如果该尺寸的blocks中为空时，这将表中对应的这一列删除。并且每次请求内存分配后将标识已经T次没有访问的列删除，T为预先设置的值以防止某些尺寸的块长时间不被使用。
该算法很容易出现内存碎片问题，可以通过以下方法解决。1）在一定数量的内存分配和释放后压缩内存。2）在一定时间后清算尺寸列表。
12.2.2 二进制伙伴系统
另外一个非顺序的内存管理方法是伙伴系统，它把内存分为两个部分。其中典型的就是二进制伙伴系统，假设内存中有2m个存储位置，则每个内存位置的地址分别为0,1,2,...,2m-1，他们都可以用二进制表示。另外该方法需要维护一个数组avail[]，对于数组中每个元素avail[i]表示大小为2i的块的双链表的首元素，其中i=0,1,2,...,m。对应大小为Size的块，伙伴系统会将整个堆平均分成这个大小的一系列块，因此其每个块的首地址是一定的。如果具有相同尺寸的块有多个，那么他们按需排列并两个分为一组，每一组中的两个块互称为伙伴块，他们以二进制表示的首地址位只有在i+1位上不同。
在最初，将avail数组除最后一个元素全部初始化为-1，最后一个元素初始化为整个堆的首地址。请求内存时，根据requSize算出roundedSize = lgroundedSize的上界整数，对于avail数组查找avail[roundedSize]中值，如果不等于-1，则将avail中的这个块链表中的第一个返回，并更新avail数组。如果等于-1，则向上找到availSize[m]不等于-1的值，并将该块内存中第一个进行分裂，并更新avail数组，重复这个操作直至availSize等于roundedSize，则将其中一块内存返回，并标识为保留块，即已经使用，并更新avail数组。
内存块也需要回收，回收方法如下。
include(block)
blockSize = size(block);
buddy = address(block),
while status(buddy) = 0 and size(block) = blockSize and blockSize != lg(内存大小)
把buddy从列表avail[blocksize]中分离出来；
block = block + boddy；
把status(block)设置为0
blockseize++;
buddy = address(现在扩展的block)，且其blockSize+1位设置为其补足块；
block包含在列表avail[blocksize]中；
二进制伙伴系统速度很高，但是当请求size刚刚大于2n，将会造成大量的内部碎片。另外这个算法也会产生一些外部碎片。出现这些问题的原因是二进制伙伴系统仅仅将块分为两个简单相等的部分。
12.2.3 Fibonacci伙伴系统
二进制伙伴系统中每个块可能的尺寸为1，2，4，8,...,2i,...。在Fibonacci伙伴系统中块大小的序列Si满足，当i=0和1时，si=1，其他情况下S(i) = S(i-1) + S(i-1)。Fibonacci伙伴系统的实现方法和二进制伙伴系统类似，但是标识其伙伴块的方法不同。主要通过伙伴位和内存位两个变量来控制块的分裂和合并，分裂时左伙伴位的块伙伴位为0，右伙伴块为1，内存位也是0和1间取值，左伙伴位的内存位继承伙伴位，右伙伴位的内存位继承内存位。合并时块的伙伴位取左伙伴位的内存位，内存位取右伙伴位的内存位。
12.2.4 加权伙伴系统
加权伙伴系统允许分裂更多尺寸的块，其块的尺寸可以是1,2,3,6,8,12,16,24,32,...尺寸为2k的块可以分裂为3×2k-2和2k-2的块，尺寸为3×2k-2可以分解为2k+1和2k的块。加权伙伴系统速度比二进制伙伴系统慢了3倍，其外部碎片也大。
12.2.5 双重伙伴系统
该方法维护两个独立的内存区域，其中一块的尺寸是1,2,4,8,...,2k，另一块的尺寸是3,6,9,18,36,...,3×2k。这种方法内部碎片在二进制系统和加权伙伴系统之间，外部碎片与二进制系统相当。
内部碎片和外部碎片呈反比，一种正处于研究中的方法是尽量减少内部碎片，并将外部碎片压缩到一起，但是合适的压缩算法不易实现。
12.3 垃圾回收
以些语言环境下并不需要关系内存的释放问题，系统会自动在恰当的时间对其进行垃圾回收操作。这个操作分为两个部分，第一步为标记阶段，这个阶段标识出所有当前使用的存储单元，第二步为重新声明阶段，这个节点把所有未标记的存储单元返回给内存池，这个阶段还可以包含堆压缩的过程。只有完全经历上述两个阶段，系统才能使用已经被释放的内存。
12.3.1 标记和重声明
12.3.1.1 标记
简单的标记类似于前序树遍历，找到已使用的内存块根节点，如果一个节点未标记就标记它，再查找其头或者尾指针。用递归形式和显示栈容易出现运行时栈溢出。如果不使用栈又会降低运行速度。为了解决在使用栈时并避免运行时栈溢出，有如下算法。
fastmark (node)
if node 不是原子
标记node；
while (true)
if head(node)和tail(node)都已经标记或是原子
if 栈为空
break;
else node = pop ();
else if 只有tail(node)未标记，也不是原子
标记tail(node);
node = tail(node);
else if 只有head(node)未标记，也不是原子
标记head(node);
node = head(node);
else if head(node)和tail(node)都未标记，也不是原子
标记head(node)和tail(node);
push(tail(node));
node = head(node)；
该算法并未完全解决运行时栈溢出的问题，即使对它进行改进，即从栈中删除已经标记的节点或者已经跟踪到tail和head的节点，偶尔也会用尽空间，出现致命错误。因此使用栈链接倒置技术更安全，尽管其速度较慢。
12.3.1.2 重新声明
在标记完所有存储单元后，从堆的最高地址开始向前查找每个块，将未标记的块放到自由堆中，并将已标记的块重新置为0。每次重新声明都会遍历整个堆的算法应该尽量提升其效率。
12.3.1.3 压缩
当重新声明后，可用堆分散在存储单元中，这时需要压缩。在c++语言中，当堆的空间被压缩后，栈的空间会增加，当堆空间增加时，栈空间减少。压缩的过程是将已用的块中的数据移动集合到一起的过程。
compact()
lo = 堆底；
hi = 堆顶；
while (lo < hi)
while *lo (由lo指向的存储单元已经标记)
lo++;
while *hi未标记
hi--；
取消对存储单元*hi的标记；
*lo = *hi；
tail(*hi--) = lo++;
lo = 堆底；
while (lo <= hi)
if *lo不是原子，且head(*lo) > hi
head(*lo) = tail(head(*lo));
if *lo不是原子，且tail(*lo) > hi
tail(*lo) = tail(tail(*lo));
lo++;
将标记、清楚和压缩的方法分开会造成多余的遍历，最好的方法是将它们集合起来。
12.3.2 复制方法
复制方法将标记、清楚和压缩的方法集合起来。它将内存分为两个去S1和S2，初次在S1中分配内存，当分配指针到达该空间末尾时，所以已使用储存单元有序复制到S2中，以后便在S2中分配空间，当再次触发交换条件时，再将已使用单元向s1中复制，这个操作不断循环执行。因为该算法每一次只用关心已使用存储，单元，因此当垃圾越多时，其效率越快。
12.3.3 递增的垃圾回收
普通的垃圾回收需要等当前垃圾回收操作全部完成后，系统才能继续分配空间，程序才能继续运行。我们可以通过递增的垃圾回收方式在程序执行的过程中进行垃圾回收工作。
12.3.3.1 对于复制方法
将内存分为两个部分fromspace和tospace，在tospace中回收器维护两个指针scan和bottom，其中fromspace是挂起的内存空间，tospace是变异器活动的存储空间，从fromspace中复制过来的单元放在tospace底部，bottom指向队列最后一个元素，scan指向队列中和fromspace中已使用存储单元关联的存储单元。通过精细的控制每次复制存储单元的个数，可以形成程序并未挂起的假象。
变异器分配的存储单元都放在tospace顶部，当需要内存回收时将scan指向元素的内存单元指向fromspace中已使用的内存单元队列中复制k个到tospace中，并更新scan和bottom指针。一次垃圾回收完成，当fromspace中已使用内存单元全部复制到tospace中的时候交换两个空间角色。
12.3.3.1 对于非复制方法
在前面的将标记、清楚和压缩的方法分开这种方法相对于复制方法更简单，因此可以想办法约束遍历次数。Yuasa对其进行了实时约束并得到了可靠的结果。其算法分为两个阶段，第一个阶段用于标记可用的存储单元，第二阶段用于清理堆。但是其不同的是每次标记指标及k1个存储单元，每次清楚的时候只清楚k2个存储单元。第一阶段和第二阶段构建了一次垃圾回收循环，当一次循环结束后开启下一场的循环。
12.3.4 分代垃圾回收
不同类型对象在系统中存在的时间不一样，分代垃圾回收方式考虑到这点将所有被分配单元分成至少两个代龄区域，在对整个堆回收之余，对年轻代进行大量的次要回收，从而提高回收器的效率。通常情况下经过n次垃圾回收后还存活的单元就是老年代。
12.4 小结
影响内存管理算法效率的主要是两个因素，程序的行为和底层硬件的特性。如在LISP机器中，在硬件和微代码中实现读取界限，说明其中的垃圾回收器依赖于该读取界限。
13 字符串匹配
13.1 字符串精确匹配
13.1.1 简单算法
从文本T的第一个字母和模式P的第一个字母开始比较，如果不匹配，就从T的第二个字符开始匹配，以此类推。在最坏情况下其效率为O(|T| |P|)。平均比较次数等于2(|T| - (|P|-1))。
该算法的一种改进方案是，从第二个字母开始比较，最后比较第一个字母，当不匹配时，并且P0=P1时，下次在源文件T中查找的位置可以+2，而不仅仅是+1，这样会增加查找效率。最坏情况下其效率为O(|T| |P|)。
13.1.2 Knuth-Morris-Pratt算法
简单算法效率很低，会有大量不必要的匹配。该算法考虑的模式P中字符串的重复部分，当检测到不匹配时，如果P中已经匹配的子集有重复的部分，下次比较移动的位置应该是将重复部分的前一段又后移动一定的距离，而且重复的部分也不用再比较。这个算法需要先初始化一个next数组，next[j] = -1（j=0时），= n（如果n存在），= 0（其他情况）。其中n表示在p的子字符串p（0...n-1）中能匹配到的后缀等于前缀的字符串长度，前缀后后缀允许重叠。
KnuthMorrisPratt（模式p， 文本T）{
findNext（p，next）
i = j = 0;
while i <= |T| - |P|
while j == -1 or j < |P| and Ti == pj
i++;
j++;
if j == |P|
return 在i-|p|处的匹配
j = next[j]
return 没有匹配
}
findnext(模式p，表next) {
next[0] = -1;
i = 0;
j = -1;
while i < |P|
while j == 0 或 i < |P| 且 pi == pj
i++;
j++;
next[i] = j;
j = next[j];
}
这种算法的效率是O(|P| + |T|)。当使用上面的next，p = abababa，t = ababcdabba-bababad时，第一次比较不匹配的是p4的a和t4的c，根据算法将p向右移动2位，这时比较p2和p4，会重复比较a和c，为了消除这种多余比较。将算法中的Next数组用哪Nexts数组替代。nexts[j] = -1（j=0时），= max: {k: 0 < k < j, p[0...k-1] = p [j - k...j-1], p(k+1) != p(j)}（如果k存在），= 0（其他情况）。
findnexts(模式p，表nexts) {
nexts[0] = -1;
i = 0;
j = -1;
while i < |P|
while j == 0 或 i < |P| 且 pi == pj
i++;
j++;
if pi != pj;
nexts[i] = j;
else nexts[i] = nexts[j];
j = next[j];
}
13.1.3 Boyer-Moore算法
13.1.3.1 简单Boyer-Moore算法
上一个算法中考虑了P中重复部分，将P移动一定的位数从而避免p中的重复比较，但是T中的每个元素还是都参加到了比较之中。Boyer-Moore算法则从P的最右端开始比较，从而跳过T中的某些元素。
在该算法中，模式p的移动遵从以下三个规则：
- 没有出现规则：如果不匹配的字符Ti在P中没有出现，就对齐P0和T(i+1)。
- 右端出现规则：如果Ti和Pj不匹配，且Pj的右端有一个字符ch等于Ti，P就移动一个位置。
- 左端出现规则：如果Pj的左端有一个字符ch等于Ti，Ti就与最靠近Pj的Pk=ch对齐。
为了实现这个算法，比较运算时每个不匹配字符i的递增量保存在函数deltal中，deltal[ch] = |P|(当ch不在P中)，=min{|P|-i-1：pi = ch}(ch在P中)。这个算法执行时间是O(|T| |P|)。
13.1.3.2 改良Boyer-Moore算法
简单Boyer-Moore算法对于出现这样的P=bam-1，T=an。算法会重复检查T中所有检查过的字母，为了提升效率我们可以重新设计delta2数组，其中每个元素delta[j]表示在当pj不匹配时扫描t的递增量。deltal2[j] = min {s + |P|-j-1：1 <= s 且(j <= s或 P(j-s) != pj) 且 j<k<|P| : (k <= s 且 P(k-s) = Pk)}。要确定一个delta2[j]只必须满足两个且连接的三个条件，注意在第三个条件中要求对于所有可能的k值都测试，这样可能有多个s索引满足条件，取其中最小的delta2。
13.1.3.3 Sunday算法
Sunday算法将简单Boyer-Moore算法中的delta[ch]都递增1，这样可以简化其中的三个个移动规则为两个：
- 没有出现规则：如果字符T(i+|P|)没有在P中出现，就对齐P0和T(i+|P|+1)。
- 出现规则：如果P中出现一个字符ch等于T(i+|P|)，就对齐T(i+|P|)和P中最靠近(即最右端)的字符ch。
13.1.4 多次搜索
当压在文本T中查找所有的模式P时，一种简单的办法就是对Boyer-Moore算法进行简单修改，在查找到一个匹配的子字符串后，将P向右移动一个位置。算法的效率为O(|T| |P|)。
但是对于T=ababababa...，P = abababa的所有位置，每当匹配到一个位置后，下一次移动迭代时又需将所有字符进行比较，为了消除这种重复比较，应考虑模式P中的重复信息。P中重复的子字符串称为周期，Boyer-Moore-Galil算法在检测到模式第一次出现的位置之前，与Boyer-Moore算法相同，之后移动模式P = |模式中的周期|个位置，此时只需检查模式模式后面的字符。
13.2 字符串的模糊匹配
对字符串模糊匹配时需要关心什么情况下在文本T中找到的子字符串R是模式P的模糊匹配结果，这时需要定义他们之间的距离，如果距离小于某个临界值k，则将其作为结果返回。通常两个字符串之间的距离可以用将一个字符串转换为另外一个字符串所需的基本操作次数来衡量。基本操作为插入I，删除D和代替S。
13.2.1 字符串的近似性
将两个字符串Q、R的距离定义为d(Q、R)，设D(i,j) = d(Q(0...i-1), R(0...j-1))，表示前缀Q(0...i-1)和R(0...j-1)之间的编辑距离，因此我们可以从Q和R的最小前缀开始逐渐求解整个Q和R的编辑距离。
WangnerFisher(编辑表 dist，字符串Q，字符串R) {
for i = 0 to |Q|
dist[i,0] = i;
for j = 0 to |R|
dist[0,j] = j;
for i = 1 to |Q|
for j = 1 to |R|
x = dist[i-1, j] + 1;
y = dist[i,j-1]+1;
z = dist[i-1,j-1];
if Q(i-1) != R(j-1)
z++
dist[i,j] = min(x,y,z);
}
通过字符串Q和R中元素和符号’-‘组成两个近似字符串Q1和R1，其中’-‘代表在这里需要删除插入一个元素。Q1可以通过最小编辑距离转换为R，R1页可以通过最小转换距离转换为Q。这样的字符串Q1和R1有很多个，可以用以下算法找出组合Q1和R1结果集中的一个。
WagnerFisherPrint(编辑表 dist，字符串Q，字符串R) {
i = |Q|;
j = |R|;
while i != 0 or j != 0
输出对(i,j);
if i > 0 and dist[i-1,j] < dist[i,j]
sQ.push(Q(i-1));
sR.push('-');
i--;
else if j > 0 and dist[i,j-1] < dist[i,j]
sQ.push('-')
sR.push(R(j-1))；
j--;
else if (i > 0 and j > 0) and ((dist[i-1,j-1] == dist[i,j] and Q(i-1) == R(j-1)) or (dist[i-1,j-1] < dist[i,j] and Q(i-1) != R(j-1)))
sQ.push(Q(i-1));
sR.push(R(j-1))；
i--;
j--;
打印栈sQ；
打印栈sR；
}
13.2.2 有k个错误的字符串匹配
对于有k个错误的字符串匹配，其在UNIX系统中实现为agrep命令。其基于二进制位操作，算法实现如下。
WuManber(模式P，文本T，int k) {
matchBit = 1;
for i = 1 to |p|-1
matchBit <<= 1;
初始化 charactersInp;
oldState[0] = 0;
for e = 1 to k
oldState[0] = (oldState[e-1] << 1) | 1;
for i = 0 to |T|-1
state[0] = ((state[0]) << 1) | 1) & charactersInp[Ti];
for e = 1 to k
state[e] = ((oldState[e] << 1) | 1) & charactersInp[Ti] | //插入/替换 以及 删除/匹配
((oldState[e-1]) << 1) | 1) | //替换
((state[e-1] << 1) | 1) | //删除
oldState[e-1]; //插入
for e =0 to k
oldState[e] = state[e];
if matchBit & state[k] != 0;
输出 "a match ending at" i；
}
14 引用
本文章是在学习原著Data Structure and Algorithms in C++, 4th Edition时的读书笔记，文中结论和数据以及代码块都出自原文。
