《老子到此一游系列》之 老子为什么是老子 ——综述视角解读压缩编码 第一章 轻松上手(转发)

《老子到此一游系列》之 老子为什么是老子 ——综述视角解读压缩编码 第一章 轻松上手(转发)

ELT.ZIP是谁?

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

成员:

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

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

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

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

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

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

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

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

入门指北

压缩编码概览:

压缩算法基础文献:

  • 《计算机基础系列之压缩算法》:
  • 《我从来不理解 “压缩算法”,直到有人这样向我解释它》
  • 《lzw压缩算法1【压缩篇】》:
  • 《lzw压缩算法2【压缩篇】》
  • 《【中英双字】JPEG算法原理 jpeg图片是如何压缩的?》:

参考文献

[1] Universal Lossless Data Compression Algorithms

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

[2]一种改进的 LZ77 无损数据压缩算法设计

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

[3] 无损数据压缩、算法比较和实现

https://kns.cnki.net/kcms/detail/detail.aspx?dbcode=CMFD&dbname=CMFD202101&filename=1020119610.nh&uniplatform=NZKPT&v=AYHUqrFSf5vzwjQ0OvGcQtr6edlzSPP0VWOuvMSWCecY2bK0v7OcHQXB_DTlr94T

[4] LZ77 Parsing, et c.

https://www.cs.helsinki.fi/u/puglisi/dct2017

有趣玩件

  • 《仅占用205k的15G好莱坞科幻大电影》:
    • https://wwa.lanzouv.com/iCDsQ00fnili
  • 《大名鼎鼎的压缩炸弹,完全解压后的大小为4.5P》
    • https://wwa.lanzouv.com/iCDsQ00fnili

第一章 轻松上手

1.1 《伟大的计算原理》

正式开始之初,我们便很轻易地从欧sir(编者注:欧建深,华为OpenHarmony开源与开发者运营总监)推荐的书目《 伟大的计算原理 》中获得了“ 文件压缩 ”的相关信息,通俗地阐述了各类不同压缩方法的简单实现原理,非常适合于作为对初学者的引入。

1.2 《数据压缩技术调查:从数据质量、编码方案、数据类型和应用的角度 》

《数据压缩技术调查:从数据质量、编码方案、数据类型和应用的角度 》(《 A Survey On Data Compression Techniques: From The Perspective Of Data Quality, Coding Schemes, Data Type And Applications 》)

从标题可知,这是一篇从数据质量、编码方案、数据类型和应用角度解读数据压缩技术的综述。

摘要部分是通常性的对文章发表背景及目的的叙述:“ 数字世界中数据的爆炸性增长导致了需要高效的技术来存储和传输数据。由于资源有限,数据压缩(DC)技术被提出,以最小化被存储或通信的数据的大小。由于DC概念能够有效利用可用存储区域和通信带宽,因此在几个方面发展了许多方法。为了分析DC技术及其应用程序是如何发展的,我们对许多现有的DC技术进行了详细的调查,以满足目前在数据质量、编码方案、数据类型和应用程序方面的要求。还进行了比较分析,以确定所审查的技术在其特征、基本概念、实验因素和局限性方面的贡献。最后,本文深入探讨各种开放问题和研究方向,探索未来发展的前景。”

从简单的一段摘要中,我们轻松获得了文章即将涵盖的技术领域,给读者提供了合适的技术背景铺垫,明确了定义:数据压缩技术是为了最小化数据大小来应对不断爆炸性增长的数据的存储传输。

接下来,是文章的目录结构:

目录是对一篇文章整体框架的梳理,便于读者掌握文章组织安排方式和迅速找到想发掘的点。

进入正文,首先,介绍部分不光是对开头摘要内容的拓展延伸,更多的是声明了后文中即将出现的专业概念词汇,强调基本的领域知识储备,避免读者在后续遇到困难。

由于入门指北已经奠定了一定基础,文字内容可以简单浏览了解;图表部分则具有很大价值,初学者很大程度上分辨不清各相关概念之间的区别与联系,而图表则提供了良好的解决方案,如:

