哈希曼压缩算法

一、哈夫曼压缩算法的原理？

（1）哈夫曼压缩算法是一种无损数据压缩算法,它通过建立一种基于字符出现频率的二叉树来实现数据压缩。

它的原理很简单:就是根据字符出现的频率,给高频字符分配较短的编码,低频字符分配较长的编码。这样一来,整个文件的总编码长度就大大缩短了,从而达到压缩的目的。

众所周知，计算机存储数据时，实际上存储的是一堆0和1（二进制）。如果我们存储一段字符：ABRACADABRA! 那么计算机会把它们逐一翻译成二进制，如A：01000001；B: 01000010; !: 00001010.每个字符占8个bits, 这一整段字符则至少占12*8=96 bits。但如果我们用一些特殊的值来代表这些字符，如：

为了方便阅读，这个表格是可以写成一棵树的：

这棵树的节点左边是0，右边是1。任何含有字符的节点都没有非空子节点。（即上文提及的前缀问题。）这棵树是在压缩的过程中建成的，这个表格是在树形成后建成的。用这个表格，我们可以很简单地把一段字符变成压缩后的数据，如：原数据：ABRACADABRA!表格如上图。令压缩后的数据为S；第一个字符是A，根据表格，A：11，故S=11;第二个字符是B，根据表格，B：00，故S=1100;第三个字符是R，根据表格，R：011，故S=1100011;如此类推，读完所有字符为止。压缩搞定了，那解压呢？很简单，跟着这棵树读就行了

压缩后的数据S=11000111101011100110001111101记住，读到1时，往右走，读到0时，往左走。令解压后的字符串为D；从根节点出发，第一个数是1，往右走：

读到有字符的节点，返回此字符，加到字符串D里。D:ABR;返回根节点，继续读。如此类推，直到读完所有压缩后的数据S为止。压缩与解压都搞定了，现在看如何构建这个表格：我们需要先把原数据读一遍，并把每个字符出现的次数记录下来。如：ABRACADABRA!中，A出现了5次;B出现了2次;C出现了1次;D出现了1次;R出现了2次;!出现了1次。理论上，出现频率越高的字符，我们给它一个占用空间越小的值，这样，我们就可以有最佳的压缩率。我们把这些字符，按次数的多少排成递增的顺序：(括弧中的数字为出现次数)

然后，我们把最小的两个字符找出来，并新建一个节点作为它们的父节点（谁左谁右不重要，随意）：