《老子到此一游系列》之 老子带你看懂这些风景—— 多维探秘通用无损压缩 第三章 基于BWT的改进算法（转发）

《老子到此一游系列》之 老子带你看懂这些风景—— 多维探秘通用无损压缩 第三章 基于BWT的改进算法（转发）

ELT.ZIP是谁？

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

成员：

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

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

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

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

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

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

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

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

前期回顾

《老子到此一游系列》之 老子带你看懂这些风景—— 多维探秘通用无损压缩 第一章 熵编码器/第二章 BWT算法

第三章  基于BWT的改进算法

3.1 基本原理

算法的第一阶段是Burrows-Wheeler变换。BWT输出序列在第二阶段经历一个加权频率计数变换，第三阶段是零运行长度编码，它减少了0次运行的长度。在最后阶段，序列

x(rle-0)由二进制算术编码器编码。算术编码是一种行之有效的熵编码方法，其中最重要的部分是概率估计方法。BWT只是对序列x的转换，并不起到压缩的作用，经过BWT算法编码后的序列还需要通过其他压缩算法才可以完成整个压缩任务：

图 3.1 基于BWT的改进算法

MTF（Move-To-Front）是一种数据编码方式，作为一个额外的步骤，用于提高数据压缩技术效果。MTF主要使用的是数据“空间局部性”，也就是最近出现过的字符很可能在接下来的文本附近再次出现。MTF的主要思想是：

  1. 首先维护一个序列字符集大小的栈表，其中每个不同的字符在其中占一个位置，位置从0开始编号
  2. 扫描需要重新编码的序列数据，对于每个扫描到的字符，使用该字符在栈表中的索引替换，并将该字符提到栈表的栈顶的位置(索引为0的位置)
  3. 重复上一步骤，直到序列扫描结束

以经过BWT算法得到的xbwt = drcraaaabba为例：

最终的得到的xmtf为34413000401。

相比于BWT算法，MTF算法的解码过程更为简单，其实就是上述过程的逆过程：

根据上表所示过程即可解码xmtf。

RLE-0(Zero run length encoding)叫做零游程编码，不同于一般的RLE算法，它只对序列中的0进行替换。在这里使用RLE-0处理序列是由于经过BWT和MTF两个过程，一般在序列中会存在大量的连续的零，因此用RLE-0对xmtf进行编码会起到一定的压缩效果。

RLE-0的原理是：

  1. 统计序列中由0组成的子序列含0的个数
  2. 用符号0a和0b表示数字m

第2步的具体做法是，先将(m+1)转换成二进制数，然后用0a代替0，0b代替1，最后舍弃最高位：

所以，xmtf = 34413000401 经过RLE-0算法得到的序列为x(rle-0)= 344130a0a40a1，由于这里的序列x过短，所以零游程编码的压缩效果并未很好的体现出来；RLE-0的解码过程就是根据个数和编码的对应关系将序列中的0~a~,0~b~替换成对应个数的0。

3.2 实际效率

为了比较压缩算法，需要选择一组文件作为测试数据。通常情况下，有两种选择测试文件的方式：

  1. 使用一个众所周知的数据集
  2. 为测试准备新的数据集

通常情况下，现实世界中有许多标准，我们不能优化所有的标准，所以不得不选择一种折衷方案。如果没有详细了解将压缩应用于的具体情况，我们就无法选择最佳的压缩方法。因此，这种情况下便需要讨论多标准优化（multi criteria optimisation）。


1896-1897年，Pareto首次对该领域进行了研究，讨论了满足许多排他性标准的问题。1906年，Pareto在他的著名著作《Manuale di economia politica, conuna introduzione alla scienca Sociale》中提出了非支配解决方案（non-dominated solutions）的概念。其在经济学术语中提出这样一种解决方案：作为一种解决方案，没有任何一个人可以更满意而别人一点不满意。目前，称此解决方案为Pareto最优解，即，不是非劣势解的解为劣势解。 

有一些标准Q1,Q2…,Qm取决于一些变量：
(1) Qi = Qi(q1,q2,…,qr), 当 i = 1, 2, … , m
一组变量：
(2) q = <q1,q2,…,qr>
被称为优化中的一个点。点q被称为Pareto-optimal，如果没有其他点p例如：
(3) ∀1≤i≤m Qi§ ≥ Qi(q)

多标准优化的目标是找到所有Pareto最优点的集合。Pareto最优集(方程3)的公式适用于所有标准Qi最大化的情况。一般情况下，所有或某些标准可以被最小化。

压缩质量至少有三个标准：压缩比、压缩速率、解压速率。通过每个输入字符(bpc)的平均输出位数度量压缩比，因此压缩比越小，效果越好。


3.3 算法比较

