《老子到此一游系列》之 老子带你看懂这些风景—— 多维探秘通用无损压缩 第五章 双标准数据压缩（转发）

ELT.ZIP是谁？

ELT<=>Elite(精英)，.ZIP为压缩格式，ELT.ZIP即压缩精英。

成员：

上海工程技术大学大二在校生 闫旭

合肥师范学院大二在校生 楚一凡

清华大学大二在校生 赵宏博

成都信息工程大学大一在校生 高云帆

黑龙江大学大一在校生 高鸿萱

山东大学大三在校生 张智腾

ELT.ZIP是来自6个地方的同学，在OpenHarmony成长计划啃论文俱乐部里，与来自华为、软通动力、润和软件、拓维信息、深开鸿等公司的高手一起，学习、研究、切磋操作系统技术…

本文的梳理来自其中的四名同学：闫旭、楚一凡、赵宏博和高云帆。

前期回顾

第一章 熵编码器/第二章 BWT算法

第三章 基于BWT的改进算法

第四章 Lempel-Ziv Parsing

第五章  双标准数据压缩

5.1 概述

问题：

解决 LZ77解析的压缩空间大小和解压缩时间的问题。

目标：

• 确定一个 LZ77 解析，在给定的时间T最小化压缩文件的空间占</u>
• 相应的，交换时间与空间两种角色，在预先给定压缩空间中最小化压缩时间

如何实现目标：

• 引入新的 Bicriteria LZ77-Parsing 问题，它以一种原则性的方式形式化了数据压缩器传统上通过启发式方法处理问题
• 通过证明和部署加权图的一些特定结构属性，在 O(n log n²) 时间和 O(n) 空间字中有效地解决了这个问题，直到可以忽略的附加常数输入文件的 LZ77 解析
• 进行初步实验，表明所制作的新型压缩器对市面上高度工程化的竞争对手 （如 Snappy，LZMA，Bzip2）都具有很强的竞争力。

5.2 介绍

压缩思想：

随着海量数据集的出现以及随之而来的高性能分布式存储系统的设计，不少大厂纷纷行动，企图制作出一款可以实现有效压缩比和非常高效的解压缩速度的压缩器。例如 Google的BigTable，Facebook的Cassandra，Apache的Hadoop等等，这些无不都重新点燃了科学界对更优秀的无损压缩器的设计的激情。

解决无损压缩器的有效压缩比与实现非常高效的解压缩速度之间的问题，打破性能瓶颈的方法有很多种。但从很多无损压缩器相关的论文中，都有一种思想：“Compress once，Decompress many times”。（翻译为：一次压缩，多次解压缩）。

这种思想又可以被分为两大家族：

1. 基于 Burrows-Wheeler 变换的压缩器。
2. 基于 Lempel-Ziv 解析方案的压缩器。

这两大家族的压缩器在压缩和解压数据时需要的时间都是线性的，并且需要的压缩空间可以用输入的K阶经验熵来约束。

对两个问题的思考

一直以来，时间和空间似乎一直是算法中相互对立，但又相互依存的两个因素，经常刷 leetcode 的人一定对此深有感触，当我们解开一道算法题，很多人又会精进自己的算法，试图用“空间换时间”，“时间换空间”，以及尝试平衡两者来降低自己的执行用时和内存消耗，来获得更多的效益。

压缩算法也是如此，要么牺牲有效压缩比，要么牺牲解压缩速度，或者尝试用强大的技巧来平衡两者，一直以来研究这个无损压缩器的人归根到底都是在研究这个问题。由于研究困难，于是引出了两个应用方面具有挑战性的问题：

• 分布式存储系统问题（时间是主要影响因素）：

分布式存储系统，将数据分散存储在多台独立的设备上，可以拓展存储空间，Google，阿里等互联网公司，管理超过千万亿字节级别的大数据，它们对性能的要求很高，需要更低的解压缩时间。于是Snappy，LZ4等压缩器出现，帮助解决分布式存储系统上对解压缩时间要求更低的情况。

• 空间是主要影响因素的问题：我们日常用的手机，手表，平板等等，这些设备对空间拓展比较难，需要尽可能在不改变其解压缩速度的情况下降低其压缩比，来让这些难以拓展内存的设备更好地利用内存。

Bicriteria Data Compression（双标准数据压缩），即解决这个问题：

简单描述，两个参数（输入文件S，限定时间T），解决一个目标（控制解压缩时间这个变量，尽可能的降低其压缩比），再反过来（控制其压缩比，尽可能地降低其解压缩时间）。

想要解决这个问题，我们就要解决两个因素：

① 将该双标准优化将在S的压缩版本中进行。解决这个因素，原文采取基于LZ77的压缩器类别，因为它们在理论上和实践中占主导地位。使用主流压缩器，可以借鉴前人经验，帮助我们解决更多问题。

② 衡量待优化资源的计算模型对于这个因素，可以从几个常用计算模型中得到启发，这些模型对多级内存层次和连续内存字的获取进行了抽象。

三大贡献：

1. 提出新的图模型

在《On the bit-complexity of Lempel-Ziv compression》中，提出了一个特殊的加权DAG，这个DAG由①n=|S| 个 节点(nodes)，每个节点代表 S 的一个字符和②m=O(n²) 条边(edges)，每条边代表 LZ77 解析 S后可能出现的短语组成。具有两个权重（时间权重，空间成本）的新的图模型，时间权重即解压缩短语的时间（根据上面提到的分层记忆模型派生），空间成本即用于计算存储与该边关联的 LZ77 短语所需的位数（根据压缩机中采用的整数 编码器导出）。

2. 证明并使用加权DAG的一些结构特性

