赫夫曼编码(huffman codes)是一种非常有用的数据压缩方法,通常能将数据压
缩20%~90%。从具体问题出发,假设我们有一包含10000个字符的文件,这些字
符仅由6个不同的字符组成,就设这6个字符分别为“abcdef”,下面的表给出了
这6个字符在整个文件中的占比,和两种不同的编码方式。

————–abcdef
Frequency (in thousands)4513121095
Fixed-length codeword000001010011100101
Variable-length codeword010110011111011100

上例中固定长度的编码方式最少需要三位。那么整个文件的长度大小为300,000
bits,而对于可变长度的编码方式其使用大小为:

(45 1 + 13 3 + 12 3 + 16 3 + 9 4 + 5 4) · 1,000 = 224,000
bits

使用第二种编码方式能比第一种方式节约大约25%的空间。上述变长编码的方式实
际上是一种名为前缀编码的编码方式。

前缀编码

如果某种编码方案中,没有一个编码会是其它编码的前缀,则称这种编码方案为
前缀编码。有一条已证明的结论,任何由字符编码技术所获得的最佳压缩数据,
也可以由前缀编码来获得。

前缀编码的编码很容易,只需将文件中的字符用对应的编码表示即可。解码也容
易完成,因为其性质,可以直接从头至尾按编码与字符的对应关系翻译即可。

在解码过程中,为了方便和提高效率,可以用一颗二叉树来提供帮助。在这棵二
叉树中,0表示往左走,1表示往右走。字符则被放置在树的叶子上。所以从根节
点到叶子的路径表示了该字符的编码。这样一颗树对于解码时很有帮助的。下图
是上面的例子中的两种编码对应的二叉树:

赫夫曼编码

赫夫曼编码是指赫夫曼提供的一种构建最优前缀编码的方法。其方法是总选取权
重最小的两个结点xy合并成一个结点z,并用z代替它们,再从中选出两
个权重最小的结点…如是反复。图解:

伪码:

1
2
3
4
5
6
7
8
9
10
HUFFMAN(C)
n = |C|
Q = C
for i = 1 to n - 1
allocate a new node z
z.left = x = EXTRACT-MIN(Q)
z.right = y = EXTRACT-MIN(Q)
z.freq = x.freq + y.freq
INSERT(Q, z)
return EXTRACT-MIN(Q) // retrun the root of the tree

赫夫曼编码的正确性

证明赫夫曼编码的正确性需证明贪心算法的两要素:

  • 具有最优子结构
  • 贪心选择性质

本来按照之前些笔记的思路该记下证明过程的。但今天就不写了,我免不了要吐槽
几句。一直以来,我是很不喜欢也很少做笔记的,我更愿意的方式是在书旁边的空
白处写点理解感想之类的,潦潦草草,信手涂鸦。大一大二的时候因为看技术方面
的书籍多是从图书馆借来。特别是《C++ primer》这本书,被我借了两年,期间续
借了又续借。刚开始看书的时候,是很期待从上面看到点什么前辈心得的,当然上
面除了很少处的一两段短线之外,并没有什么其它前辈手迹。我有这种心理,因此
遗憾之余也并没有介意在书上留下点东西。期间我涂涂画画写了不少东西,起初我
不以为意,但后来还了书后,这本书恰巧又被我的同学ZWL借去。我从他手中偶然看
到这本书,又随手翻了翻我以前写在其中的小记,个中有不少错误之处,有的是因
为笔误,有的是因为刚开始看时理解的浅薄,这令我无比汗颜。我于是想最好还是
不要在借来的书上乱写。到不是为了爱惜书籍,虽然,太多人很高尚的认为不要在
图书馆中借来的书上写画,但我仍固执的以为,书被翻烂了写烂了才最能体现它的
价值。我所顾忌的一是恐误了后来人,二是那些心得,虽然写了,却再难翻看了。

再到后来会偶尔用本子记下一点心得,但确实麻烦难了。因为我看书一直以来的习
惯决定了,那些个笔记心得难成体系,太随意了,太散了。如果不是附在原文旁边,
我自己翻看,也没觉得有多大用处。另外一点在于,我向来对于笔记本这些东西保
存不善,指不定哪天丢了,或撕了——我喜欢用质量差的作业本写字,那些漂亮的笔
记本反而让我写不习惯,因此我的笔记本和作业本还有草稿本完全是一路货色。

到看算法导论的时候,我开始萌生了要系统记一记笔记的想法。我原来写这个笔记的
初衷在于,一是要囊括要点,二是能写一些书本之外的理解,更重要的是我想这些笔
记能够简明易懂,使我以后不用频频翻看原书。不过发现自己的水平也就能勉强读懂
这本书,原来的目的自然只达到了十之一二。

这本书的笔记我还是会将它写完,但有些无谓的地方将不会多浪费笔墨。

每个人都有自己的做事原则,我的原则是做一件事,要有一个明确的理由,放弃一件
在做的事也要有一个明确的理由。