算法工程珠玑

本书由算法工程领域权威学者Paolo Ferragina撰写，是算法工程领域的扛鼎之作。作者结合多年谷歌、IBM等知名企业的实战经验与比萨大学等高校教学积累，破解“算法理论有效但实操无用” 的困局。书中通过一系列挑战性问题，展示从基础到进阶的高效算法解决方案，提供覆盖 RAM 到外部存储的全场景可复用框架，手把手引导读者将理论转化为可量化的效率提升。特别关注I/O复杂度与工程实现，引入两级存储模型，帮助读者将算法从本地转移到生产环境。多位知名教授力荐，是程序员与软件工程师提升算法实操能力的必备手册。

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

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