之后证明了上述的加权DAG的一些结构特性，使得我们能够设计一种算法，在 O(n log² n ) 时间和 O(n) 的工作空间内近似地解决我们版本的 WCSPP。

3. 将新的压缩器与其它压缩器对比

最后提出了一组初步的实验结果，将我们的压缩器的实现与最先进的基于LZ77 的算法（Snappy、LZMA、LZ4、gzip）和基于BWT的算法（具有有界和无界 的内存占用）进行比较。首先，它们为本文开始时 提出的两个相关问题提供了实际依据，并为文中新颖的双标准数据压缩问题引入的理论分析。实验结果表现出文中解析策略通过表现出接近Snappy和LZ4（即已知 最快的）的解压速度，以及接近基于BWT和LZMA的压缩器（即更简洁的）的压缩率， 在所有高度工程化的竞争对手中占了优势。

下期预告

第六章：连续小波变换
第七章：OpenHarmony内核子系统之文件系统和压缩器

参考文献

[1] Deorowicz S . Universal Lossless Data Compression Algorithms[J]. Philosophy Dissertation Thesis, 2003.

https://www.researchgate.net/publication/2910531_Universal_Lossless_Data_Compression_Algorithms

[2] Burrows M , Wheeler D J . A Block-Sorting Lossless Data Compression Algorithm[J]. technical report digital src research report, 1995.

https://www.researchgate.net/publication/2702058_A_Block-Sorting_Lossless_Data_Compression_Algorithm

[3] Gao X , Dong M , Miao X , et al. EROFS: a compression-friendly readonly file system for resource-scarce devices. 2019.

https://dl.acm.org/doi/abs/10.5555/3358807.3358821

[4] Ni G . Research on BWT and Classical Compression Algorithms[J]. Computer & Digital Engineering, 2010.

http://en.cnki.com.cn/Article_en/CJFDTOTAL-JSSG201011009.htm

[5] Farruggia A , Ferragina P , Frangioni A , et al. Bicriteria data compression[J]. Society for Industrial and Applied Mathematics, 2013.

https://xueshu.baidu.com/usercenter/paper/show?paperid=27a6024fe31d2cda63a5e79b34be6cfd

[6] Alakuijala J , Farruggia A , Ferragina P , et al. Brotli: A General-Purpose Data Compressor[J]. ACM Transactions on Information Systems, 2018, 37(1):1-30.

https://xueshu.baidu.com/usercenter/paper/show?paperid=1w6v0jh0qj360210sn0p08f0br369452&site=xueshu_se&hitarticle=1

[7] Overview – The Hitchhiker’s Guide to Compression (go-compression.github.io)

https://go-compression.github.io/

[8] Wavelet Tutorial – Part 1

https://users.rowan.edu/~polikar/WTpart1.html

[9] Wavlet Tutorial – Part 2

https://users.rowan.edu/~polikar/WTpart2.html

[10] Wavelet Tutorial – Part 3

https://users.rowan.edu/~polikar/WTpart3.html

缩略语列表

写在最后：

OpenHarmony 成长计划—“啃论文俱乐部”（以下简称“啃论文俱乐部”）是在 2022年 1 月 11 日的一次日常活动中诞生的。截至 3 月 31 日，啃论文俱乐部已有 87 名师生和企业导师参与，目前共有十二个技术方向并行探索，每个方向都有专业的技术老师带领同学们通过啃综述论文制定技术地图，按“降龙十八掌”的学习方法编排技术开发内容，并通过专业推广培养高校开发者成为软件技术学术级人才。

啃论文俱乐部的宗旨是希望同学们在开源活动中得到软件技术能力提升、得到技术写作能力提升、得到讲解技术能力提升。大学一年级新生〇门槛参与，已有俱乐部来自多所高校的大一同学写出高居榜首的技术文章。

如今，搜索“啃论文”，人们不禁想到、而且看到的都是我们——OpenHarmony 成长计划—“啃论文俱乐部”的产出。

OpenHarmony开源与开发者成长计划—“啃论文俱乐部”学习资料合集

1）入门资料：啃论文可以有怎样的体验  

https://docs.qq.com/slide/DY0RXWElBTVlHaXhi?u=4e311e072cbf4f93968e09c44294987d

2）操作办法：怎么从啃论文到开源提交以及深度技术文章输出https://docs.qq.com/slide/DY05kbGtsYVFmcUhU  

3）企业/学校/老师/学生为什么要参与 & 啃论文俱乐部的运营办法https://docs.qq.com/slide/DY2JkS2ZEb2FWckhq

 4）往期啃论文俱乐部同学分享会精彩回顾： 

同学分享会No1.成长计划啃论文分享会纪要（2022/02/18）  https://docs.qq.com/doc/DY2RZZmVNU2hTQlFY  

同学分享会No.2 成长计划啃论文分享会纪要（2022/03/11）  https://docs.qq.com/doc/DUkJ5c2NRd2FRZkhF  

同学们分享会No.3 成长计划啃论文分享会纪要（2022/03/25） 

https://docs.qq.com/doc/DUm5pUEF3ck1VcG92?u=4e311e072cbf4f93968e09c44294987d

现在，你是不是也热血沸腾，摩拳擦掌地准备加入这个俱乐部呢？当然欢迎啦！啃论文俱乐部向任何对开源技术感兴趣的大学生开发者敞开大门。

后续，我们会在服务中心公众号陆续分享一些 OpenHarmony 开源与开发者成长计划—“啃论文俱乐部”学习心得体会和总结资料。记得呼朋引伴来看哦。

扫码添加 OpenHarmony 高校小助手，加入“啃论文俱乐部”微信群