看懂哈夫曼编码

计算机中对于数据是以二进制来保存和处理的，当我们读取一个文件，计算机得到的原始内容是一些二进制序列， 当需要对这些二进制序列进行显示时，计算机会依照对应的编码方式进行解码，而其中哈夫曼编码就是一种高效的编码方式。

在计算机学科中，编码方式有很多种，对于Java开发而言，其中ASCII码和RFC3986(URL中非ASCII字符的编码)应该是我们最熟悉的了， 在ASCII编码表中我们会发现每一种字符都可以表示成相应二进制(八位定长的编码方式)， 通过ASCII编码表，我们可以将对应编码转换成人们能直观理解的数据。

为了方便说明，我们通过Java解析一个文件来看，文件中只存储一个大写字母A，然后通过读取文件的流。

文件内容

A

Java代码:

public class Test{
    public void readFileByBytes(String fileName) throws FileNotFoundException {
        InputStream in = new FileInputStream(fileName);
        try {
            int tempbyte;
            while ((tempbyte = in.read()) != -1) {
                System.out.println("十进制:" + tempbyte);
                System.out.println("二进制:" + Integer.toBinaryString(tempbyte));
            }
            in.close();
        } catch (IOException e) {
            e.printStackTrace();
            return;
        }
    }
     public static void main(String[] args) throws FileNotFoundException {
        new Test().readFileByBytes("data.txt");
     }
}

运行结果:

十进制:65
二进制:1000001

我们可以发现，字符A在计算机中使用01000001来进行存储的，当需要展示的时候，通过ASCII编码表找到对应的字符A。那么ASCII码编码的优点是什么呢？首先由于ASCII码是八位定长的编码，所以很读写方便，如下: 0100000101000010 由于我们知道ASCII码是等长的八位编码，所以可以拆分为01000001 01000010，转为字符也就是A和B。

但是ASCII编码方式也存在缺点，那就是定长会造成一些空间浪费，在数据存储和传输时会浪费相应的资源(硬盘，带宽等)。举个例子，如果我们不依靠ASCII编码，将A使用0，B使用1，C使用10来进行编码，那么这种不定长的编码就会大大减少编码的长度，从而压缩空间。当我们对ABC 以这种不定长的编码方式编码，可以得到结果为 0110。这种方式 相对 0100000101000010 确实能减少编码长度，但是如何解码呢？因为不定长，那么00110可以拆为 0 ，1， 10 也可以拆为 0， 1， 1， 0 。这是两种不同的拆分对应不同含义，0 1 10代表ABC，0 1 1 0 代表ABBA。这种结果是因为 一个字符的编码是另一种字符的前缀，这就导致解码造成歧义。

今天讲的哈夫曼编码就是一种可以减少编码长度，又使得每一个字符的编码不会是另一种字符的前缀的编码方式。

谈到哈夫曼编码就不得不提及哈夫曼树，之前有关树的文章对于哈夫曼树有过描述和实现：

哈夫曼树

那么哈夫曼树跟哈夫曼编码有什么关系呢？

假设上面的文本文件中存储的字符为DCDDCBDACBCDDCDDD， 其中A出现一次，B两次，C五次，D九次，我们将其构建成如下的哈夫曼树(可以根据自己风格构建哈夫曼树)。

下面重点来了：

如果从根结点递归到每个叶子结点的过程中，向左递归记作1，向右递归记作0，然后把走过路径进行组合， 这样是不是就得到一组二进制数字(哈夫曼编码)，如下

那么文本存储如下时，:

DCDDCBDACBCDDCDDD

对应哈夫曼编码就为

0100010110011110110100010000

我们逐位读取，首先读取到字节是0，那么转为D(编码表中0就对应D)， 读取到1的时候，发现编码表中1不存在对应的字符，那么继续读取，此时10对应编码表的C，那么转为 C，然后继续读取.......。

这个过程我们发现不会存在字符的编码是另一种字符的前缀可能，而且也大大压缩 编码长度，如果按照ASCII码编码，那么结果如下(长度大大超过哈夫曼编码):

01000100
01000011
01000100
01000100
01000011
01000010
01000100
01000001
01000011
01000010
01000011
01000100
01000100
01000011
01000100
01000100
01000100

既然哈夫曼编码具有压缩编码长度效果，那么哈夫曼编码为什么没有广泛用在数据传输中呢？

这是因为其也存在一些缺点：

首先我们需要统计字符出现的频率，然后构建哈夫曼树，如果数据量过大，那么统计压缩过程可能很耗时(通常我们愿意使用空间换时间，而不是时间换空间)。

其次是统计的概率很不平均的时候，哈夫曼编码的效果才明显。

最后就是稳定性很差，在上面得到的哈夫曼编码中，如果一位丢失或者改动那么会导致数据全部乱掉，这在数据传输过程中 是很不安全的，而二进制编码方式因为汉名码等纠错方式，所以其稳定性比哈夫曼编码要好。