Yanyg - Software Engineer

Huffman编码

目录

WIKI:

霍夫曼编码(Huffman coding),又译哈夫曼编码,赫夫曼编码,是一种用于无损数据压缩的 熵编码(权编码)算法。美国计算机科学家David Albert Huffman在1952年发明。

相关论文:A method for the Construction of Minimum-Redundancy Codes.

1 原理

HuffmanCoding根据符号的频率决定编码。符号频率越高则符号编码越短,相反则符号越长。

考虑FORGET五个字母的编码,假定其出现频率如下:

Symbol F O R G E T
Frequency 2 3 4 4 5 7

按照如下方式迭代操作生成HuffmanCoding Tree:

  • 按照出现频率大小对符号排序;
  • 频率最小的两个字母相加形成一个新的节点(内部节点);
  • 用新的内部节点替换这两个相加的字母,继续比较频率;

最终生成如下图:

         25
      __/   \__
     /         \
    10          15
   /  \        /  \
  5    \      8    \
 / \    \    / \    \
2   3    5  4   4    7
F   O    E  R   G    T

FORGET的编码结果则是:

Symbol F O R G E T
Frequency 2 3 4 4 5 7
Code 000 001 100 101 01 11

2 实现

HuffmanCoding最主要的工作是实现一个HuffmanTree,HuffmanTree是一个二叉树,包含两种节点:

  • 叶子节点包括:Symbol、Frequency、指向父节点的链接;
  • 内部节点包括:左右子节点的链接、Frequencey(左右子节点Frequency之和)、指向 父节点的链接;

用0与1分别表示指向左子节点与右子节点,最后完成的树共有n个终端节点与n-1个非终端节点。