图Fig 2. 就以文章标题所述的方式对不同压缩技术按照相应类别进行了分类,因此后文会以这样的编排方式进行解读:

  1. 从数据质量上大体分为无损压缩和有损压缩
  2. 从编码方案上可分为常用的哈夫曼编码、算数编码、字典编码(如LZ系列)、游程编码(RLE)等
  3. 按数据类型便是文本(LZMA)、图像(JPEG)、音频(MP3)、视频(H.264)
  4. 应用方向上又可分为无线传感网络、医学影像、其他等特殊应用

表Table 3. 从多方面比较了不同压缩技术的特点,详见其中。

纵览全文,通用衡量各压缩技术性能使用的主要是Compression Ratio(CR)、Peak Signal to Noise Ratio(PSNR)两项指标,即压缩比和峰值信噪比,这是一个重点。

压缩比好理解,就是数据压缩后的大小比上压缩前的大小,所以理论上压缩比越小,某种压缩算法一定程度上越占优势。那什么是峰值信噪比呢?这个概念从简单的字面意思上也能有个大致的感觉,我们不妨去搜索一下,在百度百科中得到了官方的定义:“ 峰值信噪比是一个表示信号最大可能功率和影响它的表示精度的破坏性噪声功率的比值的工程术语。由于许多信号都有非常宽的动态范围,峰值信噪比常用对数分贝单位来表示。” 什么意思呢?其实这里的“噪声”既非指日常生活中的“噪声”也非指物理学上的“噪声”,结合信息学或前文《 伟大的计算原理 》中的相关内容,我们得到以下理论:噪声是通信模型中的一个重要元素。任何在传输通道中改变信号,从而导致解码出错误消息的干扰都是噪声。如雾气和黑暗干扰了船只之间的信号通信;电报站之间过长的距离减弱了信号的强度;雷电干扰了调频广播的传输;DVD上的划痕会导致读取失败等,因此PSNR的值越高越好。

缩略语列表

缩写英文中文
ACAlternating Current交流
ASWDRAdaptively Scanned Wavelet Difference Reduction自适应扫描小波差约简
ATMAsynchronous Transfer Mode异步传输模式
CRCompression Ratio压缩比
CREWCompression with Reversible Embedded Wavelets可逆嵌入小波压缩
CSSCascading Style Sheets层叠样式表
DCData Compression数据压缩
DCTDiscrete Cosine Transform离散余弦变换
DWTDiscrete Wavelet Transform离散小波变换
EBCOTEmbedded Block Coding with Optimised Truncation优化截断的嵌入式块
ECEmbedded Coding嵌入式编码
EPWICEmbedded Predictive Wavelet Image Coder嵌入式预测小波图像
ETCEncryption Then Compression加密后压缩
EZWEmbedded Zerotree Wavelets嵌入式零树小波
GWGeometric Wavelet几何小波
HVSHuman Visual System人类视觉系统
JPEGJoint Photographic Experts Group联合图像专家组
LIPList of Insignificant Pixels不重要像素列表
LISList of Insignificant Sets不重要集合列表
LSPList of Significant Pixels重要像素列表
LZWLempel-Ziv-Welch蓝波-立夫-卫曲编码法
LZMALempel-Ziv-Markov chain-Algorithm
MSEMean Square Error均方误差
MPEGMotion Pictures Expert Group动态图像专家组
PSNRPeak SignaN-to-noise Ratio峰值信噪比
RLERun Length Encoding游程编码
ROIRegion Of Interest感兴趣区域
SBSub Bands子带
SFQSpace Frequency Quantization空频量化
SPECKSet Partitioned Embedded bloCK设置分区嵌入式块
SPIHTSetPartitioning in Hierarchical Trees多级树集合分裂
SRStack Run堆栈运行
SVDSingular Value Decomposition奇异值分解
VQVector Quantization向量量化
WDRWavelet Difference Reduction小波差约简
WMSNWireless Multimedia Sensor Network无线多媒体传感器网络
WSNWireless Sensor Networks无线传感器网络

后期预告

第二章:小波变换(Wavelet Transform)——流行的图像压缩算法

第三章:Brotli压缩算法——一种开源的压缩算法

第四章 LZ77 压缩算法——基于字典及滑动窗口的无损压缩技术

写在最后

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