转发 | 《老子到此一游系列》之 老子见证的沧海桑田 —— 轻翻那些永垂不朽的诗篇(1/6)

ELT.ZIP是谁？

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

成员：

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

合肥师范学院大二在校生

清华大学大二在校生

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

黑龙江大学大一在校生

山东大学大三在校生

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

本期看点

• 塞缪尔·莫尔斯发明摩斯密码开创编码领域先河
• 香农提出信息熵，用数学语言阐明了概率与信息冗余度的关系

技术DNA

数据压缩的历史

图片来源：https://visual.ly/community/Infographics/computers/history-data-compression

ELT.ZIP（III部压缩算法）技术地图

智慧场景

第一章 数据压缩理论缘起

1.1 起源

数据压缩概念的演变源于摩尔斯电码，也即我们日常所说的摩斯密码（SOS就是其中一种）。它是一种时通时断的信号代码，通过不同的排列顺序来表达不同的英文字母、数字和标点符号，从而最小化消息的大小和传输时间。由电报之父塞缪尔·莫尔斯于1837年发明，1838年正式用于压缩电报中的信件。

1.2 发展

1986年Richard W. Hamming编写出版的《Coding and information theory》一书中提到：“编码和信息理论的概念起源久远，但在信息理论还未建立起一个坚实的基础之时，人们对其的许多基础性想法与理解其实都只停留在1948年之前。”

说到信息理论，不得不提到一个人 —— Claude E. Shannon(克劳德·艾尔伍德·香农)。香农是美国数学家，也是信息论的创始人，他提出了信息熵的概念，为信息论和数字通信的发展奠定了基础。从本质上讲，数据压缩的目的就是要消除信息中的冗余，而信息熵及相关的定理恰恰用数学手段精确地描述了信息冗余的程度。利用信息熵公式，人们可以计算出信息编码的极限，即在一定的概率模型下，无损压缩的编码长度不可能小于信息熵公式给出的结果。

于是后来，上述形势被1948年香农发表的两篇名为《通讯的数学原理》的文章所打破，它们在信息理论领域几乎迅速地传播并流行了起来。很快，另外一些信息理论的文章出现在了相关期刊上，许多大学的电气工程等相关部门也开始教授相关课程。

但由于信息理论在当时是一个新领域，人们对其能做的事情以及能应用的方向还没有一个确切的认识，渐渐地，人们对其的关注度愈发降低，相关课程的教授也随之减少。

1.3 转折

信息理论具有广泛适用于远离其原始灵感的情况的想法。好巧不巧的是，在信息理论被创立的左右之时，编码理论也诞生了。就编码理论而言，其数学背景在一开始远没有信息理论那么复杂，而且在很长一段时间里，它也没有得到理论界的重视。但是，随着时间的推移，各种数学工具如群论、有限域理论等慢慢被应用到编码理论中。现在，编码理论已成为数学研究中一个活跃的部分。

从逻辑上讲，编码理论引出了信息论，信息论提供了对信息进行适当编码所能做的操作的界限。因此，这两种理论是密切相关的。

1948 年，香农在提出信息熵理论的同时，也给出了一种简单的编码方法—— Shannon 编码，为压缩算法领域的发展奠定了专属基调。1952 年， R. M. Fano 又进一步提出了 Fano 编码。这些早期的编码方法揭示了变长编码的基本规律，也确实可以取得一定的压缩效果，但离真正实用的压缩算法还相去甚远。

第一个实用的编码方法是由 D. A. Huffman 在 1952 年的论文《最小冗余度代码的构造方法（ A Method for the Construction of Minimum Redundancy Codes ）》中提出的。直到今天，许多《数据结构》教材在讨论二叉树时仍要提及这种被后人称为 Huffman 编码的方法。Huffman 编码在计算机界是如此著名，以至于连编码的发明过程本身也成了人们津津乐道的话题。据说， 1952 年时，年轻的 Huffman 还是麻省理工学院的一名学生，他为了向老师证明自己可以不参加某门功课的期末考试，才设计了这个看似简单，但却影响深远的编码方法。

Huffman 编码效率高，运算速度快，实现方式灵活，从 20 世纪 60 年代至今，在数据压缩领域得到了广泛的应用。例如，早期 UNIX 系统上一个不太为现代人熟知的压缩程序 COMPACT 实际就是 Huffman 0 阶自适应编码的具体实现。20 世纪 80 年代初， Huffman 编码又出现在 CP/M （编者注：CP/M，是数字研究公司在1974年开发，为8位CPU的个人电脑所设计之操作系统。）和 DOS 系统中，其代表程序叫 SQ 。（编者注：SQ是由理查德·迪克·格林劳于1981年设计的计算机程序，在1980年代初期 DOS版 和 CP / M 计算机系统来压缩文件，以便它们使用较少的空间。）今天，在许多知名的压缩工具和压缩算法（如 WinRAR 、 gzip 和 JPEG ）里，都有 Huffman 编码的身影。不过， Huffman 编码所得的编码长度只是对信息熵计算结果的一种近似，还无法真正逼近信息熵的极限。正因为如此，现代压缩技术通常只将 Huffman 视作最终的编码手段，而非数据压缩算法的全部。

后期预告

第二章：Huffman码——用生活中的烹饪视角解析Huffman编码过程

第三章：小波系数图像压缩编码——小波系数的各类编码方案大比拼

第四章 第二代图片压缩技术——8大压缩算法的大比拼

第五章：计算机视觉中的女神 —— Lenna——带你走进女神

第六章：无线传感器网络数据压缩——实践是检验真理的唯一标准

写在最后：

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