数据压缩入门

0
(0)

数据压缩入门

作者:[美]柯尔特·麦克安利斯(ColtMcAnlis)[美]亚历克斯·海奇(Ale

出版社:人民邮电出版社

译者:王凌云

出版年:2020-3

页数:188

定价:69元

装帧:平装-胶订

丛书:图灵程序设计丛书

ISBN:9787115534170

内容简介
······

本书的主题是数据压缩,也就是用最紧凑的方式来表示数据。本书先讲解了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

"数据压缩入门"试读
······

我第一次编程时,连数据压缩是什么都不知道,更谈不上认识到它的重要性了。幸运的是,我的Apple II Plus计算机内存有0.000 048 GB(约48 KB),这在1979年算是很大的内存了,足够让我去探索编程和计算机图形学。我当时完全没有意识到程序和数据在后台是不断压缩和解压缩的,从而减小了它们在内存中的大小。说到这里,真要感谢Woz!
有了几年的编程经验后,我发现:
•数据压缩需..

  • 前言
  • 第1章 并非无趣的一章

评论 ······

写出了个人理想科普书的感觉? 没有严谨的分析和证明 废话数量尚可 但是很适合做个概览 对后续深入研究还是很有帮助的 有少量的programmer's perspective这是好的

这书还挺好的,而且不难读,前面讲了下压缩算法定义,然后讲原理(统计编码,识别上下文,识别单词)讲到 LZ77,然后再讲了下 delta / RLE 这些都怎么压缩的
后面还有些有损(压视频音频的)压缩,基本介绍了常用的一些格式和trick,但讲的不是很细了

通俗易懂,非常有趣!

可爱,但是浅,但是可爱

点击星号评分!

平均分 0 / 5. 投票数: 0

还没有投票!请为他投一票。

推荐阅读

评论 抢沙发

评论前必须登录!

 

登录

找回密码

注册