本書的主題是數(shù)據(jù)壓縮,也就是用最緊湊的方式來表示數(shù)據(jù)。本書先講解了5類數(shù)據(jù)壓縮算法,即變長編碼、統(tǒng)計(jì)壓縮、字典編碼、上下文模型和多上下文模型,然后介紹了香農(nóng)的信息論,以及怎樣通過各種方法來突破熵,如統(tǒng)計(jì)編碼、自適應(yīng)統(tǒng)計(jì)編碼、字典轉(zhuǎn)換、上下文數(shù)據(jù)轉(zhuǎn)換、數(shù)據(jù)建模等。本書還討論了數(shù)據(jù)壓縮中的一些要點(diǎn),如多媒體數(shù)據(jù)壓縮和通用壓縮,并介紹了有損數(shù)據(jù)壓縮。本書最后說明了數(shù)據(jù)壓縮與你、你的公司以及未來的技術(shù)是如何相互關(guān)聯(lián)的。
要在5G時(shí)代成功獲取用戶并提升轉(zhuǎn)化率,離不開數(shù)據(jù)壓縮的專業(yè)技能。本書從理論和實(shí)踐兩方面入手,面向開發(fā)人員講解數(shù)據(jù)壓縮算法,并幫助開發(fā)人員選擇合適的數(shù)據(jù)壓縮工具。書中通過講解清晰、步驟詳細(xì)的示例,將數(shù)據(jù)壓縮算法化繁為簡,幫助開發(fā)人員做出正確的有關(guān)數(shù)據(jù)壓縮的商業(yè)決策,從而實(shí)現(xiàn)客戶更多、事業(yè)更興、利潤更高。
●了解5類數(shù)據(jù)壓縮算法:變長編碼、統(tǒng)計(jì)壓縮、字典編碼、上下文模型、多上下文模型
●了解數(shù)據(jù)、場景和算法,以選擇匹配的數(shù)據(jù)壓縮工具
●選擇合適的圖像壓縮算法,權(quán)衡圖像質(zhì)量與文件大小
●學(xué)習(xí)如何壓縮客戶端和服務(wù)器生成的數(shù)據(jù)
●了解與數(shù)據(jù)壓縮算法有關(guān)的名人及其趣事
柯爾特·麥克安利斯 (Colt McAnlis)
谷歌開發(fā)倡導(dǎo)者,專注于游戲開發(fā)、壓縮技術(shù)和性能提升。擔(dān)任南衛(wèi)理公會(huì)大學(xué)Guildhall學(xué)院的兼職教授,加州大學(xué)洛杉磯分校繼續(xù)教育學(xué)院講師,以及優(yōu)達(dá)學(xué)城(Udacity)的講師。
亞歷克斯·海奇 (Aleks Haecky)
谷歌開發(fā)倡導(dǎo)者、培訓(xùn)開發(fā)人員,從事性能提升、文檔編寫等幕后工作,在優(yōu)達(dá)學(xué)城、谷歌開發(fā)者頻道也從事一些幕后工作。
【譯者簡介】
王凌云
先后就讀于大連理工大學(xué)與北京師范大學(xué),現(xiàn)從事科技信息服務(wù)工作。閱讀興趣廣泛,對(duì)數(shù)學(xué)、計(jì)算機(jī)、歷史、文學(xué)等有濃厚的興趣。除本書外,另譯有《度量:一首獻(xiàn)給數(shù)學(xué)的情歌》《軟件開發(fā)本質(zhì)論》。
序 xiii
前言 xv
第 1章 并非無趣的一章 1
1.1 5類數(shù)據(jù)壓縮算法 1
1.2 惹人“憤怒”的克勞德 香農(nóng) 2
1.3 關(guān)于數(shù)據(jù)壓縮,你必須知道的 3
第 2章 不容錯(cuò)過的一章 9
2.1 理解二進(jìn)制 9
2.1.1 十進(jìn)制計(jì)數(shù)系統(tǒng) 9
2.1.2 二進(jìn)制計(jì)數(shù)系統(tǒng) 10
2.2 信息論 12
2.2.1 二分查找 14
2.2.2 熵:表示一個(gè)數(shù)所需要的最少二進(jìn)制位數(shù) 15
2.2.3 標(biāo)準(zhǔn)的數(shù)字長度 16
第3章 突破熵 17
3.1 理解熵 17
3.2 熵有什么用處呢 19
3.3 理解概率 19
3.4 突破熵 20
3.4.1 示例1:增量編碼 21
3.4.2 示例2:符號(hào)分組 22
3.4.3 示例3:排列 22
3.5 信息論與數(shù)據(jù)壓縮 26
第4章 VLC 29
4.1 摩爾斯碼 29
4.2 概率、熵與碼字長度 31
4.3 VLC 33
4.3.1 運(yùn)用VLC 34
4.3.2 創(chuàng)建VLC 37
4.3.3 幾個(gè)VLC示例 39
4.3.4 為數(shù)據(jù)集找到最適合的編碼方法 45
第5章 統(tǒng)計(jì)編碼 47
5.1 利用統(tǒng)計(jì)使數(shù)據(jù)壓縮接近熵 47
5.2 哈夫曼編碼 49
5.2.1 構(gòu)造哈夫曼樹 49
5.2.2 生成碼字 50
5.2.3 編碼和解碼 52
5.2.4 實(shí)際的實(shí)現(xiàn)方法 52
5.3 算術(shù)編碼 53
5.3.1 找出正確的數(shù) 54
5.3.2 編碼 55
5.3.3 選擇正確的輸出值 57
5.3.4 解碼 57
5.3.5 具體實(shí)現(xiàn) 62
5.4 ANS 62
5.4.1 通過轉(zhuǎn)換表來編碼和解碼 62
5.4.2 創(chuàng)建備查表 64
5.4.3 使用ANS壓縮數(shù)據(jù) 66
5.4.4 解碼示例 67
5.4.5 壓縮是從哪里來的 68
5.5 在實(shí)際壓縮中,選擇哪一種統(tǒng)計(jì)壓縮算法 69
第6章 自適應(yīng)統(tǒng)計(jì)編碼 71
6.1 位置對(duì)熵的重要性 71
6.2 自適應(yīng)VLC編碼 73
6.2.1 動(dòng)態(tài)創(chuàng)建VLC表 73
6.2.2 字面值 75
6.2.3 重置 78
6.2.4 知道何時(shí)重置 79
6.2.5 實(shí)際中的應(yīng)用 80
6.3 自適應(yīng)算術(shù)編碼 80
6.4 自適應(yīng)哈夫曼編碼 81
6.5 現(xiàn)代的選擇 81
第7 章 字典轉(zhuǎn)換 83
7.1 基本字典轉(zhuǎn)換 84
7.2 LZ算法 87
7.2.1 LZ算法的工作原理 88
7.2.2 編碼 92
7.2.3 解碼 93
7.2.4 壓縮LZ算法的輸出 94
7.2.5 LZ算法的變體 95
7.3 盡可能多地收集數(shù)據(jù) 96
第8章 上下文數(shù)據(jù)轉(zhuǎn)換 97
8.1 RLE 98
8.1.1 處理短行程問題 98
8.1.2 壓縮 99
8.2 增量編碼 101
8.2.1 XOR增量編碼 103
8.2.2 參照系增量編碼 104
8.2.3 修正的參照系增量編碼 105
8.2.4 壓縮增量編碼后的數(shù)據(jù) 107
8.2.5 那么它對(duì)文本有效嗎 107
8.3 MTF 107
8.3.1 消除搗亂符號(hào)的影響 109
8.3.2 壓縮MTF 109
8.4 BWT 110
8.4.1 順序很重要 111
8.4.2 BWT的工作原理 111
8.4.3 BWT的逆操作 112
8.4.4 具體的實(shí)現(xiàn) 114
8.4.5 壓縮BWT后的數(shù)據(jù) 115
第9 章 數(shù)據(jù)建!117
9.1 馬爾可夫鏈 118
9.1.1 馬爾可夫鏈與壓縮 121
9.1.2 實(shí)際的實(shí)現(xiàn) 125
9.2 部分匹配預(yù)測算法 126
9.2.1 單詞查找樹 127
9.2.2 字符的壓縮 128
9.2.3 選擇一個(gè)合理的N值 130
9.2.4 處理未知的符號(hào) 130
9.3 上下文混合算法 130
9.3.1 模型的類型 131
9.3.2 混合的類型 132
9.4 下一代技術(shù) 133
第 10章 換個(gè)話題 135
10.1 多媒體數(shù)據(jù)壓縮 135
10.2 通用壓縮 136
10.3 實(shí)踐中的數(shù)據(jù)壓縮 137
第 11章 評(píng)價(jià)數(shù)據(jù)壓縮 139
11.1 數(shù)據(jù)壓縮的使用場景 139
11.1.1 線下壓縮,客戶端解壓 139
11.1.2 客戶端壓縮,云端解壓 140
11.1.3 云端壓縮,客戶端解壓 140
11.1.4 客戶端壓縮,客戶端解壓 141
11.2 數(shù)據(jù)壓縮的需求 141
11.3 壓縮率 142
11.4 壓縮性能 142
11.5 解壓性能 143
11.6 解碼流的能力 143
11.7 比較壓縮算法 144
第 12章 壓縮圖像數(shù)據(jù) 147
12.1 理解圖像質(zhì)量與文件大小 147
12.1.1 是什么降低了圖像的質(zhì)量 149
12.1.2 度量圖像質(zhì)量 150
12.1.3 讓想法真正工作 152
12.2 圖像的尺寸很重要 152
12.3 選擇正確的圖像格式 153
12.3.1 PNG 154
12.3.2 JPG 154
12.3.3 GIF 155
12.3.4 WebP 156
12.3.5 現(xiàn)在,到了選擇的時(shí)刻 156
12.4 GPU 紋理格式 157
12.5 矢量格式 158
12.6 收獲的捷徑 160
第 13 章 序列化數(shù)據(jù) 161
13.1 了解常見的使用場景 162
13.1.1 服務(wù)器動(dòng)態(tài)生成的數(shù)據(jù) 162
13.1.2 服務(wù)器擁有的靜態(tài)數(shù)據(jù) 162
13.1.3 客戶端動(dòng)態(tài)生成的數(shù)據(jù) 162
13.1.4 客戶端擁有的靜態(tài)數(shù)據(jù) 162
13.2 序列化格式的問題 162
13.2.1 可讀文本 163
13.2.2 解碼時(shí)間長 164
13.3 更小的序列化數(shù)據(jù) 164
13.3.1 使用二進(jìn)制序列化格式 164
13.3.2 重構(gòu)列表以獲得更好的壓縮 165
13.3.3 組織數(shù)據(jù)以便高效獲取 166
13.3.4 將數(shù)據(jù)切分為適當(dāng)?shù)膲嚎s格式 168
第 14章 有損數(shù)據(jù)壓縮 171
第 15章 讓世界變得更小 173
15.1 數(shù)據(jù)壓縮與你 173
15.2 數(shù)據(jù)壓縮與盈利 173
15.2.1 用戶獲取與保持 173
15.2.2 運(yùn)行成本 174
15.2.3 提前規(guī)劃 175
15.3 讓用戶的生活更美好更便宜 175
15.4 對(duì)下一步技術(shù)的思考 175
15.4.1 未來的50億用戶 176
15.4.2 移動(dòng)網(wǎng)絡(luò) 176
15.5 開始行動(dòng) 176
數(shù)據(jù)壓縮術(shù)語表 179
關(guān)于作者 188
關(guān)于封面 188