赫夫曼树及其编码

赫夫曼树

在树这种数据结构中，从树中的一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上分支的数目叫做路径长度，从根结点到每个结点的路径长度之和叫做树的路径长度。如果一个结点带有权重，则路径长度和该结点权重的乘积叫做该结点的**带权路径长度(WPL)**，一棵树的带权路径长度为树中所有叶子结点的带权路径长度之和。

赫夫曼树（霍夫曼树），又称最优树或者最优二叉树。假设有n个权值{$w_1$, $w_2$,…,$w_n$}，通过这n个权值构造n个结点，每个结点的权值为$w_i$（1<=i<=n），然后以这n个结点为叶子结点构造一棵二叉树，在所有构成的二叉树中带权路径长度最小的二叉树被称作最优二叉树或者赫夫曼树。如下:

给定4个权重分别为7, 5, 2, 4的四个叶子结点a, b, c, d, 下图为用该4个结点构造的3棵二叉树:

上面图中三个二叉树的带权路径长度分别为:

(a) WPL = 72 + 52 + 22 + 42 = 36

(b) WPL = 73 + 53 + 21 + 42 = 46

(c) WPL = 71 + 52 + 23 + 43 = 35

其中(c)的带权路径最小，从图中可以看出：权值从高到低的节点对应路径长度依次递增，可以得出该树的带权路径为最小，该树即为赫夫曼树。

赫夫曼树的构造

构造赫夫曼树的步骤如下:

1. 根据给定的n个权值{$w_1$, $w_2$,…,$w_n$}构成n棵二叉树集合F={$T_1$,$T_2$,…,$T_n$}，其中每棵二叉树$T_i$中只有一个带权为$w_i$的根结点，其左右子树均为空（即初始集合中每棵树只有一个根结点）。

2. 在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，并且新二叉树根结点的权值为两棵子树根结点的权值之和。

3. 在F中删除步骤2中选中的两棵树，同时步骤2新构造出的二叉树加入到F中。

4. 重复步骤2和3，直到F中只剩下一棵树为止，此时剩下的这棵树便是赫夫曼树。

具体过程如下图所示，为前面给定的4个结点构造赫夫曼树的过程(注意：图中的结点按照权值大小已经排好序，在实际代码中需要排序或者选出最小权值结点的过程):

赫夫曼树的应用-赫夫曼编码

在现实生活中，我们通常经常会遇到对数据进行编码的场景，目的是为了对数据进行一定程度的压缩的同时也能对原始数据进行加密工作，从而避免原始数据暴露在网络中。最简单的方法是对每个原始数据的每个源符号生成一个固定长度的编码，然后用编码替换每个源符号，以达到对整个数据编码的目的。但是这种方法有两个弊端:

1. 每个编码长度固定，容易被破译。

2. 每个编码长度固定，导致编码后的数据长度不尽如人意。

而赫夫曼编码则很好的规避了这两个问题，赫夫曼编码使用变长编码表对源符号进行编码，其中每个编码的长度是根据评估源符号出现几率的方法得到的，即出现频率高的源符号使用较短的编码，反之使用较长的编码，这样编码后的数据整体平均长度降低，从而实现更高效的压缩。例如在英文中，e的出现几率最高，而z的出现几率最低，当利用赫夫曼编码对一篇英文进行压缩时，假设e用一个bit来表示，而z则可能用25个bit表示。如果使用定长的编码表示，每个英文字母使用8个bit来表示。二者相比，普通方法中，频率最高的e就会浪费7个bit，而赫夫曼中z则是3倍多，但是如果能够对英文中各个字母出现的概率有较准确的估算，则可以大幅度的提高无损压缩比例。

赫夫曼编码是对赫夫曼树的一种应用，常用于处理符号编写工作，根据原始数据中符号出现的频率高低，决定如何给符号编码，频率越高的符号编码越短，相反编码越长。

赫夫曼编码是由通过构造赫夫曼树生成的一种编码。编码生成过程如下:

假设给定的某些英文符号的出现频率如下表所示:

符号	A	B	C	D	E	F
频率	2	3	4	4	5	7

我们以频率为权值构造6棵只有一个结点的二叉树，然后按照赫夫曼树的构造规则构造赫夫曼树:

构造好赫夫曼树后，下一步便是进行编码，赫夫曼编码步骤为:

1. 给赫夫曼树中存在孩子结点的左路径编码”0”，右路径编码”1”
2. 从赫夫曼树的根结点开始到每一个叶子结点所经过的路径的编码组成的一个编码串便是该叶子结点代表的符号的赫夫曼编码。

如下图:

根据上图得到每个字符的编码为:

符号	A	B	C	D	E	F
频率	2	3	4	4	5	7
编码	010	011	110	111	00	10

注意: 赫夫曼编码并不唯一，如上图中的C和D的位置可以互换

对数据编码的过程为构造赫夫曼树，然后根据生成的编码来进行压缩，而数据解码则与编码相反，解码根据给定的编码数据，遍历赫夫曼树得到原始数据。下面为用Go语言实现的赫夫曼树。

