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

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

本期看点

  • 用生活中的烹饪视角解析Huffman编码过程

第二章 Huffman码

2.1 引言

说到哈夫曼编码或是霍夫曼编码，热爱自然科学、关注计算机科学的朋友们，或许曾听过、研究过。若是第一次听闻，或许会有一种像听到相对论、量子力学等一般的紧张感。请不必担心，我们接下来以一种老少皆宜、通俗有趣的方式传播分享，通读一遍说不定也能收获满满。接下来让我们进入正题吧。

先来感性地认识一下霍夫曼编码，首先顾名思义，我们可以明确一个大前提，这是霍夫曼的作品，其次这是一种编码技术。技术是用来解决问题的，那霍夫曼编码是用来解决什么问题的呢？——信息压缩问题。

现在大家心中已经对霍夫曼编码建立起了一个最基本的概念，这是由霍夫曼创立的用于解决信息压缩问题的编码技术。但这个概念还是太笼统了，再详尽一些是什么样子的呢？（别紧张，接下来你不会看到满屏的数学公式）。

我们用烹饪来举个例子，大家或许做过，或者看别人做过饭，做饭首先就得明确目标，就是我要做什么菜；对于霍夫曼编码来说就是目标压缩文本是什么。然后你就得列个清单看看做这道菜需要哪些原材料，各种要多少；对于霍夫曼编码来说就是一个统计构成文本的元素的种类和出现频率的过程。料备齐了就要掌握如何搭配，以及掌握火候，这就是考验一个人的厨艺的时候了；对于霍夫曼编码来说就是建立一个高效的字典树的过程。这一套流程下来我们可以获得一个菜的菜谱，这就是一个成品菜的压缩成果；对于霍夫曼来说我们就获得了一个文本的字典树。

在浏览器中粘贴以下网址，在线体验霍夫曼编码生成过程（Online Huffman Tree Generator (with frequency!)）：

huffman.ooz.ie 

2.2 现代场景

2.2.1 汉字字形压缩

通俗些说就是把我们的中文文本进行识别和压缩，这与英文文本有什么不同呢？中华文化博大精深，不像英文文本只有26个字母和一些标点符号，汉字千变万化，无法通过传统的方式统计编码。但是万变不离其宗。我们从小写字就知道一点，我们的汉字是由笔划再按照一定笔顺写成的，那么这时笔划也就是我们前面所说的原材料模板：

而笔顺就是我们建立字典的依据。我们的汉字通过这样的处理就可以通过霍夫曼编码进行压缩编码了。

2.2.2 3D网格的编码压缩

说到3D网格大家脑海中最先会联想到的可能会是3D动画。没错，这一项技术广泛的应用于这一领域。下面一些图片可供直观感受：

那么如何让这些精美的3D作品高效的压缩存储呢？霍夫曼编码大显身手的时侯到了。下面介绍相关场景并补充一项3D网格几何压缩的强大算法：

【征服三角形】

对未征服也就是未编码之处围绕其边界插入三角形，进行拟合重构。

其中箭头和数字给出了三角形征服的顺序。三角形中填满了不同图案来代表不同的操作码，当它们被征服时就会生成这些操作码，再通过霍夫曼进行处理。

【kD-tree分解（强大的3D图像处理算法）】

该方案特别适用于地形模型和密集采样对象。

为便于理解，我们用2D来表述KD-tree的几何编码。

每次将一个单元格细分为两个小单元格，对顶点数量进行编码。这种细分被重复地应用，直到每个单元格足够小，可以只包含一个顶点，并能够足够精确地重建顶点位置。

2.3 动态Huffman码的设计

动态哈夫曼编码（Dynamic Huffman coding），又称适应性哈夫曼编码（Adaptive Huffman coding），是基于哈夫曼编码的自适应编码技术。它允许在符号正在传输时构建代码，允许一次编码并适应数据中变化的条件，即随着数据流的到达，动态地收集和更新符号的概率（频率）。一遍扫描的好处是使得源程序可以实时编码，但由于单个丢失会损坏整个代码，因此它对传输错误更加敏感。

2.3.1 摘要

《Design and analysis of dynamic Huffman codes》这篇文章介绍并分析了一种构造动态Huffman码的单遍算法，同时还分析了由 Faller、Gallager和Knuth 三位学者得到的单遍算法。在每个算法中，发送器和接收器都保持等效的动态变化 Huffman 树，并对其进行实时编码。他们证明了新算法编码包含 t 个字母的消息所占用的bit数小于t，远远优于传统的两遍 Huffman 方案，并且与字母表的大小没有关系。对于任何一种单遍 Huffman 算法来说，这是在最坏状态下能做到的最佳可能情况。实验表明，新算法生成的编码长度比其他单遍算法的短，除了长消息外，也比两遍算法的短。最后明确了该算法适用于数据网络的在线编/解码和文件压缩场景。

2.3.2 介绍

由于传统的静态 Huffman 算法存在一个缺点，即它需要对数据进行两次遍历：第一次是通过构造和传输 Huffman 树到接收器，来收集消息中字母出现的频率计数；然后第二次再基于第一次构造的静态树结构，来编码和传输消息本身。那么，这会导致在将其用于网络通信时产生延迟，或者在文件压缩应用程序中产生额外的磁盘访问从而减慢算法。所以，Faller 和 Gallager两人各提出了一种一次遍历方案，后来被 Knuth 大大改进，以构造动态 Huffman 编码。发送器用来编码消息中第 t + 1 个字母的二叉树(同时也是接收器用来重建第 t + 1 个字母的二叉树)是消息前 t 个字母的二叉树。这样的话，发送器和接收器就都会从相同的初始树开始，发送器永远不需要将树发送给接收器。很显然，这与两次遍历算法的情况不同。

随后，研究者设计并证明了一个所有单遍Huffman方案中，在最坏情况下表现仍然是最优的算法A，它可以用于网络通信的通用编码方案，也可以作为基于文字的压缩算法中的一种高效子例程。

2.3.3 实验结论

算法A的优点：

  • 对于编码效率差异相对较大的小消息，每个字母占用更少的位。
  • 在 t 小于10^4（编者注：10的4次方）时，相比所有两遍算法都表现得更好。
  • 能够对消息进行实时编码解码，每个字母使用不到一个额外的比特位对消息进行编码。
  • 在文件压缩、网络通信和硬件实现方面有很大的应用潜力。
  • 可用来增强其他压缩方案。

前期回顾

第一章：数据压缩理论缘起——摩斯密码开创编码领域先河，信息熵用数学语言阐明了概率与信息冗余度的关系

后期预告

第三章：小波系数图像压缩编码——小波系数的各类编码方案大比拼
第四章 第二代图片压缩技术——8大压缩算法的大比拼
第五章：计算机视觉中的女神 —— Lenna——带你走进女神
第六章：无线传感器网络数据压缩——实践是检验真理的唯一标准

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] Vitter, Scott J . Design and analysis of dynamic Huffman codes[J]. Journal of the Acm, 1987, 34(4):825-845.

https://dl.acm.org/doi/10.1145/31846.42227

[2] Peng J , Kim C S , Kuo C C J . Technologies for 3D mesh compression: A survey[J]. Journal of Visual Communication & Image Representation, 2005, 16(6):688-733.

http://mcl.usc.edu/wp-content/uploads/2014/01/200503-Technologies-for-3D-triangular-mesh-compression-a-survey.pdf

写在最后：

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