許多算法教材都側(cè)重于大O符號(hào)和基本設(shè)計(jì)原則。本書提供了一種獨(dú)特的方法，將設(shè)計(jì)和分析提升到可預(yù)測(cè)的實(shí)際效率水平，討論了大數(shù)據(jù)應(yīng)用開發(fā)過(guò)程中出現(xiàn)的核心和經(jīng)典算法問(wèn)題，并提出了日益復(fù)雜和高效的優(yōu)雅解決方案。書中分析了經(jīng)典的 RAM 模型和更具實(shí)際意義的外部?jī)?nèi)存模型（允許執(zhí)行 I/O 復(fù)雜性評(píng)估）中的解決方案，各章內(nèi)容涵蓋各種數(shù)據(jù)類型，包括整數(shù)、字符串、樹和圖，以及采樣、排序、數(shù)據(jù)壓縮、字典和文本搜索等算法工具，最后是壓縮數(shù)據(jù)結(jié)構(gòu)的最新發(fā)展。算法解決方案附有詳細(xì)的偽代碼和許多運(yùn)行示例，適合對(duì)高效處理大數(shù)據(jù)感興趣的學(xué)生、研究人員和其他專業(yè)人士閱讀。
本書由算法工程領(lǐng)域權(quán)威學(xué)者Paolo Ferragina撰寫，是算法工程領(lǐng)域的扛鼎之作。作者結(jié)合多年谷歌、IBM等知名企業(yè)的實(shí)戰(zhàn)經(jīng)驗(yàn)與比薩大學(xué)等高校教學(xué)積累，破解算法理論有效但實(shí)操無(wú)用 的困局。書中通過(guò)一系列挑戰(zhàn)性問(wèn)題，展示從基礎(chǔ)到進(jìn)階的高效算法解決方案，提供覆蓋 RAM 到外部存儲(chǔ)的全場(chǎng)景可復(fù)用框架，手把手引導(dǎo)讀者將理論轉(zhuǎn)化為可量化的效率提升。特別關(guān)注I/O復(fù)雜度與工程實(shí)現(xiàn)，引入兩級(jí)存儲(chǔ)模型，幫助讀者將算法從本地轉(zhuǎn)移到生產(chǎn)環(huán)境。多位知名教授力薦，是程序員與軟件工程師提升算法實(shí)操能力的手冊(cè)。
前 言
本書為程序員和軟件工程師提供了寶貴的忠告：在算法工程領(lǐng)域，無(wú)論個(gè)人天資如何聰穎，不深思熟慮是無(wú)法找到現(xiàn)實(shí)問(wèn)題的合理解決方案的；面對(duì)龐雜的現(xiàn)實(shí)問(wèn)題、復(fù)雜的機(jī)器、挑剔的用戶、資源消耗巨大的應(yīng)用程序和精密的算法工具，你需要接受培訓(xùn)才能成為一名算法工程師。
我們將通過(guò)探討一系列具有挑戰(zhàn)性的問(wèn)題來(lái)展示一系列優(yōu)雅且高效的算法解決方案。在選擇章節(jié)主題時(shí)，我們主要考慮兩個(gè)目標(biāo)：一方面，為讀者提供算法工程工具箱，幫助他們解決涉及海量數(shù)據(jù)集的編程問(wèn)題；另一方面，匯集我在讀碩士/博士時(shí)希望學(xué)習(xí)到的課程內(nèi)容。部分章節(jié)的標(biāo)題帶有上標(biāo)符號(hào)，這表示該部分為進(jìn)階內(nèi)容，可以跳過(guò)，這并不會(huì)影響整體的閱讀體驗(yàn)。最后，對(duì)于熱愛(ài)編程的讀者，我想指出本書的另一個(gè)特點(diǎn)，即數(shù)組索引從1開始，而不是通常采用的從0開始，因?yàn)檫@樣可以使算法的表述更簡(jiǎn)潔，而且公式也不會(huì)因±1的修正而變得復(fù)雜。
本書的風(fēng)格和內(nèi)容是與許多研究員同事和學(xué)生經(jīng)過(guò)長(zhǎng)時(shí)間的啟發(fā)性討論（有時(shí)是艱苦而令人疲憊的）后形成的。其中部分內(nèi)容來(lái)自2004年以來(lái)我在比薩大學(xué)和其他國(guó)際學(xué)校中教授的信息檢索和高級(jí)算法課程。值得一提的是，這些內(nèi)容的初稿來(lái)源于2009年9月至12月參加比薩大學(xué)和圣安娜高級(jí)研究學(xué)院合作開設(shè)的計(jì)算機(jī)科學(xué)與網(wǎng)絡(luò)專業(yè)的算法工程碩士課程的學(xué)生的筆記。另外一些來(lái)源于2010年3月在意大利貝爾蒂諾羅國(guó)際春季學(xué)校（BISS）中參加我教授的海量數(shù)據(jù)集高級(jí)算法課程的博士生的筆記。我將這些筆記作為某些章節(jié)的基礎(chǔ)。當(dāng)然，得益于2010年以來(lái)參加算法工程課程的眾多學(xué)生提出的建議和反饋，這些筆記在隨后的幾年中經(jīng)過(guò)了大量的修訂和完善。
特別感謝Antonio Boffa、Andrea Guerra、Francesco Tosoni和Giorgio Vinciguerra仔細(xì)閱讀了本書的最新版本，感謝Gemma Martini對(duì)第15章的貢獻(xiàn)，感謝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，感謝他們多年來(lái)對(duì)這些主題進(jìn)行的許多有趣且具有挑戰(zhàn)性的探討。最后，我要衷心感謝我的導(dǎo)師 Fabrizio Luccio，他不斷激發(fā)我的研究熱情，并以簡(jiǎn)潔（但并不簡(jiǎn)單）的方式引導(dǎo)我去感受教學(xué)和寫作的樂(lè)趣。至于我是否成功實(shí)現(xiàn)了這一目標(biāo)，就留給讀者評(píng)判吧。
我的終極愿望是，當(dāng)讀者翻閱這些章節(jié)時(shí)，能夠感受到我初次邂逅這些算法解決方案時(shí)的那種快樂(lè)和興奮，從而激發(fā)自己對(duì)算法世界進(jìn)行進(jìn)一步探索，為學(xué)術(shù)追求和職業(yè)生涯尋找靈感。計(jì)算機(jī)編程是一門藝術(shù)，但要達(dá)到藝術(shù)的巔峰，需要借助出色的工具。
保羅·費(fèi)拉吉納（Paolo Ferragina）是意大利比薩大學(xué)算法方面的教授，同時(shí)也是馬克斯·普朗克信息學(xué)研究所的博士后。他曾在比薩大學(xué)擔(dān)任信息通信技術(shù)學(xué)院副院長(zhǎng)和應(yīng)用研究與創(chuàng)新學(xué)院的副院長(zhǎng)，以及計(jì)算機(jī)科學(xué)博士項(xiàng)目的負(fù)責(zé)人。他的研究重點(diǎn)是用于大數(shù)據(jù)壓縮、挖掘和檢索的算法與數(shù)據(jù)結(jié)構(gòu)。他曾與AT&T、彭博社、谷歌、ST微電子、提斯卡利和雅虎合作，并與合作者共同獲得了著名的Paris Kanellakis理論與實(shí)踐獎(jiǎng)，以及其他多個(gè)國(guó)際獎(jiǎng)項(xiàng)。他已獲得多項(xiàng)專利，在著名會(huì)議和期刊上發(fā)表了170多篇論文。他還曾在馬克斯·普朗克信息學(xué)研究所、北得克薩斯大學(xué)、紐約大學(xué)庫(kù)朗研究所、麻省總醫(yī)院/哈佛醫(yī)學(xué)院、AT&T、谷歌、IBM研究院和雅虎從事過(guò)研究工作。
目 錄
譯者序
前言
第1章 概述 1
參考文獻(xiàn) 8
第2章 準(zhǔn)備活動(dòng) 9
2.1 時(shí)間復(fù)雜度為3次方的算法 10
2.2 時(shí)間復(fù)雜度為2次方的算法 12
2.3 線性時(shí)間算法 13
2.4 另一種時(shí)間復(fù)雜度為線性的算法 16
2.5 有趣的變體 18
參考文獻(xiàn) 22
第3章 隨機(jī)抽樣 23
3.1 磁盤模型和已知序列長(zhǎng)度 24
3.2 流式模型和已知序列長(zhǎng)度 26
3.3 流式模型和未知序列長(zhǎng)度 29
參考文獻(xiàn) 32
第4章 列表排名 33
4.1 指針跳躍技術(shù) 34
4.2 兩級(jí)存儲(chǔ)中的并行算法模擬 36
4.3 分治技術(shù) 39
4.3.1 隨機(jī)化的解決方案 42
4.3.2 確定性拋硬幣 42
參考文獻(xiàn) 44
第5章 原子項(xiàng)排序 45
5.1 基于歸并的排序范式 46
5.1.1 終止遞歸 48
5.1.2 雪犁技術(shù) 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 選擇中心點(diǎn) 62
5.3.3 限制額外的工作空間 66
5.3.4 從二分到多分快速排序 67
5.4 使用多磁盤排序 70
參考文獻(xiàn) 73
第6章 集合交集 75
6.1 合并式方法 77
6.2 互相分區(qū) 78
6.3 倍增搜索 80
6.4 兩級(jí)存儲(chǔ)方法 82
參考文獻(xiàn) 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 關(guān)于兩級(jí)存儲(chǔ)模型的觀察 97
參考文獻(xiàn) 98
第8章 字典問(wèn)題 99
8.1 直接尋址表 101
8.2 哈希表 101
8.3 通用哈希 104
8.4 簡(jiǎn)單的（靜態(tài)）完美哈希表 109
8.5 布谷鳥哈希 114
8.6 更多關(guān)于靜態(tài)哈希和完美哈希：
最小化和有序化 120
8.7 布隆過(guò)濾器 125
8.7.1 空間占用的下界 128
8.7.2 簡(jiǎn)單的應(yīng)用 129
參考文獻(xiàn) 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é)構(gòu) 153
參考文獻(xiàn) 157
第10章 子串搜索 158
10.1 符號(hào)與術(shù)語(yǔ) 159
10.2 后綴數(shù)組 160
10.2.1 子字符串搜索問(wèn)題 160
10.2.2 LCP數(shù)組及其構(gòu)建 164
10.2.3 后綴數(shù)組的構(gòu)建 167
10.3 后綴樹 179
10.3.1 子字符串查找問(wèn)題 181
10.3.2 基于后綴數(shù)組的構(gòu)建與反向
構(gòu)建 182
10.3.3 McCreight算法 184
10.4 一些有趣的問(wèn)題 188
10.4.1 近似模式匹配 188
10.4.2 LCA、RMQ和笛卡兒樹 190
10.4.3 文本壓縮 196
10.4.4 文本挖掘 198
參考文獻(xiàn) 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
參考文獻(xiàn) 215
第12章 統(tǒng)計(jì)編碼 216
12.1 霍夫曼編碼 217
12.2 算術(shù)編碼 227
12.2.1 位流和二元分?jǐn)?shù) 228
12.2.2 壓縮算法 229
12.2.3 解壓縮算法 231
12.2.4 效率 233
12.2.5 區(qū)間編碼 236
12.3 通過(guò)部分匹配進(jìn)行預(yù)測(cè) 241
參考文獻(xiàn) 246
第13章 基于字典的壓縮技術(shù) 247
13.1 LZ77算法 248
13.2 LZ78算法 251
13.3 LZW算法 253
13.4 關(guān)于壓縮技術(shù)的最優(yōu)性 255
參考文獻(xiàn) 257
第14章 塊排序壓縮技術(shù) 259
14.1 BWT 260
14.1.1 正向變換 260
14.1.2 反向變換 262
14.2 另外兩種簡(jiǎn)單轉(zhuǎn)換 265
14.2.1 MTF變換 266
14.2.2 RLE變換 269
14.3 bzip壓縮 270
14.4 關(guān)于壓縮提升 273
14.5 關(guān)于壓縮索引 275
參考文獻(xiàn) 279
第15章 壓縮的數(shù)據(jù)結(jié)構(gòu) 280
15.1 （二進(jìn)制）數(shù)組的壓縮表示 280
15.1.1 通過(guò)Rank和Select實(shí)現(xiàn)的簡(jiǎn)潔
方案 281
15.1.2 通過(guò) Elias-Fano 編碼的壓縮
解決方案 288
15.2 樹的簡(jiǎn)潔表示法 290
15.2.1 二叉樹 291
15.2.2 任意樹 295
15.3 圖的簡(jiǎn)潔表示法 298
15.3.1 Web圖的情況 299
15.3.2 通用圖的情況 302
參考文獻(xiàn) 305
第16章 結(jié)論 306
書單推薦![算法工程珠璣 [意]保羅·費(fèi)拉吉納](/images/noimages.gif)
