无失真压缩算法的先行者:David Huffman 的故事

作者: 时间:2020-05-22G生活篇796人已围观

大家在压缩文件的时候有没有想过,为什幺文件经压缩后既减少了存储空间,又不会损害文件本身的内容?

在电脑资料处理中,霍夫曼编码(Huffman’s Encode)的利用,透过出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,使编码之后的字串的平均长度、期望值降低,从而达到无失真压缩资料的目的。

而提到这个霍夫曼编码,就不得不提它的发明者 — 大卫·霍夫曼(David Huffman)。

为了不用考试,他提出了霍夫曼编码

霍夫曼大生于美国俄亥俄州,在18岁的时候已经在俄亥俄州立大学取得电机工程学士。在服军役及修读硕士后,他进入了麻省理工学院攻读博士,主修电机工程。

在他攻读博士的期间,霍夫曼和修读资讯论课程的同学可以在完成学期报告还是期末考试中选择,而为了不去考试,他选择了完成学期报告。而当时学期报告的题目是:寻找最有效的二进制编码。

霍夫曼在多月的研究后仍然无法证明哪个已有编码是最有效的。正当他把他的笔记扔进垃圾桶时,他突然灵机一触,放弃对已有编码的研究,转向新的探索,最终发现了基于有序频率二元树编码的想法,亦即是后来被称为霍夫曼编码的方法,亦证明了这个方法是最有效的。

针对文字出现的频率进行编码 令编码最短化

霍夫曼编码的原理是用较少码来表示出现频率最高的字符,用较多的码表示出现频率低的字符,这便使编码之后的字串的平均长度降低,从而达到无失真压缩资料的目的。

霍夫曼编码的步骤如下:

1)按字符出现的概率按多少的顺序排队。

2)把两个最小的概率相加,并继续这一步骤,始终将较高的概率分支放在右边,直到最后变成概率1。

3)画出由概率1处到每个信源符号的路径,顺序记下沿路径的0和1,所得就是该符号的霍夫曼码字。

4)将每对组合的左边一个指定为0,右边一个指定为1(或相反)。

举例来说,以这句句子「this is an example of a huffman tree」,空格出现的频率最多,x出现的频率最少,所以空格的编码最短,x的编码最长,整句句子共需要135 bit。

无失真压缩算法的先行者:David Huffman 的故事 无失真压缩算法的先行者:David Huffman 的故事

为了纪念他的成就,人们把他在编码中用到的特殊二元树称之为霍夫曼树,将他的编码方法称为霍夫曼编码。

现时霍夫曼编码主要用于帮助压缩MP3音乐文件和JPEG图像,从而令文件的所需空间更少。

即使很多人使用霍夫曼代码用来压缩文件,但霍夫曼从未试图从他的作品中获得发明专利。相反,他把精力集中在教育上。用霍夫曼的话说,「我的产品就是我的学生。(My products are my students.)」

相关文章