Superpack：突破 Facebook 移动应用程序的压缩极限作者|SapanBhatia译者|张健欣策划

作者|SapanBhatia
译者|张健欣
策划|褚杏娟
在Facebook上管理应用程序的大小是一个独特的挑战：开发者每天都要检查大量的代码，每行代码最终都会转化为人们下载到手机上的应用程序中的附加位。如果不加检查，这些添加的代码会使应用程序越来越大，直到下载应用程序所需的时间变得不可接受。
压缩是我们用来保持应用程序大小最小化的方法之一。这些压缩过的文件占用更少的空间，这意味着更小的应用程序下载地更快，全球数十亿用户使用更少的带宽。在移动宽带有限的地区，这样的节省尤其重要，因为有限的带宽会使下载大型应用程序的花费很高。但单靠压缩还不足以跟上我们所做的所有更新和添加到应用程序中各种功能的步伐。因此，我们开发了一种称为“Superpack”的技术，它将编译器分析和数据压缩相结合，开拓出超越传统压缩工具能力的优化。 Superpack突破了压缩极限，实现了比现有压缩工具更好的压缩率。
在过去两年中， Superpack已经能够控制开发人员导致的应用程序大小增长，并保持我们的Android应用程序小型化。 Superpack的压缩有助于减小我们的Android应用程序群的大小，这与常规AndroidAPK压缩相比要小得多，与Android的默认Zip压缩相比节省了20%以上空间。使用Superpack的应用程序包括Facebook、Instagram、WhatsApp和Messenger 。这些应用程序由于Superpack而减小的大小如下表所示。

文章图片

文章图片
Superpack：编译器+数据压缩
虽然现有的压缩算法，例如Zip的Deflat和Xz的LZMA ，能够很好地处理大型单体数据，但它们不足以抵消我们在应用程序中看到的增长速度，因此我们开始开发自己的解决方案。压缩是一个成熟的领域，我们开发的技术跨越了整个压缩领域，从数据压缩和Lempel-Ziv（LZ）解析到统计编码。
Superpack的优势在于压缩编码，如机器码和字节码，以及其它类型的结构化数据。 Superpack的底层方法是基于Kolmogorov的算法复杂性度量的想法，将一段数据的信息内容定义为生成该数据的最短程序的长度。换句话说，可以通过将数据表示成能够生成这段数据的程序来压缩数据。当数据是代码时，可以将其转换成更小的压缩后的表示。生成斐波那契数列及其索引列表的程序，是包含这些数列的文件的高度压缩表示。降低Kolmogorov复杂性本身的想法对于压缩领域并不新鲜。 Superpack的新方法涉及将编译器方法与现代压缩技术相结合来实现这一目标。
将生成小型程序的生成过程作为压缩的形式有很大的好处。这为数据压缩工程师提供了一系列成熟的编译工具和技术，这些工具和技术可以更改用途进行压缩。 Superpack压缩利用常见的编译器技术，例如解析和代码生成，以及最近的创新，例如Satisfiabilitymodulotheories(SMT)求解器，来找到最小的程序。
能够将这些编译器技术与主流数据压缩中使用的技术结合起来，这是Superpack有效性的一个重要组成部分。来自编译器的语义知识占了Superpack的一半，造就增强的LZ解析（消除冗余的压缩步骤），以及改进的熵编码（为频繁的信息片段生成短编码的步骤）。
改进的LZ解析
压缩器通常使用从LZ家族中选择的算法来识别重复的字节序列。大体上，每一个这样的算法都试图用指向以前出现的数据的指针来替换重复出现的数据序列。这个指针由上一次出现的距离（字节数）和序列长度组成。如果这个指针可以用比实际数据更少的位表示，则可以用之替换作为压缩大小。 Superpack通过发现更长重复序列，同时减少表示指针的位数，从而改进了LZ解析过程。