Question

哈夫曼编码（理论）

Answer 1

哈夫曼编码是一种无损压缩文件一种方法，他的思路很简单，却又十分经典，他利用的是无重复前缀这种思想，就是每个字符的前缀是唯一的，若a的编码是001，那么就不会存在另一个以001开头的编码了，因为，哈夫曼编码是以二叉树为基础实现的，而二叉树到每一个叶子节点的路径是唯一的，那么也就是说每一个字符的编码也是唯一的。

哈夫曼编码是一种变长编码，比起定长编码的ascii码来说，哈夫曼编码能节省很多的空间，因为每一个字符出现的频率不是一致的，例如在英语中，‘e’出现的次数是最高的，那么如果我把‘e’的编码定义的短一点，那么是不是比起定长编码来说，空间就减少了？

基于这种思路，哈夫曼编码的具体实现过程如下：
（1）首先统计文本中各字符出现的频率（权重）。
（2）使用这些频率（权重），构建出哈夫曼树。
（3）规定从根节点开始，向叶子节点行走，经过左子树，编码为0，右子树，编码为1，这样就能得到每一个叶子节点字符的编码值了。