书名：数据压缩入门pdf/doc/txt格式电子书下载

推荐语：谷歌开发高手通俗讲解数据压缩算法，化繁为简，轻松做出正确的有关数据压缩的商业决策，高效传输和存储海量数据，打造流畅的用户体验

作者：（美）柯尔特·麦克安利斯,（美）亚历克斯·海奇,王凌云译

出版社：人民邮电出版社

出版时间：2020-04-01

书籍编号：30618076

ISBN：9787115534170

正文语种：中文

字数：136459

版次：1

所属分类：计算机-程序设计

版权信息

书名：数据压缩入门

作者：[美] 柯尔特 • 麦克安利斯 亚历克斯 • 海奇

译者：王凌云

ISBN：978-7-115-53417-0

版权声明

© 2016 by O\'Reilly Media, Inc.

Simplified Chinese Edition, jointly published by O\'Reilly Media, Inc. and Posts & Telecom Press, 2020. Authorized translation of the English edition, 2020 O\'Reilly Media, Inc., the owner of all rights to publish and sell the same.

All rights reserved including the rights of reproduction in whole or in part in any form.

英文原版由 O\'Reilly Media, Inc. 出版，2016。

简体中文版由人民邮电出版社出版，2020。英文原版的翻译得到 O\'Reilly Media, Inc. 的授权。此简体中文版的出版和销售得到出版权和销售权的所有者——O\'Reilly Media, Inc. 的许可。

版权所有，未得书面许可，本书的任何部分和全部不得以任何形式重制。

O\'Reilly Media, Inc.介绍

O\'Reilly 以“分享创新知识、改变世界”为己任。40 多年来我们一直向企业、个人提供成功所必需之技能及思想，激励他们创新并做得更好。

O\'Reilly 业务的核心是独特的专家及创新者网络，众多专家及创新者通过我们分享知识。我们的在线学习（Online Learning）平台提供独家的直播培训、图书及视频，使客户更容易获取业务成功所需的专业知识。几十年来 O\'Reilly 图书一直被视为学习开创未来之技术的权威资料。我们每年举办的诸多会议是活跃的技术聚会场所，来自各领域的专业人士在此建立联系，讨论最佳实践并发现可能影响技术行业未来的新趋势。

我们的客户渴望做出推动世界前进的创新之举，我们希望能助他们一臂之力。

业界评论

“O\'Reilly Radar 博客有口皆碑。”

——Wired

“O\'Reilly 凭借一系列非凡想法（真希望当初我也想到了）建立了数百万美元的业务。”

——Business 2.0

“O\'Reilly Conference 是聚集关键思想领袖的绝对典范。”

——CRN

“一本 O\'Reilly 的书就代表一个有用、有前途、需要学习的主题。”

——Irish Times

“Tim 是位特立独行的商人，他不光放眼于最长远、最广阔的领域，并且切实地按照 Yogi Berra 的建议去做了：‘如果你在路上遇到岔路口，那就走小路。’回顾过去，Tim 似乎每一次都选择了小路，而且有几次都是一闪即逝的机会，尽管大路也不错。”

——Linux Journal

致 JAM 与 MLM：

我曾向祖鲁族（Zuul）发誓，如果你们不立刻把西兰花吃了，那么我就会写一本书，并且在献词中这样写道：你们连一种人类已经吃了几千年的菜叶子都害怕。等 20 年后你们也为人父母时，我再将这本书拿出来，让你们看我写下的话，并当面嘲笑你们。只有这样，你们才知道现在你们把我弄得多么抓狂。

致 KMKM：

让我们再试十年，怎么样？

柯尔特 • 麦克安利斯

致 AHS 与 GHS：

我希望你们能学会做饭。然而，你们证明了人类是可以靠吃新鲜的苹果和超市里卖的不新鲜的寿司存活的。

亚历克斯 • 海奇

序

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

有了几年的编程经验后，我发现：

• 数据压缩需要花费时间并可能会导致软件变慢；
  
• 改变数据的组织结构可以让数据压缩得更小；
  
• 复杂的数据压缩算法各式各样。

这使我意识到压缩不是一个刚性的黑盒，相反，它是一个灵活的工具，可以极大地影响软件的质量。我们可以通过以下几种方式运用压缩：

