許多算法教材都側(cè)重于大O符號和基本設計原則。本書提供了一種獨特的方法，將設計和分析提升到可預測的實際效率水平，討論了大數(shù)據(jù)應用開發(fā)過程中出現(xiàn)的核心和經(jīng)典算法問題，并提出了日益復雜和高效的優(yōu)雅解決方案。書中分析了經(jīng)典的 RAM 模型和更具實際意義的外部內(nèi)存模型（允許執(zhí)行 I/O 復雜性評估）中的解決方案，各章內(nèi)容涵蓋各種數(shù)據(jù)類型，包括整數(shù)、字符串、樹和圖，以及采樣、排序、數(shù)據(jù)壓縮、字典和文本搜索等算法工具，最后是壓縮數(shù)據(jù)結(jié)構的最新發(fā)展。算法解決方案附有詳細的偽代碼和許多運行示例，適合對高效處理大數(shù)據(jù)感興趣的學生、研究人員和其他專業(yè)人士閱讀。
本書由算法工程領域權威學者Paolo Ferragina撰寫，是算法工程領域的扛鼎之作。作者結(jié)合多年谷歌、IBM等知名企業(yè)的實戰(zhàn)經(jīng)驗與比薩大學等高校教學積累，破解算法理論有效但實操無用 的困局。書中通過一系列挑戰(zhàn)性問題，展示從基礎到進階的高效算法解決方案，提供覆蓋 RAM 到外部存儲的全場景可復用框架，手把手引導讀者將理論轉(zhuǎn)化為可量化的效率提升。特別關注I/O復雜度與工程實現(xiàn)，引入兩級存儲模型，幫助讀者將算法從本地轉(zhuǎn)移到生產(chǎn)環(huán)境。多位知名教授力薦，是程序員與軟件工程師提升算法實操能力的手冊。
前 言
本書為程序員和軟件工程師提供了寶貴的忠告：在算法工程領域，無論個人天資如何聰穎，不深思熟慮是無法找到現(xiàn)實問題的合理解決方案的；面對龐雜的現(xiàn)實問題、復雜的機器、挑剔的用戶、資源消耗巨大的應用程序和精密的算法工具，你需要接受培訓才能成為一名算法工程師。
我們將通過探討一系列具有挑戰(zhàn)性的問題來展示一系列優(yōu)雅且高效的算法解決方案。在選擇章節(jié)主題時，我們主要考慮兩個目標：一方面，為讀者提供算法工程工具箱，幫助他們解決涉及海量數(shù)據(jù)集的編程問題；另一方面，匯集我在讀碩士/博士時希望學習到的課程內(nèi)容。部分章節(jié)的標題帶有上標符號，這表示該部分為進階內(nèi)容，可以跳過，這并不會影響整體的閱讀體驗。最后，對于熱愛編程的讀者，我想指出本書的另一個特點，即數(shù)組索引從1開始，而不是通常采用的從0開始，因為這樣可以使算法的表述更簡潔，而且公式也不會因±1的修正而變得復雜。
本書的風格和內(nèi)容是與許多研究員同事和學生經(jīng)過長時間的啟發(fā)性討論（有時是艱苦而令人疲憊的）后形成的。其中部分內(nèi)容來自2004年以來我在比薩大學和其他國際學校中教授的信息檢索和高級算法課程。值得一提的是，這些內(nèi)容的初稿來源于2009年9月至12月參加比薩大學和圣安娜高級研究學院合作開設的計算機科學與網(wǎng)絡專業(yè)的算法工程碩士課程的學生的筆記。另外一些來源于2010年3月在意大利貝爾蒂諾羅國際春季學校（BISS）中參加我教授的海量數(shù)據(jù)集高級算法課程的博士生的筆記。我將這些筆記作為某些章節(jié)的基礎。當然，得益于2010年以來參加算法工程課程的眾多學生提出的建議和反饋，這些筆記在隨后的幾年中經(jīng)過了大量的修訂和完善。
特別感謝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，感謝他們多年來對這些主題進行的許多有趣且具有挑戰(zhàn)性的探討。最后，我要衷心感謝我的導師 Fabrizio Luccio，他不斷激發(fā)我的研究熱情，并以簡潔（但并不簡單）的方式引導我去感受教學和寫作的樂趣。至于我是否成功實現(xiàn)了這一目標，就留給讀者評判吧。
我的終極愿望是，當讀者翻閱這些章節(jié)時，能夠感受到我初次邂逅這些算法解決方案時的那種快樂和興奮，從而激發(fā)自己對算法世界進行進一步探索，為學術追求和職業(yè)生涯尋找靈感。計算機編程是一門藝術，但要達到藝術的巔峰，需要借助出色的工具。
保羅·費拉吉納（Paolo Ferragina）是意大利比薩大學算法方面的教授，同時也是馬克斯·普朗克信息學研究所的博士后。他曾在比薩大學擔任信息通信技術學院副院長和應用研究與創(chuàng)新學院的副院長，以及計算機科學博士項目的負責人。他的研究重點是用于大數(shù)據(jù)壓縮、挖掘和檢索的算法與數(shù)據(jù)結(jié)構。他曾與AT&T、彭博社、谷歌、ST微電子、提斯卡利和雅虎合作，并與合作者共同獲得了著名的Paris Kanellakis理論與實踐獎，以及其他多個國際獎項。他已獲得多項專利，在著名會議和期刊上發(fā)表了170多篇論文。他還曾在馬克斯·普朗克信息學研究所、北得克薩斯大學、紐約大學庫朗研究所、麻省總醫(yī)院/哈佛醫(yī)學院、AT&T、谷歌、IBM研究院和雅虎從事過研究工作。
目 錄
譯者序
前言
第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 互相分區(qū) 78
6.3 倍增搜索 80
6.4 兩級存儲方法 82
參考文獻 84
第7章 字符串排序 85
7.1 字符串排序下界 86
7.2 基數(shù)排序 87
7.2.1 最高有效位優(yōu)先 87
7.2.2 最低有效位優(yōu)先 90
7.3 多鍵快速排序 93
7.4 關于兩級存儲模型的觀察 97
參考文獻 98
第8章 字典問題 99
8.1 直接尋址表 101
8.2 哈希表 101
8.3 通用哈希 104
8.4 簡單的（靜態(tài)）完美哈希表 109
8.5 布谷鳥哈希 114
8.6 更多關于靜態(tài)哈希和完美哈希：
最小化和有序化 120
8.7 布隆過濾器 125
8.7.1 空間占用的下界 128
8.7.2 簡單的應用 129
參考文獻 130
第9章 字符串前綴搜索 132
9.1 字符串指針數(shù)組 133
9.1.1 字符串的連續(xù)分配 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 在磁盤上打包樹的結(jié)構 153
參考文獻 157
第10章 子串搜索 158
10.1 符號與術語 159
10.2 后綴數(shù)組 160
10.2.1 子字符串搜索問題 160
10.2.2 LCP數(shù)組及其構建 164
10.2.3 后綴數(shù)組的構建 167
10.3 后綴樹 179
10.3.1 子字符串查找問題 181
10.3.2 基于后綴數(shù)組的構建與反向
構建 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章 整數(shù)編碼 201
11.1 Elias編碼：和 204
11.2 Rice編碼 205
11.3 PForDelta編碼 206
11.4 可變字節(jié)編碼和(s,c)密集編碼 207
11.5 插值編碼 210
11.6 Elias-Fano編碼 212
參考文獻 215
第12章 統(tǒng)計編碼 216
12.1 霍夫曼編碼 217
12.2 算術編碼 227
12.2.1 位流和二元分數(shù) 228
12.2.2 壓縮算法 229
12.2.3 解壓縮算法 231
12.2.4 效率 233
12.2.5 區(qū)間編碼 236
12.3 通過部分匹配進行預測 241
參考文獻 246
第13章 基于字典的壓縮技術 247
13.1 LZ77算法 248
13.2 LZ78算法 251
13.3 LZW算法 253
13.4 關于壓縮技術的最優(yōu)性 255
參考文獻 257
第14章 塊排序壓縮技術 259
14.1 BWT 260
14.1.1 正向變換 260
14.1.2 反向變換 262
14.2 另外兩種簡單轉(zhuǎn)換 265
14.2.1 MTF變換 266
14.2.2 RLE變換 269
14.3 bzip壓縮 270
14.4 關于壓縮提升 273
14.5 關于壓縮索引 275
參考文獻 279
第15章 壓縮的數(shù)據(jù)結(jié)構 280
15.1�。ǘM制）數(shù)組的壓縮表示 280
15.1.1 通過Rank和Select實現(xiàn)的簡潔
方案 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章 結(jié)論 306
書單推薦![算法工程珠璣 [意]保羅·費拉吉納](/images/noimages.gif)
