哈夫曼树（哈夫曼建树及编码）

本文主要是介绍哈夫曼树（哈夫曼建树及编码），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

哈夫曼树是数据结构的一种，用于实现无损压缩。压缩分为无损压缩和有损压缩，使用哈夫曼压缩的压缩比可达3:1到5:1，流行的有损压缩方法有lzw字典压缩等。

几个名词解释：

最优二叉树：树的加权路径总长度最短的二叉树。

权值：每个叶子节点带有一定的权值，在哈夫曼树中为该叶子节点代表的字符的出现频率。

树的加权路径总长度：各叶子节点到根节点的路径长度与该节点的权的乘积的总和。

加权路径长度：从根节点到该节点之间的路径长度与该节点的权的乘积。

路径长度（深度）：当前节点到根节点所经历的层数。

叶子节点：没有子树的节点。

根节点：没有父节点的节点。

哈夫曼树属于二叉树的一种，是一种非线性的数据结构，其实现压缩的思想大致如下：

举个例子：英文中各个字母出现的频率是大不相同的，因此，对不同字母的编码长度若相同，就会浪费太多的空间，若给予出现频率较高的字符以较短的编码，而出现频率较少的字符以较长的编码。那么，总体的编码长度便会大大缩短，把该二进制编码存进文件中可实现压缩。术语志之曰：“最优编码方法”。哈夫曼树是一种最优二叉树，其自下向上的建树方法使得权值越大的节点越靠近根节点。

实现过程：

1.统计字符频率

建一个大小为256的byte数组，使用位映射，每读入一个字节，便在数组中该字节对应的ASCII码对应的位置加一，这样一来，文件读完的时候，字符频率也就统计完了。如：读入字符a，便使byte数组的下标为97的元素加一。

//统计字符频率
private byte[] bytecount = new byte[256];
public void countWeight() throws IOException {
java.io.InputStream fins = new java.io.FileInputStream(
"D:/JAVA/TestForIO(java)/testforIO.txt");
while (fins.available() > 0) {
int i = fins.read();// 读入字节
bytecount[i]++;// 统计每个字节出现的次数（位图映射）
}
fins.close();
}

2.建树

i.使用队列，把字符及其频率存到一个队列中。

ii.对队列按频率大小进行排序，取频率最小的两个节点，生成一个父节点，权值为两个节点的频率之和，然后把这两个元素从队列中删掉，把父节点存到队列中。然后又排序，生成······如此往复，直到队列中只剩下一个节点，该节点就是根节点。

/*
* 使用队列构建哈夫曼树
*/
private static HuffNode root;// 声明根节点
public void creatHuffTree() {
ArrayList<HuffNode> quene = new ArrayList<HuffNode>();// 创建队列，使用指定排序规则
// 把所有节点加入队列中
for (int i = 0; i < bytecount.length; i++) {
if (bytecount[i] != 0) {
// System.out.println(((char) i) + "    " + bytecount[i]);
HuffNode node = new HuffNode((char) i, bytecount[i]);
quene.add(node);// 加入节点
}
}
// 构建哈夫曼树
while (quene.size() != 1) {
sort(quene);
HuffNode min1 = quene.get(0);// 获取队列头两个
quene.remove(0);
HuffNode min2 = quene.get(0);
quene.remove(0);
HuffNode result = new HuffNode('-', min1.times + min2.times);
result.leftchild = min1;
result.rightchild = min2;
quene.add(result);
}
// 得到根节点
root = quene.get(0);
System.out.println("root=" + root.data + "    " + root.times);
}

3.编码

哈夫曼树建成后，对其进行编码，左边子树编码为0，右边为1。

// (前序遍历)
private Code[] saveCode = new Code[256];// 创建一个code数组，储存每个字符对应的编码和编码长度
public void getMB(HuffNode root, String s) {
if (root.leftchild == null && root.rightchild == null) {
Code huffcode = new Code();
huffcode.length = s.length();// 把编码串的长度存到huffcode的length属性中
huffcode.code = s;// 把编码串存到huffcode的code属性中
saveCode[root.data] = huffcode;// 把huffcode对象存进saveCode对象数组中
System.out.println("节点" + root.data + "编码" + huffcode.code);
System.out.println("节点" + root.data + "次数" + huffcode.length);
}
// 左0右1
if (root.leftchild != null) {
getMB(root.leftchild, s + "0");
}
if (root.rightchild != null) {
getMB(root.rightchild, s + "1");
}
}

为便于理解，建树及编码过程如图所示（图片来自维基百科）：

各字符频率如下：