代码实现

type HuffmanNodeList []*HuffmanNode

func (list HuffmanNodeList) Len() int {
	return len(list)
}

func (list HuffmanNodeList) Swap(i, j int) {
	list[i], list[j] = list[j], list[i]
}

func (list HuffmanNodeList) Less(i, j int) bool {
	return list[i].Weight < list[j].Weight
}

//赫夫曼节点，用于构成赫夫曼树
type HuffmanNode struct {
	Weight uint         //权重
	Data   interface{}  //数据
	Parent *HuffmanNode //父节点
	Left   *HuffmanNode //左孩子
	Right  *HuffmanNode //右孩子
}

//赫夫曼树结构，这里使用的interface作为源数据类型
type HuffmanTree struct {
	root    *HuffmanNode           //根节点
	leaf    HuffmanNodeList        //所有叶子节点（即数据对应的节点）
	src     map[interface{}]uint   //源数据，key为数据，value为权重
	codeSet map[interface{}]string //编码集，key为数据，value为通过构造赫夫曼树得到的数据的编码
}

//给定一组字符及其权重的集合，初始化出一棵赫夫曼树
func NewHuffmanTree(src map[interface{}]uint) *HuffmanTree {
	var tree = &HuffmanTree{
		src: src,
	}
	tree.init()
	tree.build()
	tree.parse()
	return tree
}

//根据数据进行赫夫曼编码
func (h *HuffmanTree) Coding(target interface{}) (result string) {
	if target == nil {
    		return
    	}
    	var s string
    	switch t := target.(type) {
    	case string:
    		s = t
    	case []byte:
    		s = string(t)
    	default:
    		return
    	}
    	for _, t := range s {
    		v := string(t)
    		if c, ok := h.codeSet[v]; !ok {
    			panic("invalid code: " + v)
    		} else {
    			result += c
    		}
    	}
    	return result
}

//根据赫夫曼编码获取数据
func (h *HuffmanTree) UnCoding(target string) (result string) {
	node := h.root
	for i := 0; i < len(target); i++ {
		switch target[i] {
		case '0':
			node = node.Left
		case '1':
			node = node.Right
		}
		if node.Left == nil && node.Right == nil {
			result = result + node.Data.(string)
			node = h.root
		}
	}
	return
}

//初始化所有叶子节点
func (h *HuffmanTree) init() {
	if len(h.src) <= 1 {
		panic("invalid src length.")
	}
	h.codeSet = make(map[interface{}]string)
	h.leaf = make(HuffmanNodeList, len(h.src))
	var i int
	for data, weight := range h.src {
		var node = &HuffmanNode{
			Weight: weight,
			Data:   data,
		}
		h.leaf[i] = node
		i++
	}
	//对leaf根据权值排序
	sort.Sort(h.leaf)
}

//构造赫夫曼树
//src: key为data，value为权值
func (h *HuffmanTree) build() {
	nodeList := h.leaf
	//根据huffman树的规则构造赫夫曼树
	for nodeList.Len() > 1 {
		//1. 选取权值最小的两个node构造出第一个节点
		var temp = &HuffmanNode{
			Weight: nodeList[0].Weight + nodeList[1].Weight,
			Left:   nodeList[0],
			Right:  nodeList[1],
		}
		nodeList[0].Parent = temp
		nodeList[1].Parent = temp

		//2.将生成的新节点插入节点序列中
		nodeList = regroup(nodeList[2:], temp)
	}
	h.root = nodeList[0]
}

//获取每个byte的编码，目的是为了下次需要编码的时候不用再次遍历树以获取每个byte的编码了
//在赫夫曼树中的所有节点要么没有孩子节点，要么有两个孩子节点，不存在只有一个孩子节点的节点
//此处的编码为由底至顶获取，也可以由顶至底的获取
func (h *HuffmanTree) parse() {
	if h.root == nil {
		return
	}
	var temp *HuffmanNode
	var code string
	for _, n := range h.leaf {
		temp = n
		for temp.Parent != nil {
			if temp == temp.Parent.Left {
				code = "0" + code
			} else {
				code = "1" + code
			}
			temp = temp.Parent
		}
		h.codeSet[n.Data] = code
		code = ""
	}
}

//重组，将生成的节点放入既有的list，排序后返回，权值最小的始终在最前面
func regroup(src HuffmanNodeList, temp *HuffmanNode) HuffmanNodeList {
	//将temp添加进src，然后取出weight最小的一个
	length := len(src)
	result := make(HuffmanNodeList, len(src)+1)
	if length == 0 {
		result[0] = temp
		return result
	}
	if src[length-1].Weight <= temp.Weight {
		copy(result, src)
		result[length] = temp
		return result
	}
	for i := range src {
		if src[i].Weight <= temp.Weight {
			result[i] = src[i]
		} else {
			result[i] = temp
			copy(result[i+1:], src[i:])
			break
		}
	}
	return result
}

参考文献

《数据结构(C语言版)》

《Wiki》

最后

谢谢阅读，此处为源码，欢迎赏脸！