• 改变压缩算法有可能让软件运行得更快；
  
• 针对数据的组织结构选择正确的压缩算法，可以使数据变得更小；
  
• 选择不匹配的数据组织结构或压缩算法，可能会导致数据变大或运行变慢。

如今我明白数据压缩为什么重要了。如果数据太大、内存不够，或者解压缩太慢，可以稍微改变一下数据的组织结构，以使它更好地适应压缩算法。比如，我会将数单独放在一组，字符串放在另一组，为重复出现的数据类型建表，或者将分数截断为整数。如果能让数据与算法匹配，我就无须去做评估与采用新的压缩算法这样的苦差。

后来，我开始做专业的电子游戏，大部分游戏数据是由艺术家、设计师和音乐家这样的非技术人员生成的。结果表明，数学不是他们最喜欢讨论的话题，而且他们对改变游戏数据以便更好地利用我的单向压缩算法不太感兴趣。好吧，既然数据的组织结构无法改善，剩下能做的就是选择最合适的压缩算法来与这些“伟大的”艺术数据匹配了。

我调查了各种数据压缩算法，发现有两大类很适合电子游戏数据：

• 
  

  无损方法

  
  
  
  
  • 去掉重复数据（LZ 算法）
    
  • 熵压缩（哈夫曼编码、算术编码）
  
  
• 
  

  有损方法

  
  
  
  
  • 降低精度（截断或降采样）
    
  • 图像 / 视频压缩
    
  • 音频压缩

对文本字符串和二进制数据使用 LZ 算法，可以将完全重复的数据压缩掉。对像素数据使用有损的矢量量化（vector quantization，VQ）算法，可以将像素映射为调色板。对音频数据使用有损的降采样和线性预测编码（linear predictive coding，LPC）算法，可以减少每秒的二进制位数。如果 CPU 足够快，前述所有这些压缩算法的输出都可以再用无损的哈夫曼算法进行一次额外的统计熵压缩。

20 世纪八九十年代，我参与制作了大约 30 个游戏，其中大多数使用的是这些算法，外加简单的数据构造工具对数据的组织结构进行有限的优化。

但是到了 2000 年左右，情况变得复杂起来。数据生成工具与数据展示和分析工具之间展开了持续的竞争。其结果是软件性能、存储大小、网络拥塞，以及压缩算法与数据组织结构的有效配对。

这种数据洪流被更大的存储空间（蓝光光盘、TB 级的硬盘以及云存储）、更快的多核 CPU、新的无损压缩算法（如 BWT、ANS 和 PAQ），以及针对图像、视频、音频等数据的有损编解码器的巨大性能提升部分抵消了。然而，由于数据每年的增长速度太快，相比之下，网络带宽的增加、压缩算法的性能提升以及存储容量增长的速度就太慢了。

这些因素造成了我们的现状，这也是本书内容之所以重要的原因。

程序员怎么才能知道为数据选择哪种压缩算法，以及对数据做什么样的改变能使特定的算法表现得更好或更差呢？其实真正有帮助的是对主要的数据压缩算法进行介绍，指导开发人员从众多可用的算法中选择最合适的。大部分开发人员其实并不需要掌握实现这些算法所需要的所有理论和数学细节，他们只要知道这些算法的优缺点，以及在特定场景中怎样充分利用它们即可。

我很高兴在过去的 37 年里一直在实现和使用不同的数据压缩算法，并看到它们的发展变化。我希望这本书能揭开数据压缩的神秘面纱，为软件开发人员学习压缩算法提供一个起点，同时帮助他们开发出更好的软件。

John Brooks
Blue Shift 公司首席技术官

前言

数据压缩无处不在，对现代计算来说它仍然像以前一样必不可少。过去，1 GB 就已经很大了，数据以每秒几千字节的速度传输。从某种意义上来说，我们已经经历了一个完整的循环，从内存和带宽有限的古董计算机时代，来到了内存有限且数据套餐十分昂贵的移动设备时代。

幸运的是，有很多工具、API 以及程序包可以帮我们压缩数据。理解它们如何工作，有助于我们正确地选择压缩工具（或算法），而这又可以令用户更高兴，同时降低成本、增加收入。

