[Python&DS]- Python实现Huffman

本文主要介绍Huffman编码、Huffman树、和如何借助Python实现Huffman编码树对文件进行压缩和解压缩。下文目录：

1. 什么是Huffman编码；
2. 如何通过Huffman树创建Huffman编码；
3. Python实现Huffman编码对文件进行压缩和解压缩

---

一、什么是Huffman编码

百科给的定义如下：

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）

如上，Huffman编码就是一种效率很高的编码方式，在理解Huffman编码之前，我们先来了解一下下面两种编码方式：
1.定长编码方式
例如ASCII码，8-bit定长编码，使用8位(一个字节)代表一个字符，比如tea就一定得需要 3x8 = 24位去表示该自字符串，一个含有n个字符的字符串就得需要 nx8 位去表示该字符串;
这样的编码没有考虑到一些字符出现的频率会高于一些其它的字符，比如在英文26个字母e的出现频率最高，而z出现的频率最低，此时我们使用较短位数的编码来表示e，代价是表示z字符可能需要稍长的编码，但是这并不妨碍我们达到压缩的效果：
例如: 使用7位的编码表示e，9位的编码表示z，其它字符的编码不变，由于e出现的频率比z的高，假设一篇文章当中e出现了10000次，而z出现的次数是10次，那么相比于定长编码，就节省了 10000 - 10 = 9990位的空间。(这个例子主要展示定长码的缺点，以及变长码可以给我们带来的好处)

2.变长编码方式
上面提到了，变长编码方式可以给我带来节省空间的好处，但是对于使用变长码编码的文件，如何去解析该文件得到原文件内容呢，又可能会出现什么问题呢？
举个例子：
使用 0 表示 e，1 表示 a，01表示t，那么 tea就被编码成0101，但是我们解析的时候，0101就可以解析成为 tt，eat，eaea,为了解决这个问题，科学家们又引入一个新的概念，那就是前缀码(Prefix codes 是属于变长编码范围的)

前缀码定义：任何一个字符的编码都不能是其它任何字符的编码的前缀

对于上面的例子，使用前缀码的意思就是 e 不能用0去表示，应为 0是 t对应的编码 01 的前缀，如果我们使用 001 去表示e，1 表示 a，01表示t，那么 tea就被编码成为 010011，并且在解析的时候，我们就只能解析成为 tea。

Huffman编码就是一种能够使用最短的位数来编码被编码文件的前缀码

如何构造这样的前缀码？

二、借助Huffman树创建Huffman编码

Huffman编码将给字母分配编码。每个字母的编码的长度取决于在被压缩文件中对应字母的出现频率，我们称之为权重(weight)。每个字母的Huffman编码是从称为Huffman编码树的满二叉树(所有节点要么有左右两个子孩子，要么就没有子孩子)中得到的。Huffman编码树的每一个叶节点对应于一个字母，叶节点的权重 （weight）就是它对应的字母出现的频率。使用权重的目的是建立的Huffman编码树有最小外部路径权重。
下图1将给大家解释一下什么是最小外部路径权重，并且Huffman编码的过程：

图1 外部路径权重解释

那么接下来，我们将解释图1 中的第一步构建Huffman编码树的过程：

1. 创建n个初始化的Huffman树，每个树只包含单一的叶节点，叶节点纪录对应的字母和该字母出现的频率(weight)；
2. 按照weight从小到大对其进行所有的Huffman树进行排序，取出其中weight最小的两棵树，构造一个新的Huffman树，新的Huffman树的weight等于两棵子树的weight之和，然后再加入到原来的Huffman树数组当中；
3. 反复上面的2中的操作，直到该数组当中只剩下一棵Huffman树，那么最后剩下来的那棵Huffman树就是我们构造好的Huffman编码树；

下面几个图将展示对应上图例子的一个构造Huffman编码树的过程，如图 2和图 3所示：

图 2 构造Huffman编码树的过程 1 图 3 构造Huffman编码树的过程 2

得到上面的Huffman编码树之后，就可以得到每个字符对应的编码了，方法就是：从根节点找到该叶节点，如果向左子树前进一步，那么code + = '0',如果向右子树前进了一步，那么code+= '1',等到达该叶节点，code对应的内容，就是该叶节点对应字符的编码

自此，你已经知道了如何使用Huffman编码树如何给字符分配编码，并且也知道了如何去构造这样的Huffman编码树，那么接下来就借助Python来实现它吧！

三、Python实现Huffman编码对文件进行压缩和解压缩

文件压缩的思路如图 4所示：

图 4 压缩文件的思想

文件解压缩的思路如图 5所示：

图 5 解压缩文件的思想.png

Python代码实现：
step1:实现Huffman编码树及其构造方法，代码如下：

#-*- coding:utf-8 -*-
#copyright@zhanggugu
import six
import sys

