算法工程珠玑 [意]保罗·费拉吉纳_[意]保罗·费拉吉纳（PaoloFerragina）_9787111784500

许多算法教材都侧重于大O符号和基本设计原则。本书提供了一种独特的方法，将设计和分析提升到可预测的实际效率水平，讨论了大数据应用开发过程中出现的核心和经典算法问题，并提出了日益复杂和高效的优雅解决方案。书中分析了经典的 RAM 模型和更具实际意义的外部内存模型（允许执行 I/O 复杂性评估）中的解决方案，各章内容涵盖各种数据类型，包括整数、字符串、树和图，以及采样、排序、数据压缩、字典和文本搜索等算法工具，最后是压缩数据结构的最新发展。算法解决方案附有详细的伪代码和许多运行示例，适合对高效处理大数据感兴趣的学生、研究人员和其他专业人士阅读。

前　　言
本书为程序员和软件工程师提供了宝贵的忠告：在算法工程领域，无论个人天资如何聪颖，不深思熟虑是无法找到现实问题的合理解决方案的；面对庞杂的现实问题、复杂的机器、挑剔的用户、资源消耗巨大的应用程序和精密的算法工具，你需要接受培训才能成为一名算法工程师。
我们将通过探讨一系列具有挑战性的问题来展示一系列优雅且高效的算法解决方案。在选择章节主题时，我们主要考虑两个目标：一方面，为读者提供算法工程工具箱，帮助他们解决涉及海量数据集的编程问题；另一方面，汇集我在读硕士/博士时希望学习到的课程内容。部分章节的标题带有上标符号，这表示该部分为进阶内容，可以跳过，这并不会影响整体的阅读体验。最后，对于热爱编程的读者，我想指出本书的另一个特点，即数组索引从1开始，而不是通常采用的从0开始，因为这样可以使算法的表述更简洁，而且公式也不会因±1的修正而变得复杂。
本书的风格和内容是与许多研究员同事和学生经过长时间的启发性讨论（有时是艰苦而令人疲惫的）后形成的。其中部分内容来自2004年以来我在比萨大学和其他国际学校中教授的信息检索和高级算法课程。值得一提的是，这些内容的初稿来源于2009年9月至12月参加比萨大学和圣安娜高级研究学院合作开设的计算机科学与网络专业的算法工程硕士课程的学生的笔记。另外一些来源于2010年3月在意大利贝尔蒂诺罗国际春季学校（BISS）中参加我教授的海量数据集高级算法课程的博士生的笔记。我将这些笔记作为某些章节的基础。当然，得益于2010年以来参加算法工程课程的众多学生提出的建议和反馈，这些笔记在随后的几年中经过了大量的修订和完善。
特别感谢Antonio Boffa、Andrea Guerra、Francesco Tosoni和Giorgio Vinciguerra仔细阅读了本书的最新版本，感谢Gemma Martini对第15章的贡献，感谢Riccardo Manetti帮忙整理tikz图表。还要感谢我的博士生和同事们：Jyrki Alakuijala、Ricardo Baeza-Yates、Lorenzo Bellomo、Massi Ciaramita、Marco Cornolti、Martin Farach-Colton、Andrea Farruggia、Raffaele Giancarlo、Roberto Grossi、Antonio Gullì、Luigi Laura、Veli Makinen、Giovanni Manzini、Kurt Mehlhorn、Ulli Meyer、Bud Mishra、S. Muthukrishnan、Gonzalo Navarro、Igor Nitto、Linda Pagli、Francesco Piccinno、Luca Pinello、Marco Ponza、Prabhakar Raghavan、Peter Sanders、Rossano Venturini和Jeff S. Vitter，感谢他们多年来对这些主题进行的许多有趣且具有挑战性的探讨。最后，我要衷心感谢我的导师 Fabrizio Luccio，他不断激发我的研究热情，并以简洁（但并不简单）的方式引导我去感受教学和写作的乐趣。至于我是否成功实现了这一目标，就留给读者评判吧。
我的终极愿望是，当读者翻阅这些章节时，能够感受到我初次邂逅这些算法解决方案时的那种快乐和兴奋，从而激发自己对算法世界进行进一步探索，为学术追求和职业生涯寻找灵感。计算机编程是一门艺术，但要达到艺术的巅峰，需要借助出色的工具。

目　　录
译者序
前言
第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.5　Patricia字典树 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.2　LCP数组及其构建 164
10.2.3　后缀数组的构建 167
10.3　后缀树 179
10.3.1　子字符串查找问题 181
10.3.2　基于后缀数组的构建与反向
构建 182
10.3.3　McCreight算法 184
10.4　一些有趣的问题 188
10.4.1　近似模式匹配 188
10.4.2　LCA、RMQ和笛卡儿树 190
10.4.3　文本压缩 196
10.4.4　文本挖掘 198
参考文献 200
第11章　整数编码 201
11.1　Elias编码：和 204
11.2　Rice编码 205
11.3　PForDelta编码 206
11.4　可变字节编码和(s,c)密集编码 207
11.5　插值编码 210
11.6　Elias-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.1　LZ77算法 248
13.2　LZ78算法 251
13.3　LZW算法 253
13.4　关于压缩技术的最优性 255
参考文献 257
第14章　块排序压缩技术 259
14.1　BWT 260
14.1.1　正向变换 260
14.1.2　反向变换 262
14.2　另外两种简单转换 265
14.2.1　MTF变换 266
14.2.2　RLE变换 269
14.3　bzip压缩 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.1　Web图的情况 299
15.3.2　通用图的情况 302
参考文献 305
第16章　结论 306

你还可能感兴趣

我要评论