數據壓縮入門

本書的主題是數據壓縮，也就是用*緊湊的方式來表示數據。
本書先講解了5類數據壓縮算法，即變長編碼、統計壓縮、字典編碼、
上下文模型和多上下文模型，然後介紹了香農的信息論，
以及怎樣通過各種方法來突破熵，如統計編碼、自適應統計編碼、
字典轉換、上下文數據轉換、數據建模等。
本書還討論了數據壓縮中的一些要點，如多媒體數據壓縮和通用壓縮，
並介紹了有損數據壓縮。
本書*後說明瞭數據壓縮與你、你的公司以及未來的技術是如何相互關聯的。  

Colt McAnlis

谷歌開發倡導者，專注於遊戲開發、壓縮技術和性能提升。
擔任南衛理公會大學Guildhall學院的兼職教授，
加州大學洛杉磯分校繼續教育學院講師，以及優達學城（Udacity）的講師。

Aleks Haecky

谷歌開發倡導者、培訓開發人員，從事性能提升、
文檔編寫等幕後工作，在優達學城、谷歌*發者頻道也從事一些幕後工作。

【譯者簡介】 

王凌雲

先後就讀於大連理工大學與北京師範大學，現從事科技信息服務工作。
閱讀興趣廣泛，對數學、計算機、歷史、文學等有濃厚的興趣。
除本書外，另譯有《度量：一首獻給數學的情歌》《軟件開發本質論》。

目錄：  
序xiii  
前言xv  
第1章並非無趣的一章1  
1.1 5類數據壓縮算法1  
1.2惹人“憤怒”的克勞德香農2  
1.3關於數據壓縮，你必須知道的3  

第2章不容錯過的一章9  
2.1理解二進制9  
2.1.1十進制計數係統9  
2.1.2二進制計數係統10  
2.2信息論12  
2.2.1二分查找14  
2.2.2熵：表示一個數所需要的*少二進制位數15  
2.2.3標準的數字長度16  

第3章突破熵17  
3.1理解熵17  
3.2熵有什麼用處呢19  
3.3理解概率19  
3.4突破熵20  
3.4.1示例1：增量編碼21  
3.4.2示例2：符號分組22  
3.4 .3示例3：排列22  
3.5信息論與數據壓縮26  

第4章VLC 29  
4.1摩爾斯碼29  
4.2概率、熵與碼字長度31  
4.3 VLC 33  
4.3.1運用VLC 34  
4.3.2創建VLC 37  
4.3.3幾個VLC示例39  
4.3.4為數據集找到*適合的編碼方法45  

第5章統計編碼47  
5.1利用統計使數據壓縮接近熵47  
5.2哈夫曼編碼49  
5.2. 1構造哈夫曼樹49  
5.2.2生成碼字50  
5.2.3編碼和解碼52  
5.2.4實際的實現方法52  
5.3算術編碼53  
5.3.1找出正確的數54  
5.3.2編碼55  
5.3.3選擇正確的輸出值57  
5.3.4解碼57  
5.3.5具體實現62  
5.4 ANS 62  
5.4.1通過轉換錶來編碼和解碼62  
5.4.2創建備查表64  
5.4.3使用ANS壓縮數據66  
5.4.4解碼示例67  
5.4.5壓縮是從哪裡來的68  
5.5在實際壓縮中，選擇哪一種統計壓縮算法69  

第6章自適應統計編碼71  
6.1位置對熵的重要性71  
6.2自適應VLC編碼73  
6.2. 1動態創建VLC表73  
6.2.2字面值75  
6.2.3重置78  
6.2.4知道何時重置79  
6.2.5實際中的應用80  
6.3自適應算術編碼80  
6.4自適應哈夫曼編碼81  
6.5現代的選擇81 
 
第7章字典轉換83  
7.1基本字典轉換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盡可能多地收集數據96 
 
第8章上下文數據轉換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壓縮增量編碼後的數據107  
8.2.5那麼它對文本有效嗎107  
8.3 MTF 107  
8.3.1消除搗亂符號的影響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具體的實現114  
8.4.5壓縮BWT後的數據115  

第9章數據建模117  
9.1馬爾可夫鏈118  
9.1.1馬爾可夫鏈與壓縮121  
9.1.2實際的實現125  
9.2部分匹配預測算法126  
9.2.1單詞查找樹127  
9.2.2字符的壓縮128  
9.2. 3選擇一個合理的N值130  
9.2.4處理未知的符號130  
9.3上下文混合算法130  
9.3.1模型的類型131  
9.3.2混合的類型132  
9.4下一代技術133  

第10章換個話題135  
10.1多媒體數據壓縮135  
10.2通用壓縮136  
10.3實踐中的數據壓縮137  

第11章評價數據壓縮139  
11.1數據壓縮的使用場景139  
11.1.1線下壓縮，客戶端解壓139  
11.1.2客戶端壓縮，雲端解壓140  
11.1.3雲端壓縮，客戶端解壓140  
11.1.4客戶端壓縮，客戶端解壓141  
11.2數據壓縮的需求141  
11.3壓縮率142  
11.4壓縮性能142  
11.5解壓性能143  
11.6解碼流的能力143  
11.7比較壓縮算法144 
 
第12章壓縮圖像數據147  
12.1理解圖像質量與文件大小147  
12.1.1是什麼降低了圖像的質量149  
12.1.2度量圖像質量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現在，到了選擇的時刻156  
12.4 GPU紋理格式157  
12.5矢量格式158  
12.6收穫的捷徑160 
 
第13章序列化數據161  
13.1了解常見的使用場景162  
13.1.1服務器動態生成的數據162  
13.1.2服務器擁有的靜態數據162  
13.1.3客戶端動態生成的數據162  
13.1.4客戶端擁有的靜態數據162  
13.2序列化格式的問題162  
13.2.1可讀文本163  
13.2.2解碼時間長164  
13.3更小的序列化數據164  
13.3.1使用二進制序列化格式164  
13.3.2重構列表以獲得更好的壓縮165  
13.3.3組織數據以便高效獲取166  
13.3. 4將數據切分為適當的壓縮格式168  

第14章有損數據壓縮171  

第15章讓世界變得更小173  
15.1數據壓縮與你173  
15.2數據壓縮與盈利173  
15.2.1用戶獲取與保持173  
15.2 .2運行成本174  
15.2.3提前規劃175  
15.3讓用戶的生活更美好更便宜175  
15.4對下一步技術的思考175  
15.4.1未來的50億用戶176  
15.4.2移動網絡176  
15.5開始行動176  
數據壓縮術語表179  
關於作者188  
關於封面188