class HuffNode(object):
    """
    定义一个HuffNode虚类，里面包含两个虚方法：
    1. 获取节点的权重函数
    2. 获取此节点是否是叶节点的函数

    """
    def get_wieght(self):
        raise NotImplementedError(
            "The Abstract Node Class doesn't define 'get_wieght'")

    def isleaf(self):
        raise NotImplementedError(
            "The Abstract Node Class doesn't define 'isleaf'")


class LeafNode(HuffNode):
    """
    树叶节点类
    """
    def __init__(self, value=0, freq=0,):
        """
        初始化 树节点 需要初始化的对象参数有 ：value及其出现的频率freq
        """
        super(LeafNode, self).__init__()
        # 节点的值
        self.value = value
        self.wieght = freq

    
    def isleaf(self):
        """
        基类的方法，返回True，代表是叶节点
        """
        return True

    def get_wieght(self):
        """
        基类的方法，返回对象属性 weight，表示对象的权重
        """
        return self.wieght

    def get_value(self):
        """
        获取叶子节点的 字符 的值
        """
        return self.value


class IntlNode(HuffNode):
    """
    中间节点类
    """
    def __init__(self, left_child=None, right_child=None):
        """
        初始化 中间节点 需要初始化的对象参数有 ：left_child, right_chiled, weight
        """
        super(IntlNode, self).__init__()

        # 节点的值
        self.wieght = left_child.get_wieght() + right_child.get_wieght()
        # 节点的左右子节点
        self.left_child = left_child
        self.right_child = right_child


    def isleaf(self):
        """
        基类的方法，返回False，代表是中间节点
        """
        return False

    def get_wieght(self):
        """
        基类的方法，返回对象属性 weight，表示对象的权重
        """
        return self.wieght

    def get_left(self):
        """
        获取左孩子
        """
        return self.left_child

    def get_right(self):
        """
        获取右孩子
        """
        return self.right_child


class HuffTree(object):
    """
    huffTree
    """
    def __init__(self, flag, value =0, freq=0, left_tree=None, right_tree=None):

        super(HuffTree, self).__init__()

        if flag == 0:
            self.root = LeafNode(value, freq)
        else:
            self.root = IntlNode(left_tree.get_root(), right_tree.get_root())


    def get_root(self):
        """
        获取huffman tree 的根节点
        """
        return self.root

    def get_wieght(self):
        """
        获取这个huffman树的根节点的权重
        """
        return self.root.get_wieght()

    def traverse_huffman_tree(self, root, code, char_freq):
        """
        利用递归的方法遍历huffman_tree，并且以此方式得到每个 字符 对应的huffman编码
        保存在字典 char_freq中
        """
        if root.isleaf():
            char_freq[root.get_value()] = code
            print ("it = %c  and  freq = %d  code = %s")%(chr(root.get_value()),root.get_wieght(), code)
            return None
        else:
            self.traverse_huffman_tree(root.get_left(), code+'0', char_freq)
            self.traverse_huffman_tree(root.get_right(), code+'1', char_freq)



def buildHuffmanTree(list_hufftrees):
    """
    构造huffman树
    """
    while len(list_hufftrees) >1 :

        # 1. 按照weight 对huffman树进行从小到大的排序
        list_hufftrees.sort(key=lambda x: x.get_wieght()) 
               
        # 2. 跳出weight 最小的两个huffman编码树
        temp1 = list_hufftrees[0]
        temp2 = list_hufftrees[1]
        list_hufftrees = list_hufftrees[2:]

        # 3. 构造一个新的huffman树
        newed_hufftree = HuffTree(1, 0, 0, temp1, temp2)

        # 4. 放入到数组当中
        list_hufftrees.append(newed_hufftree)

    # last.  数组中最后剩下来的那棵树，就是构造的Huffman编码树
    return list_hufftrees[0]

上面代码详细展示了如何构造Huffman编码树，代码当中的注释已经足够详细，并且算法在第二部分已经进行了详细的讲解，在此就不赘述！

step2:压缩文件函数compress() 的实现，其主要思路就如图 4所示，其代码参考github 工程：

step3:解压缩文件函数decompress() 的实现，其主要思路就如图 5所示，其代码参考github 工程：

对代码中解压缩和压缩对齐处理方法说明：

图 6 解压缩和压缩过程中字节对齐处理方法


测试： 图 7 原文件大小 图 8 压缩之后的文件大小 图 9 解压缩文件之后的内容

原则上，该程序可以对任意格式的文件进行压缩，我自己也试过将xsl，word的文件进行压缩，大概可以得到30%左右的空间节省

四、总结

看完本文，希望你对Huffman编码方法能够有一个清晰的了解，并且知道如何使用Python实现Huffman编码树并且对文件进行解压缩。
完整源码请参考github工程

参考资料：

[1] - Data Structures and Algorithm Analysis in C++ Third Edition by Clifford A. Shaffer （<<数据结构与算法分析 C++版第三版>> 作者Clifford A. Shaffer ， 电子工业出版社 ）

声明：

1. 联系作者，新浪微博私信 @谷谷_z
2. 如果在文章当中发现有描述错误的地方，还请您不吝指出，万分感谢！
3. 此文章系本人原创作品，转发请注明出处！