数据结构与算法(十)

树结构实际应用

赫夫曼树

基本介绍

1. 给定 n 个 权值 作为 n 个 叶子节点，构造一颗二叉树，若该树的 带权路径长度（WPL）达到最小，称这样的二叉树为 最优二叉树，也称为 哈夫曼树（Huffman Tree），还有的叫 霍夫曼树
2. 赫夫曼树是带全路径长度最短的树，权值较大的节点离根节点较近

重要概念

• 路径 和 路径长度：

  在一颗树中，从一个节点往下可以到达的孩子或孙子节点之间的通路，称为 路径。

  通路中分支的数目称为路径长度。若规定根节点的层数为 1，则从根节点到第 L 层节点的路径长度为 L-1

• 节点的权 及 带权路径长度

  若将树中节点赋给一个有着某种函数的数值，则这个数值称为该节点的 权。

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

• 树的带权路径长度

  所有叶子节点的带权路径长度之和，记为 WPL（weighted path length），权值越大的节点离根节点越近的二叉树才是最优二叉树

• WPL 最小的就是赫夫曼树
  

如上图：

• 权：元素的值
• 路径长度：一个节点到另一个节点的一段路，就叫路径长度
• 带权路径长度：从根节点到 13 有几条路径长度，则是他的带权路径长度
• 树的带权路径长度：（图上的带全路径长度所指的是 树的带全路径长度）

创建思路

以数列 13,7,8,3,29,6,1 进行讲解。

1. 首先将它进行从小到大进行排序，排序后是：1,3,6,7,8,13,29

   其中，每一个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树

2. 取出根节点权值最小的两颗树：1 和 3

3. 组成一颗新的二叉树，该二叉树的根节点权值是，这两颗树的权值之和，如下图：
   

4. 再将这颗新的二叉树，以 根节点的权值大小，再次排序，并不断重复上述步骤
   

5. 将剩余未处理的节点，与新的根节点权值进行排序，那么再次取最小的两棵树 4 和 6，组成新的根节点 10,一般来说，可以将左节点指向权值较大的，右节点指向权值较小的。以上过程重复处理，直到组成如下图这颗赫夫曼树
   

代码实现