数据压缩的基础是数学，让我们坦然面对它。对大多数人来说，数学很难，真的很难，而且对于程序员曾经是最高的一道门槛。想想数据压缩之父克劳德 • 香农（Claude Shannon），他的数学非常好，在黑板上随手一写就是一行行复杂的方程。

更疯狂的是，现代程序员不需要了解数学。现在，8 岁的孩子都能上网，甚至在没有上过代数课的情况下，就能通过自学教程发布自己的网页或应用程序。

我们相信，这就是过去 20 多年里数据压缩领域一直停滞不前的原因。虽然有 20 亿人在使用移动设备 1，并且他们经常遇到内存不足和网络连接不良等问题，但是数据压缩技术仍然处于半停滞状态。这是因为懂数学的程序员不多。

1这是 2015 年的数据，如果你是在未来某个时间点读到这本书的，数据肯定会不同。还有，很感谢你阅读这本书。

当然也因为数学比较难。

你可以看到，压缩不是真的与数据有关。数据压缩领域早期的创始人考虑的并不是数据，而是统计。他们寻找并发现了操纵数据集中符号的概率分布的不同方法，并利用这些方法来生成包含同样的信息但更小的数据集。

随着计算机技术越来越普遍、越来越去数学化，普通程序员需要知道的统计学知识和其他高等数学知识也越来越少。因此，尽管 21 世纪初出现了计算机史上最大规模的技术繁荣，整个数据压缩领域却只取得了两三项技术进展。

因为数据压缩很难。

因为它以数学为基础。

现在，我们从公平和实用的角度来看待这个问题。如今，大多数程序员和内容开发人员不需要懂得高等数学，也不需要理解压缩的工作原理，因为他们只需要获得一个像样的数据压缩库，再把数据扔给它，就可以到处使用压缩后的数据了。

然而，向前看，这还不够。根据预测，到 2025 年，将有 50 亿人使用计算机并通过互联网传输数据。想想那时，数据量会急剧增长，我们会有太多的数据，运营商的传输速度会不够快，数据仓库又太小而无法容纳这些数据。当然，一个解决方法就是使用尚未发明出来的创新算法，实现更快、更好的压缩。

这自然要用到数学。

而数学又很难。

另一个解决方法是教那些愿意学的人理解数据压缩的工作原理。因此，你不再是随便拿到某个压缩工具就去使用，而是可以选择最好的压缩工具，并将数据以最高效的方式提供给用户。

这就是本书的写作动机。我们试图将数据压缩这一学科中大量难以理解的内容简化为普通人都能理解的内容，并且让他们能将这些知识应用到日常的数据需求中。我们试着尽可能少用数学，尽量用图、表和数据流的形式来解释数据压缩的基本原理。与柯尔特在 YouTube 上的 Compressor Head 系列视频相似，我们希望能通过本书教给任何高中以上文化水平的读者一些数据压缩知识，即使你不是程序员也不要紧。

不过，我们要坦诚地告诉读者：如果你真想理解这些内容，就必须做一些思维训练。就像骑自行车一样，数据压缩还是比较难的，只有你真正领会了其中的要点，一切才变得有意义起来。但在这之前，你必须坚持下去，并通过例子加深自己的理解。

有一点需要明确，本书的目标不是让你成为压缩专家，因为那需要相当深厚的数学功底(这很难做到），而是让你理解压缩算法，这意味着我们有时会使用恰当的术语，有时则会使用虽然不太正确但更具描述性的术语。掌握这些术语也许还不足以让你与其他数据压缩专业人员在茶歇时随心交流。我们想为你提供足够多的信息，以确保你做出正确的有关数据压缩的商业决策。

最后，老实说，数据压缩真的很酷。当然，这是我们的想法，希望当你深入阅读本书后，也会这样认为。

在写这本书时，我们觉得很开心，也希望你能从数据压缩知识的学习中获得乐趣。

怎样阅读本书

与任何好故事一样，本书也回答了所有相关的疑问。什么是数据压缩？为什么需要了解数据压缩？数据压缩这一技术是什么时候发明的？有哪些人致力于减少更多的二进制位？我们需要在产品开发周期的哪个阶段关注数据的大小？还有最重要的，它是如何节省二进制位、金钱以及用户的数据流量的？

本书是按先后顺序编排内容的，因此我们建议你从前往后按章阅读。本书的每一章都以前一章为基础，这

....