目录

●译者序
前言
第1章概述1
参考文献8
第2章准备活动9
2.1时间复杂度为3次方的算法10
2.2时间复杂度为2次方的算法12
2.3线性时间算法13
2.4另一种时间复杂度为线性的算法16
2.5有趣的变体∞18
参考文献22
第3章随机抽样23
3.1磁盘模型和已知序列长度24
3.2流式模型和已知序列长度26
3.3流式模型和未知序列长度29
参考文献32
第4章列表排名33
4.1指针跳跃技术34
4.2两级存储中的并行算法模拟36
4.3分治技术39
4.3.1随机化的解决方案42
4.3.2确定性抛硬币∞42
参考文献44
第5章原子项排序45
5.1基于归并的排序范式46
5.1.1终止递归48
5.1.2雪犁技术∞49
5.1.3从二分到多分归并排序52
5.2下界54
5.2.1排序下界55
5.2.2排列下界57
5.3基于分布的排序范式59
5.3.1从二分法到三分法60
5.3.2选择中心点62
5.3.3额外的工作空间66
5.3.4从二分到多分快速排序67
5.4使用多磁盘排序∞70
参考文献73
第6章集合交集75
6.1合并式方法77
6.2互相分区78
6.3倍增搜索80
6.4两级存储方法82
参考文献84
第7章字符串排序85
7.1字符串排序下界86
7.2基数排序87
7.2.1优选有效位优先87
7.2.2大力度优惠有效位优先90
7.3多键快速排序93
7.4关于两级存储模型的观察∞97
参考文献98
第8章字典问题99
8.1直接寻址表101
8.2哈希表101
8.3通用哈希104
8.4简单的（静态）完美哈希表109
8.5布谷鸟哈希114
8.6更多关于静态哈希和完美哈希：
最小化和有序化120
8.7布隆过滤器125
8.7.1空间占用的下界128
8.7.2简单的应用129
参考文献130
第9章字符串前缀搜索132
9.1字符串指针数组133
9.1.1字符串的连续分配134
9.1.2前端编码135
9.2局部保持的前端编码∞138
9.3插值搜索140
9.4压缩字典树143
9.5Patricia字典树146
9.6管理海量字典∞150
9.6.1字符串B-树151
9.6.2在磁盘上打包树的结构153
参考文献157
第10章子串搜索158
10.1符号与术语159
10.2后缀数组160
10.2.1子字符串搜索问题160
10.2.2LCP数组及其构建∞164
10.2.3后缀数组的构建167
10.3后缀树179
10.3.1子字符串查找问题181
10.3.2基于后缀数组的构建与反向
构建182
10.3.3McCreight算法∞184
10.4一些有趣的问题188
10.4.1近似模式匹配188
10.4.2LCA、RMQ和笛卡儿树190
10.4.3文本压缩196
10.4.4文本挖掘198
参考文献200
第11章整数编码201
11.1Elias编码：γ和δ204
11.2Rice编码205
11.3PForDelta编码206
11.4可变字节编码和(s,c)密集编码207
11.5插值编码210
11.6Elias-Fano编码212
参考文献215
第12章统计编码216
12.1霍夫曼编码217
12.2算术编码227
12.2.1位流和二元分数228
12.2.2压缩算法229
12.2.3解压缩算法231
12.2.4效率233
12.2.5区间编码∞236
12.3通过部分匹配进行预测∞241
参考文献246
第13章基于字典的压缩技术247
13.1LZ77算法248
13.2LZ78算法251
13.3LZW算法253
13.4关于压缩技术的很优性∞255
参考文献257
第14章块排序压缩技术259
14.1BWT260
14.1.1正向变换260
14.1.2反向变换262
14.2另外两种简单转换265
14.2.1MTF变换266
14.2.2RLE变换269
14.3bzip压缩270
14.4关于压缩提升∞273
14.5关于压缩索引∞275
参考文献279
第15章压缩的数据结构280
15.1（二进制）数组的压缩表示280
15.1.1通过Rank和Select实现的简洁
方案281
15.1.2通过Elias-Fano编码的压缩
解决方案288
15.2树的简洁表示法290
15.2.1二叉树291
15.2.2任意树295
15.3图的简洁表示法298
15.3.1Web图的情况299
15.3.2通用图的情况302
参考文献305
第16章结论306