哈夫曼树

基本概念

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

树的路径长度就是从树根到每一结点的路径长度之和。

若将树中结点赋予一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL(weighted path length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。WPL最小的就是赫夫曼树，也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。

哈夫曼树的创建

思路分析：

每个数据都是一个节点，从小到大进行排序, 每个节点可以看成是一颗最简单的二叉树。

取出节点权值最小的两颗二叉树。组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和。

再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复2-3的步骤，直到数列中，所有的数据都被处理，只剩下一个节点时就得到一颗赫夫曼树。

代码实现：

package com.nanzx.huffmantree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class HuffmanTree {

	public static void main(String[] args) {
		int[] arr = { 13, 7, 8, 3, 29, 6, 1 };
		Node root = createHuffmanTree(arr);
		preOrder(root);
	}

	public static void preOrder(Node root) {
		if (root != null) {
			root.preOrder();
		} else {
			System.out.println("根节点为空，不能遍历");
		}
	}

	public static Node createHuffmanTree(int[] arr) {
		List<Node> nodes = new ArrayList<Node>();
		for (int value : arr) {
			nodes.add(new Node(value));
		}

		while (nodes.size() > 1) {
			Collections.sort(nodes);

			Node leftNode = nodes.get(0);
			Node righNode = nodes.get(1);

			Node parentNode = new Node(leftNode.value + righNode.value);
			parentNode.left = leftNode;
			parentNode.right = righNode;

			nodes.remove(leftNode);
			nodes.remove(righNode);
			nodes.add(parentNode);
		}

		return nodes.get(0);
	}
}

class Node implements Comparable<Node> {
	int value;
	Node left;
	Node right;

	public Node(int value) {
		super();
		this.value = value;
	}

	// 前序遍历
	public void preOrder() {
		System.out.println(this);
		if (this.left != null) {
			this.left.preOrder();
		}
		if (this.right != null) {
			this.right.preOrder();
		}
	}

	@Override
	public String toString() {
		return "Node [value=" + value + "]";
	}

	@Override
	public int compareTo(Node o) {
		return this.value - o.value;
	}
}

哈夫曼编码

基本介绍：

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法。

哈夫曼编码是哈夫曼树在电讯通信中的经典的应用之一。

哈夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%～90%之间。

哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，称之为最佳编码。

原理剖析：在线转码工具 (https://www.mokuge.com/tool/asciito16/ )

通信领域中信息的处理方式1-定长编码

i like like like java do you like a java // 共40个字符(包括空格)

105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118 97 32 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97 //对应Ascii码

01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001

//对应的二进制

按照二进制来传递信息，总的长度是 359 (包括空格)

通信领域中信息的处理方式2-变长编码

i like like like java do you like a java // 共40个字符(包括空格)

d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数

0= , 1=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d // 说明：按照各个字符出现的次数进行编码，原则是出现次数越多的，则编码越小，比如空格出现了9 次，编码为0 ,其它依次类推

按照上面给各个字符规定的编码，则我们在传输 “i like like like java do you like a java” 数据时，编码就是 10010110100…

通信领域中信息的处理方式3-赫夫曼编码

i like like like java do you like a java // 共40个字符(包括空格)

d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数

按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值

//根据赫夫曼树，给各个字符规定编码，向左的路径为0,向右的路径为1 ，编码如下:

o : 1000 u : 10010 d : 100110 y : 100111 i : 101
a : 110 k : 1110 e : 1111 j : 0000 v : 0001
l : 001 : 01

按照上面的赫夫曼编码，我们的”i like like like java do you like a java” 字符串对应的编码为 (注意这里我们使用的无损压缩)

1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110

长度为： 133
说明:
原来长度是 359 , 压缩了 (359-133) / 359 = 62.9%
此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性,变长编码有多义性

注意, 这个赫夫曼树根据权值的排序方法不同，也可能不太一样，相同权值的字符顺序不同，这样对应的赫夫曼编码也不完全一样，但是wpl 是一样的，都是最小的。

数据压缩

创建哈夫曼树

package com.nanzx.huffmancode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class HuffmanCode {

	public static void main(String[] args) {
		String content = "i like like like java do you like a java";
		byte[] contentBytes = content.getBytes();//会将字符转为Ascii码存储
		System.out.println(contentBytes.length);

		List<Node> nodes = getNodes(contentBytes);
		Node huffmanTreeRoot = createHuffmanTree(nodes);
		preOrder(huffmanTreeRoot);
	}

	public static void preOrder(Node root) {
		if (root != null) {
			root.preOrder();
		} else {
			System.out.println("根节点为空，不能遍历");
		}
	}

	public static List<Node> getNodes(byte[] contentBytes) {
		List<Node> nodes = new ArrayList<Node>();
		Map<Byte, Integer> map = new HashMap<Byte, Integer>();

		for (byte b : contentBytes) {
			Integer count = map.get(b);
			if (count == null) {
				map.put(b, 1);
			} else {
				map.put(b, count + 1);
			}
		}
		for (Map.Entry<Byte, Integer> e : map.entrySet()) {
			nodes.add(new Node(e.getKey(), e.getValue()));
		}
		return nodes;
	}

	public static Node createHuffmanTree(List<Node> nodes) {
		while (nodes.size() > 1) {
			Collections.sort(nodes);

			Node leftNode = nodes.get(0);
			Node righNode = nodes.get(1);

			Node pareNode = new Node(null, leftNode.weight + righNode.weight);
			pareNode.left = leftNode;
			pareNode.right = righNode;

			nodes.remove(leftNode);
			nodes.remove(righNode);
			nodes.add(pareNode);
		}

		return nodes.get(0);
	}
}

class Node implements Comparable<Node> {
	Byte data;
	int weight;
	Node left;
	Node right;

	public Node(Byte data, int weight) {
		super();
		this.data = data;
		this.weight = weight;
	}

	// 前序遍历
	public void preOrder() {
		System.out.println(this);
		if (this.left != null) {
			this.left.preOrder();
		}
		if (this.right != null) {
			this.right.preOrder();
		}
	}

	@Override
	public String toString() {
		return "Node [data=" + data + ", weight=" + weight + "]";
	}

	@Override
	public int compareTo(Node o) {
		return this.weight - o.weight;
	}
}

运行结果：

40
Node [data=null, weight=40]
Node [data=null, weight=17]
Node [data=null, weight=8]
Node [data=108, weight=4]
Node [data=null, weight=4]
Node [data=106, weight=2]
Node [data=111, weight=2]
Node [data=32, weight=9]
Node [data=null, weight=23]
Node [data=null, weight=10]
Node [data=97, weight=5]
Node [data=105, weight=5]
Node [data=null, weight=13]
Node [data=null, weight=5]
Node [data=null, weight=2]
Node [data=100, weight=1]
Node [data=117, weight=1]
Node [data=null, weight=3]
Node [data=121, weight=1]
Node [data=118, weight=2]
Node [data=null, weight=8]
Node [data=101, weight=4]
Node [data=107, weight=4]

生成哈夫曼编码表

// 生成赫夫曼树对应的赫夫曼编码
// 思路:
// 1. 将赫夫曼编码表存放在 Map<Byte,String> 形式
// 生成的赫夫曼编码表{32=01, 97=100, 100=11000, 117=11001...}
static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();
// 2. 在生成赫夫曼编码表时，需要去拼接路径, 定义一个StringBuilder存储某个叶子结点的路径
static StringBuilder stringBuilder = new StringBuilder();

/**
 * 功能：将传入的node结点的所有叶子结点的赫夫曼编码得到，并放入到huffmanCodes集合
 * 
 * @param node          传入结点
 * @param code          路径： 左子结点是 0, 右子结点 1
 * @param stringBuilder 用于拼接路径
 */
private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
	StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
	stringBuilder2.append(code);
	if (node.data == null) {
		getCodes(node.left, "0", stringBuilder2);
		getCodes(node.right, "1", stringBuilder2);
	} else {
		huffmanCodes.put(node.data, stringBuilder2.toString());
	}
}

// 为了调用方便，我们重载 getCodes
private static Map<Byte, String> getCodes(Node root) {
	if (root == null) {
		return null;
	} else {
		getCodes(root, "", stringBuilder);
		return huffmanCodes;
	}

运行结果：

{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}

压缩成哈夫曼字节数组

String content = “i like like like java do you like a java”; 原文
byte[] contentBytes = content.getBytes(); 会将原文字符转为Ascii码存储
1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100 将Ascii码用哈夫曼编码表转换
- byte[] huffmanCodeBytes ，即 8位对应一个 byte放入到 huffmanCodeBytes
  - 计算机中二进制都是以补码的形式表示的。
  - huffmanCodeBytes[0] = 10101000(补码) => [推导 10101000=> 10101000 - 1 => 10100111(反码)=> 11011000(原码)= -88 ]
  - huffmanCodeBytes[0] = -88

private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {

	// 1.利用 huffmanCodes哈夫曼编码表 将 contentBytes 转成 赫夫曼编码对应的字符串
	StringBuilder stringBuilder = new StringBuilder();
	for (byte b : bytes) {
		stringBuilder.append(huffmanCodes.get(b));
	}
	huffmanStr = stringBuilder;
       
	//2.将赫夫曼编码对应的字符串每8位（补码）进行压缩（十进制数）
	int lenth = 0;
	// 一句话 int len = (stringBuilder.length() + 7) / 8;
	if (stringBuilder.length() % 8 == 0) {
		lenth = stringBuilder.length() / 8;
	} else {
		lenth = stringBuilder.length() / 8 + 1;
	}
	byte[] huffmanCodeBytes = new byte[lenth];
	int index = 0;
	for (int i = 0; i < stringBuilder.length(); i = i + 8) {
		String strByte;
		if (i + 8 > stringBuilder.length()) {
			strByte = stringBuilder.substring(i);
		} else {
			strByte = stringBuilder.substring(i, i + 8);
		}
		huffmanCodeBytes[index++] = (byte) Integer.parseInt(strByte, 2);
	}
	return huffmanCodeBytes;
}

static StringBuilder huffmanStr = new StringBuilder();//存储赫夫曼编码对应的字符串

运行结果：

[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]

哈夫曼数据压缩封装

// 使用一个方法，将前面的方法封装起来，便于我们的调用.
/**
 * 
 * @param bytes 原始的字符串对应的字节数组
 * @return 是经过 赫夫曼编码处理后的字节数组(压缩后的数组)
 */
private static byte[] huffmanZip(byte[] bytes) {
	List<Node> nodes = getNodes(bytes);
	// 根据 nodes 创建的赫夫曼树
	Node huffmanTreeRoot = createHuffmanTree(nodes);
	// 对应的赫夫曼编码(根据 赫夫曼树)
	Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
	// 根据生成的赫夫曼编码，压缩得到压缩后的赫夫曼编码字节数组
	byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
	return huffmanCodeBytes;
}

数据解压

字节转二进制字符串

private static String byteToBitString(boolean flag, byte b) {
		int temp = b; 
		if (flag) {//当flag为true时，补高位
			temp |= 256; // 按位或 256 1 0000 0000 | 0000 0001 => 1 0000 0001
		}
		String str = Integer.toBinaryString(temp); // 返回的是temp对应的二进制的补码
		if (flag) { 
			return str.substring(str.length() - 8);
		} else {
			return str;
		}
	}

为什么补高位：

String str = Integer.toBinaryString(56); //返回 11 1000

String str = Integer.toBinaryString(56 | 256); //返回 1 0011 1000

为什么要截取8位：

String str = Integer.toBinaryString(56 | 256); //返回 1 0011 1000

String str = Integer.toBinaryString(-88); //返回11111111111111111111111110101000

String str = Integer.toBinaryString(-88 | 256); //返回11111111111111111111111110101000

哈夫曼解码

private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
		// 1.将压缩后的字节数组转换成原先的"10101000101111111..."
		StringBuilder stringBuilder = new StringBuilder();
		for (int i = 0; i < huffmanBytes.length - 1; i++) {
			stringBuilder.append(byteToBitString(true, huffmanBytes[i]));
		}
		// 字节数组的最后一个字节另做处理，如果是负数，flag为true；
		// 如果是正数，flag为false，拼接后长度与原先相等不做处理，若小于原先长度则先补0后拼接，使其与原先长度相等
		if (huffmanBytes[huffmanBytes.length - 1] < 0) {
			stringBuilder.append(byteToBitString(true, huffmanBytes[huffmanBytes.length - 1]));
		} else {
			String str = byteToBitString(false, huffmanBytes[huffmanBytes.length - 1]);
			while (str.length() + stringBuilder.length() < huffmanStr.length()) {
				stringBuilder.append(0);
			}
			stringBuilder.append(str);
		}

		// 2. 将哈夫曼编码表转换成哈夫曼解码表
		Map<String, Byte> huffmanDecodes = new HashMap<String, Byte>();
		for (Map.Entry<Byte, String> b : huffmanCodes.entrySet()) {
			huffmanDecodes.put(b.getValue(), b.getKey());
		}

		// 3.把"10101000101111111..."按照指定的哈夫曼解码表进行解码
		List<Byte> list = new ArrayList<Byte>();
		for (int i = 0; i < stringBuilder.length();) {
			int count = 1; // 小的计数器
			Byte b = null;

			while (true) {
				// 1010100010111...
				// 递增的取出 key 1
				String key = stringBuilder.substring(i, i + count);// i 不动，让count移动，指定匹配到一个字符
				b = huffmanDecodes.get(key);
				if (b == null) {// 说明没有匹配到
					count++;
				} else {
					// 匹配到
					break;
				}
			}
			list.add(b);
			i += count;// i 直接移动到 count
		}
		byte b[] = new byte[list.size()];
		for (int i = 0; i < b.length; i++) {
			b[i] = list.get(i);
		}
		return b;
	}

注意：韩顺平老师的代码是最后一个字节时，flag为false，不做任何处理。

BUG:如果压缩生成的最后一个byte数为负值，会多出24位1；

如果最后一个byte为001等前面有0的正数时，还原后会少了前面的0。

所以我们另外取最后一个字节处理。

文件压缩

public static void zipFile(String srcFile, String dstFile) {
		// 创建输出流
		OutputStream os = null;
		ObjectOutputStream oos = null;
		// 创建文件的输入流
		FileInputStream is = null;
		try {
			// 创建文件的输入流
			is = new FileInputStream(srcFile);
			// 创建一个和源文件大小一样的byte[]
			byte[] b = new byte[is.available()];
			// 读取文件
			is.read(b);
			// 直接对源文件压缩
			byte[] huffmanBytes = huffmanZip(b);
			// 创建文件的输出流, 存放压缩文件
			os = new FileOutputStream(dstFile);
			// 创建一个和文件输出流关联的ObjectOutputStream
			oos = new ObjectOutputStream(os);
			// 把 赫夫曼编码后的字节数组写入压缩文件
			oos.writeObject(huffmanBytes); // 我们是把
			// 这里我们以对象流的方式写入 赫夫曼编码，是为了以后我们恢复源文件时使用
			// 注意一定要把赫夫曼编码 写入压缩文件
			oos.writeObject(huffmanCodes);

		} catch (Exception e) {
			System.out.println(e.getMessage());
		} finally {
			try {
				is.close();
				oos.close();
				os.close();
			} catch (Exception e) {
				System.out.println(e.getMessage());
			}
		}
	}

文件解压

public static void unZipFile(String zipFile, String dstFile) {
		//定义文件输入流
		InputStream is = null;
		//定义一个对象输入流
		ObjectInputStream ois = null;
		//定义文件的输出流
		OutputStream os = null;
		try {
			//创建文件输入流
			is = new FileInputStream(zipFile);
			//创建一个和  is关联的对象输入流
			ois = new ObjectInputStream(is);
			//读取byte数组  huffmanBytes
			byte[] huffmanBytes = (byte[])ois.readObject();
			//读取赫夫曼编码表
			Map<Byte,String> huffmanCodes = (Map<Byte,String>)ois.readObject();
			
			//解码
			byte[] bytes = decode(huffmanCodes, huffmanBytes);
			//将bytes 数组写入到目标文件
			os = new FileOutputStream(dstFile);
			//写数据到 dstFile 文件
			os.write(bytes);
		} catch (Exception e) {
			System.out.println(e.getMessage());
		} finally {
			
			try {
				os.close();
				ois.close();
				is.close();
			} catch (Exception e2) {
				System.out.println(e2.getMessage());
			}	
		}
	}

可以看到压缩和解压成功了，解压后的图片与原来一致，大小也完全一样。

哈夫曼编码压缩文件注意事项

如果文件本身就是经过压缩处理的，那么使用赫夫曼编码再压缩效率不会有明显变化, 比如视频,ppt 等等文件。
赫夫曼编码是按字节来处理的，因此可以处理所有的文件(二进制文件、文本文件)。
如果一个文件中的内容，重复的数据不多，压缩效果也不会很明显。

哈夫曼树以及哈夫曼编码

哈夫曼树

基本概念

哈夫曼树的创建

哈夫曼编码

数据压缩

创建哈夫曼树

生成哈夫曼编码表

压缩成哈夫曼字节数组

哈夫曼数据压缩封装

数据解压

字节转二进制字符串

哈夫曼解码

文件压缩

文件解压

哈夫曼编码压缩文件注意事项