复制代码

	public class HuffmanTree {
	public static void main(String[] args) {
	int[] arr = {13,7,8,3,29,6,1};
	Node root = createHuffman(arr);
	preOrder(root);
	}
	//前序输出
	public static void preOrder(Node root){
	if(root != null){
	root.preOrder();
	}else{
	System.out.println("霍夫曼树为空");
	}
	}
	/**
	* 创建哈夫曼树
	* @param arr 要创建树的数据队列
	*/
	public static Node createHuffman(int[] arr){
	//循环遍历数组，使用Node封装每个数据，并装入到集合ArrayList中方便进行排序，取出
	ArrayList<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 rightNode = nodes.get(1);
	Node parent = new Node(leftNode.value + rightNode.value);
	parent.left = leftNode;
	parent.right = rightNode;
	//将最小的两个节点从集合中移出，添加新节点
	nodes.remove(leftNode);
	nodes.remove(rightNode);
	nodes.add(parent);
	}
	return nodes.get(0);
	}
	}
	//创建节点,为了让Node节点能够进行比较排序，实现Comparable接口
	class Node implements Comparable<Node>{
	int value;
	Node left;
	Node right;
	public Node(int value){
	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 年提出一种编码方法，称之为最佳编码

原理剖析

1. 定长编码

复制代码

	// 原始字符，共40个字符(包括空格)
	i like like like java do you like a java
	// 对应 Ascii 码
	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. 变长编码

复制代码

	// 原始字符，共40个字符(包括空格)
	i like like like java do you like a java
	// 各个字符对应的个数
	d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9
	// 按照各个字符出现的次数进行编码，原则是出现次数越多的，则编码越小，比如 空格出现了 9 次， 编码为 0 ,其它依次类推.
	// 等号前面的数字就是就是赫夫曼树节点的带权路径，后面讲解为什么
	0= , 1=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d

按照上面给各个字符规定的编码，对于原始字符 i like like like java do you like a java，进行编码时，对应的编码为：

复制代码

	i 空格 l i k
	10 0 101 10 100 ...
	传输的编码就是：10010110100 ...

注意： 字符的编码都不能是其他字符编码的前缀，符合此要求的编码叫做 前缀编码，即不能匹配到重复的编码。（下面会详细讲解）

3. 赫夫曼编码

复制代码

	// 原始字符，共40个字符(包括空格)
	i like like like java do you like a java
	// 各个字符对应的个数
	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%。

此编码满足前缀编码，即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性，比如：

复制代码

	比如前面的这一串编码：101010011011110
	i 空格 l i k
	101 01 001 101 1110

简单说就是：上面给出的每个字符的编码都是唯一的，

注意事项

赫夫曼树 根据排序方法不同，也可能不太一样，这样对应的 赫夫曼编码 也不完全一样，但是 WPL 是一样的，都是最小的，最后生成的赫夫曼编码的长度是一样。

什么意思呢：比如这个数列 4,4,4,4,4,4,4,5,6,7，有很多相同的树节点，每次取最小的两个组成一颗新树：

复制代码

	原始：4,4,4,4,4,4,4,5,6,7
	第一次：4,4,4,4,4,5,6,7,8 # 处理排序之后，减少了两个 4，多了一个 8 的树
	第二次：4,4,4,5,6,7,8,8 # 处理排序之后，减少了两个 4，多了一个 8 的树

那么问题就来了：相同的权值，你怎么排序？这个就是排序不稳定。导致后面每次重新生成树的编码都对应不上同一个字符。

但是他们的 WPL 是一样的，也就是最后用赫夫曼编码之后的数据长度都是一样的（压缩程度是一样的）。

下面对比下规则的不同，生成的树不同：

前面给出的图是：每次生成新的二叉树排在相同权值的前面

下面是每次生成新的二叉树总是排在权值相同的二叉树的最后一个，则生成二叉树为：

最明显的就是右下角的，2+2=4，第一张图是放在左下角的的 4 节点下，这里是放在右下角的 4 节点下

最佳实践-数据压缩

根据赫夫曼编码压缩数据的原理，创建 i like like like java do you like a java 字符串对应的赫夫曼树。

创建赫夫曼树

思路：

1. 创建 Node，具有如下属性：

   • data：存放对应的字符
   • weight：该字符出现的总次数
   • left：左节点
   • right：右节点

2. 得到该字符串的 byte 数组

   在 Java中，中英文得到的 byte 是不一样的，比如

   复制代码

   	System.out.println("i".getBytes().length); // 1
   	System.out.println("中".getBytes().length); // 3

   也就是说，我们是对 byte 进行压缩，最后还原成这个 byte 数组。

   比如 UTF-8 编码得到的 bytes，它的英文一个 byte 就对应了 ASCII 码值

3. 构建这个 byte 数组对应的 Node 列表

4. 对这个 Node 列表进行哈夫曼树构建

   复制代码

   	//定义Node节点
   	class Node implements Comparable<Node>{
   	Byte data;//存放实际的数据
   	int weight;//每个节点的权重，也就是出现的次数
   	Node left;
   	Node right;
   	public Node(Byte data, int weight) {
   	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;
   	}
   	}
   	//将对应的字符数组转换成List集合，里面存放的是Node节点
   	public static List<Node> getNodeList(byte[] arr){
   	ArrayList<Node> nodes = new ArrayList<>();
   	//使用Map统计每次字符出现的次数
   	HashMap<Byte, Integer> map = new HashMap<>();
   	for(Byte b : arr){
   	Integer count = map.get(b);
   	if(count == null){//还不存在该元素的键值对，添加
   	map.put(b,1);
   	}else{//已经存在该元素的键值对，将value+1
   	map.put(b,count+1);
   	}
   	}
   	//遍历完成之后，将所有元素封装到Node节点中，放到List返回
   	for(Map.Entry<Byte,Integer> entry: map.entrySet()){
   	nodes.add(new Node(entry.getKey(),entry.getValue()));
   	}
   	return nodes;
   	}
   	/**
   	* 创建赫夫曼树
   	* @param nodes 原始数组的节点集合
   	* @return 赫夫曼树
   	*/
   	public static Node createHuffmanTree(List<Node> nodes){
   	while(nodes.size() > 1){
   	//1.排序
   	Collections.sort(nodes);
   	//获取两个最小权值的节点，创建树
   	Node leftNode = nodes.get(0);
   	Node rightNode = nodes.get(1);
   	Node parent = new Node(null, leftNode.weight + rightNode.weight);
   	parent.left = leftNode;
   	parent.right = rightNode;
   	nodes.remove(leftNode);
   	nodes.remove(rightNode);
   	nodes.add(parent);
   	}
   	return nodes.get(0);
   	}

赫夫曼编码表

我们要得到 赫夫曼编码 前，还要先构建出 赫夫曼编码表，如下所示

复制代码

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

注意：前面已经说过了，根据排序稳定性不同，得到编码表可能也不同，但是最终得到的数据编码长度是一致的。

思路分析：

1. 用 Map<Byte,String> 来保存编码表
2. 获取到每个叶子节点的 权路径：如 110

代码实现如下

复制代码

	//重载
	public static Map<Byte,String> getCodeTable(Node root){
	if(root == null){
	System.out.println("当前赫夫曼树为空");
	return null;
	}
	getCodeTable(root.left,"0",stringBuilder);
	getCodeTable(root.right,"1",stringBuilder);
	return huffmanCode;
	}
	/**
	* 用于构建当前的赫夫曼编码表
	* @param node 要构建编码的节点
	* @param code 编码，规定，左子树节点为0，右子树节点为1
	* @param StringBuilder 拼接编码
	*/
	private static void getCodeTable(Node node,String code,StringBuilder StringBuilder){
	StringBuilder stringBuilder1 = new StringBuilder(StringBuilder);
	stringBuilder1.append(code);
	if(node != null){
	if(node.data == null){
	//非叶子节点，递归继续拼接编码
	//拼接左子树
	getCodeTable(node.left,"0",stringBuilder1);
	//拼接右子树
	getCodeTable(node.right,"1",stringBuilder1);
	}else{
	//叶子节点,将当前节点加入到Map中
	huffmanCode.put(node.data,stringBuilder1.toString());
	}
	}
	}

赫夫曼编码

根据 编码表 来得到 数据编码

思路：

1. 将原始字符串的 byte 数组，转成 赫夫曼编码对应的值

   也就是如上的 10101001101

   这一步的实现，直接遍历原始字符串的 byte 数组，从编码表中获取对应的编码拼接起来就可以了

2. 将赫夫曼编码字符串，转成 byte 数组，做法如下：

   一个 byte 是 8 位，所以将赫夫曼编码字符串按 8 位分割，每一个 8 位都可以转成一个 byte

   这里涉及到的是 Java 基础中的二进制转码：原码、补码、反码知识点。 最简单的使用 Integer 的 API parseInt 转成一个 Byte 。这是因为数据发送也是通过 byte 二进制发送的。

   复制代码

   	/**
   	* 将原字节数组通过赫夫曼编码转换成压缩后的字节数组
   	* @param byteCount 要压缩的字节数组
   	* @param huffmanCode 赫夫曼编码表
   	* @return 压缩后的字节数组
   	*/
   	public static byte[] zip(byte[] byteCount,Map<Byte,String> huffmanCode){
   	//用于拼接赫夫曼编码的String
   	StringBuilder stringBuilder = new StringBuilder();
   	for(byte b : byteCount){
   	stringBuilder.append(huffmanCode.get(b));
   	}
   	//System.out.println("测试编码之后的字符串：" + stringBuilder.toString());
   	//构建要返回的字节数组长度
   	int len;
   	if(stringBuilder.length()/8 == 0){
   	len = stringBuilder.length()/8;
   	}else{
   	len = stringBuilder.length()/8 + 1;
   	}
   	//创建要返回的byte数组
   	byte[] huffmanCountByte = new byte[len];
   	int index = 0;
   	for(int i = 0; i < stringBuilder.length(); i += 8){
   	String strByte;
   	if(i+8 > stringBuilder.length()){
   	strByte = stringBuilder.substring(i);
   	}else{
   	strByte = stringBuilder.substring(i,i+8);
   	}
   	//通过二进制输入数据得到int类型数据转换成byte
   	huffmanCountByte[index] = (byte)Integer.parseInt(strByte,2);
   	index++;
   	}
   	return huffmanCountByte;
   	}

   封装

   复制代码

   	/**
   	* 对字节数组中的数据进行赫夫曼编码返回
   	* @param srcByte 要进行编码的原数组
   	* @return 编码后的字节数组
   	*/
   	public static byte[] huffmanZip(byte[] srcByte){
   	//将对应的字符数组转换成List集合，里面存放的是Node节点，方便后续操作
   	List<Node> nodes = getNodeList(srcByte);
   	//创建赫夫曼树
   	Node root = createHuffmanTree(nodes);
   	//用于构建当前的赫夫曼编码表
   	Map<Byte, String> codeTable = getCodeTable(root);
   	//将原字节数组通过赫夫曼编码转换成压缩后的字节数组
   	byte[] huffmanCodeBytes = zip(srcByte, codeTable);
   	return huffmanCodeBytes;
   	}

    

   最佳实践-数据解压

   复制代码

   	赫夫曼编码字节数组：[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
   	↓ 转换成
   	原始字符串：i like like like java do you like a java

   byte 转二进制字符串

   首先里面有一个知识点是：将 byte 转成二进制的字符串显示

   需要注意的是：我们之前生成的赫夫曼编码字符串，转成 byte 时，它是补码（正数的补码就是原码）。所以在数据解压的时候，要按补码的方式进行还原。

   复制代码

   	/**
   	* 将一个byte转换成二进制的字符串
   	* @param flag 是否需要补高位，真补高位,最后一个字节无序补高位
   	* @param b 传入b
   	* @return 返回转换后的字符串
   	*/
   	private static String byteToString(boolean flag,byte b){
   	int temp = b;
   	if(flag){
   	temp |= 256;
   	}
   	String str = Integer.toBinaryString(temp);
   	if(flag){
   	return str.substring(str.length()-8);
   	}else{
   	return str;
   	}
   	}

   解码

   复制代码

   	/**
   	* 将赫夫曼编码后的字符串解码成原数据
   	* @param huffmanCode 赫夫曼编码表
   	* @param codeBytes 要进行解码的字节数组
   	* @return 解压后的数据
   	*/
   	private static byte[] decode(Map<Byte,String> huffmanCode,byte[] codeBytes){
   	//1.先将压缩数组转换成字符串
   	StringBuilder stringBuilder = new StringBuilder();
   	for(int i = 0; i < codeBytes.length; i++){
   	Byte b = codeBytes[i];
   	boolean flag = (i == codeBytes.length-1);
   	stringBuilder.append(byteToString(!flag,b));
   	}
   	//System.out.println(stringBuilder.length() + " " + stringBuilder.toString());
   	//2.将赫夫曼编码表反转，
   	HashMap<String, Byte> map = new HashMap<>();
   	for(Map.Entry<Byte,String> entry : huffmanCode.entrySet()){
   	map.put(entry.getValue(),entry.getKey());
   	}
   	//System.out.println(map);
   	ArrayList<Byte> bytes = new ArrayList<>();
   	//循环遍历转换byte
   	for(int i = 0; i < stringBuilder.length();){
   	int count = 1;
   	boolean flag = true;
   	Byte b = null;
   	while(flag){
   	String key = stringBuilder.substring(i,i+count);
   	b = map.get(key);
   	if(b == null){
   	count++;
   	}else{
   	flag = false;
   	}
   	}
   	bytes.add(b);
   	i += count;
   	}
   	byte[] b = new byte[bytes.size()];
   	for(int i = 0; i < bytes.size(); i++){
   	b[i] = bytes.get(i);
   	}
   	return b;
   	}

   文件压缩和解压

   复制代码

   	/**
   	* 实现对文件的压缩
   	* @param srcFile 要压缩的文件
   	* @param descFile 压缩之后的文件
   	*/
   	public static void zipFile(String srcFile,String descFile){
   	InputStream is = null;
   	OutputStream os = null;
   	ObjectOutputStream oos = null;
   	try{
   	//读取文件
   	is = new FileInputStream(srcFile);
   	int len = is.available();
   	byte[] huffmanByte = new byte[len];
   	is.read(huffmanByte);
   	//对数据进行压缩
   	byte[] bytes = huffmanZip(huffmanByte);
   	os = new FileOutputStream(descFile);
   	oos = new ObjectOutputStream(os);
   	//将文件写出
   	oos.writeObject(bytes);
   	//写出赫夫曼编码表
   	oos.writeObject(huffmanCode);
   	}catch(IOException e){
   	System.out.println(e.getMessage());
   	}finally {
   	try {
   	oos.close();
   	os.close();
   	is.close();
   	} catch (IOException e) {
   	e.printStackTrace();
   	}
   	}
   	}
   	/**
   	* 对压缩文件进行解压
   	* @param srcFile 解压源文件
   	* @param descFile 解压后的文件
   	*/
   	public static void unZipFile(String srcFile,String descFile){
   	InputStream is = null;
   	ObjectInputStream ois = null;
   	OutputStream os = null;
   	try{
   	is = new FileInputStream(srcFile);
   	ois = new ObjectInputStream(is);
   	//读取压缩文件
   	byte[] huffmanBytes = (byte[])ois.readObject();
   	//读取赫夫曼编码表
   	Map<Byte,String> huffmanCode = (Map<Byte,String>)ois.readObject();
   	//获取解压后的字节数组
   	byte[] decode = decode(huffmanCode, huffmanBytes);
   	os = new FileOutputStream(descFile);
   	os.write(decode);
   	}catch(IOException | ClassNotFoundException e){
   	System.out.println(e.getMessage());
   	}finally {
   	try {
   	os.close();
   	ois.close();
   	is.close();
   	} catch (IOException e) {
   	e.printStackTrace();
   	}
   	}
   	}