通过实验检验了如下算法：

  • A02 —— 基于BWT的算法，反演频率变换作为第二阶段，结果来自Arnavut的工作
  • acb —— Buyanovsky的关联编码器，压缩结果来自于acb 2.00c项目的实验
  • B97 —— Bunton提出的PPM算法的最佳版本
  • boa —— 由Sutton编写的boa 0.58b压缩程序，是PPM算法的实现
  • BS99 —— Balkenhol和Shtarkov提出的基于BWT的算法
  • BW94 —— 初始Burrows-Wheeler算法
  • Bzip —— Seward编写的bzip 0.21压缩程序，实现了与Fenwick方法的相同压缩比
  • CTW —— Willems等提出的上下文树加权方法
  • DM —— 基于BWT的改进算法，第二阶段是移动到前端的变换
  • DW —— 基于BWT的改进算法，第二阶段是加权频率计数变换
  • F96 —— Fenwick提出的基于BWT的算法，在Silesia corpus实验的bzip 0.21程序中取得了相同压缩比
  • gzip —— 标准gzip程序，是著名的LZ77算法的实现
  • LDMC —— 目前最好的动态Markov编码算法，最初由Cormack和Horspool 引入，是由Bunton改进的LazyDMC版本
  • lgha —— 速度优化的ha压缩程序，由Lyapko提供实现
  • LZMA —— Pavlov提出的Ziv-Lempel算法，结果来自7-zip程序的实验
  • LZW —— 标准UNIX压缩程序，是LZW算法的一个实现
  • MH —— Shkarin提出的cPPMII算法，结果来自PPMonstr var. H程序的实验
  • MI4 —— Shkarin的cPPMII算法，结果来自4阶PPMonstr var. I程序的实验
  • MI64 —— Shkarin的cPPMII算法，结果来自64阶PPMonstr var. I程序的实验
  • PPMdH —— Shkarin提出的PPMII算法，结果来自PPMd var. H程序的实验
  • PPMN —— Smirnov 的 PPMN 算法，结果来自*ppmnb1+*程序的实验
  • rar —— rar 2.90压缩程序
  • szip —— Schindler提出的基于BWT的算法，结果来自szip程序的实验
  • T98 —— Teahan提出的PPMD+算法，结果来自*ppmd+*程序的实验
  • ufa —— Pavlov提出的二进制PPM算法，结果来自* ufa 0.04 Beta 1*程序的实验
  • VW98 —— Volf和Willems提出的切换算法
  • WM01 —— 基于BWT的最佳算法，无第二阶段，结果来自Wirth和Moffat的工作
  • ybs —— 基于BWT的压缩程序，距离编码器变换作为第二阶段，是Yoockin的实现

3.4 实验结论

以上其中几幅表对解压速度和压缩比进行了比较。我们可以看到，PPM算法的解压速度几乎与其压缩速度相同；LZ算法解压比压缩快得多；基于BWT算法的解压与压缩速度之间有着明显的差异，但低于LZ算法；PPMdH算法仅支配了两种基于BWT的算法，但其平均解压缩速度的标准差远远高于这两种算法；DM算法是Pareto最优的，而其在基于BWT的算法中取得了最佳压缩比；测试中的LZMA算法实现了LZ系列中的最佳压缩比，但其压缩速度慢，比最慢的基于BWT的算法慢两倍以上，解压速度方面优于所有基于BWT的算法及LZW算法。

从多准则优化的角度对实验结果进行分析，可将这些方法粗略地分为三组：

  • 包括PPM、CTW、DMC算法，达到了最佳压缩比，但速度较慢
  • 包括LZ算法，速度较快，但压缩比较差
  • 包括基于BWT系列算法，比PPM运行速度快，比LZ有更好的压缩比
算法优点缺点
cPPMII压缩比显著优运行速度慢、内存消耗高
LZMA压缩比明显优、解压速度快压缩速度慢
PPM压缩比明显优压缩、解压速度慢
基于BWT系列大文件压缩速度较快小文件压缩比较差

在基于BWT系列中，最佳压缩比的是本文改进算法——DW，其运行速度与其他BWT系列算法相当。对不同大小文件的测试表明，DW的压缩与解压速度比其他基于BWT的大尺寸块算法相对更稳定。

下期预告

第四章：Lempel-Ziv Parsing

第五章：双标准数据压缩

第六章：连续小波变换

第七章：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

缩略语列表

缩写英文中文
ANSAsymmetric numeral systems非对称数字系统
BSLDCAThe Block Sorting Lossless Data Compression Algorithm块排序无损数据压缩算法
BTWBurrows–Wheeler  TransformBurrows–Wheeler转换
BWCABurrows-Wheeler Compression AlgorithmBurrows-Wheeler压缩算法
CTWContext Tree Weighting上下文树加权
CWTContinue Wavelet Transform连续小波变换
DMCDynamic Markov Coding动态马可夫压缩
DWTDiscrete Wavelet Transform离散小波变换
ECEntropy Coder熵编码器
MCOMulti-Criteria Optimisation多标准优化
MTFMove To Front Transform前移变换
PPMPrediction by Partial Matching通过部分匹配进行预测
RLE-0Zero Run Length Encoding零游程编码
STFTShort-time Fourier transform短时傅里叶变换

写在最后：

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 高校小助手，加入“啃论文俱乐部”微信群