【数据结构(十·树结构的实际应用)】赫夫曼编码(3)

2023-12-12 04:12

本文主要是介绍【数据结构(十·树结构的实际应用)】赫夫曼编码(3),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 1. 基本介绍
    • 1.1. 赫夫曼编码基本概念
    • 1.2. 通信领域中的编码方式
      • 1.2.1. 定长编码
      • 1.2.2. 变长编码
      • 1.2.3. 赫夫曼编码(属于变长编码的一种)
  • 2. 实例应用-赫夫曼编码实现数据压缩
    • 2.1. 创建赫夫曼树
    • 2.2. 生成赫夫曼编码
      • 2.2.1. 生成赫夫曼树对应的赫夫曼编码表
      • 2.2.2. 赫夫曼编码字节数组(赫夫曼编码后的数据)
  • 3. 实例应用-赫夫曼编码实现数据解压
  • 4. 实例应用-使用赫夫曼编码压缩文件
    • 4.1. 压缩文件
    • 4.2. 解压文件
    • 4.3 赫夫曼编码压缩文件注意事项


1. 基本介绍

1.1. 赫夫曼编码基本概念

    赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法。赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。
    赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%~90%之间。
    赫夫曼码是
可变字长编码
(VLC)的一种。Huffman于1952年提出一种编码方法,称之为最佳编码。

1.2. 通信领域中的编码方式

    通信领域中信息的处理方式:有定长编码变长编码方式,其中定长编码需要的存储空间较大,通过使用变长编码能够提高存储利用率。

1.2.1. 定长编码

定长编码:

举例说明:

    i like like like java do you like a java // 共40个字符(包括空格)
    对上面这句话进行Ascii码转换和二进制转换,如下:
    
对应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
    
对应的二进制:
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 (包括空格)

1.2.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

注:先了解一下什么是前缀编码:
字符的编码都不能是其他字符编码的前缀,符合此要求的编码叫做前缀编码, 即不能匹配到重复的编码。
上面的变长编码不是一个前缀编码。

1.2.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,编码如下:

字符编码字符编码字符编码
o1000u10010d100110
y100111i101a110
k1110e1111j0000
v0001l001(空格)01

按照上面的赫夫曼编码,“i like like like java do you like a java” 字符串对应的编码为 (赫夫曼编码属于无损压缩)

对应的赫夫曼编码:
101 01 001 101 1110 1111 01 001 101 1110 1111 01 001 101 1110 1111 01 0000 110 0001 110 01 100110 1000 01 100111 1000 10010 01 001 101 1110 1111 01 110 01 0000 110 0001 110
长度为 : 133
    
说明:
    原来长度是 359 , 压缩了 (359-133) / 359 = 62.9%
    此编码满足前缀编码,即字符的编码都不能是其他字符编码的前缀,不会造成匹配的多义性。
    赫夫曼编码是无损处理方案


注意事项:
注意,这个赫夫曼树根据排序方法不同,也可能不太一样,这样对应的赫夫曼编码也不完全一样,但是 wpl 是 一样的,都是最小的,最后生成的赫夫曼编码的长度是一样。
比如:如果我们让每次生成的新的二叉树总是排在权值相同的二叉树的最后一个,则生成的二叉树为:
    在这里插入图片描述


2. 实例应用-赫夫曼编码实现数据压缩

    
问题:
    给出的一段文本,比如 “i like like like java do you like a java”
    根据前面的讲的赫夫曼编码原理,对其进行数据压缩处理,形式如:“101 01 001 101 1110 1111 01 001 101 1110 1111 01 001 101 1110 1111 01 0000 110 0001 110 01 100110 1000 01 100111 1000 10010 01 001 101 1110 1111 01 110 01 0000 110 0001 110”

2.1. 创建赫夫曼树

思路:前面已经分析过了
(1) 创建 Node { data (存放的数据), weight (权值), left , right }
(2) 得到 “i like like like java do you like a java” 对应的 byte[] 数组
(3) 编写一个方法,将准备构建赫夫曼树的Node 节点放到 List , 形式 [Node[data=97 ,weight = 5], Node[data=32,weight = 9]…], 体现 d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9
(4) 可以通过List 创建对应的赫夫曼树

代码实现:

package 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();System.out.println(contentBytes.length);// 40List<Node> nodes = getNodes(contentBytes);System.out.println("nodes = " + nodes);// 测试,创建的二叉树System.out.println("赫夫曼树");Node huffmanTreeRoot = createHuffmanTree(nodes);System.out.println("前序遍历");huffmanTreeRoot.preOrder();}// 前序遍历的方法private static void preOrder(Node root) {if (root != null) {root.preOrder();} else {System.out.println("赫夫曼树为空");}}/*** * @param bytes 接受一个字节数组* @return 返回的就是List形式: [Node[data=97 ,weight = 5], Node[data=32,weight = 9]…]*/private static List<Node> getNodes(byte[] bytes) {// 创建一个ArrayListArrayList<Node> nodes = new ArrayList<Node>();// 遍历bytes,统计每一个byte出现的次数->map[key, value]Map<Byte, Integer> counts = new HashMap<>();for (byte b : bytes) {Integer count = counts.get(b);if (count == null) {// Map还没有这个字符数据,第一次counts.put(b, 1);} else {counts.put(b, count + 1);}}// 把每个 键值对 转成一个Node对象,并加入到nodes集合// 遍历mapfor (Map.Entry<Byte, Integer> entry : counts.entrySet()) {nodes.add(new Node(entry.getKey(), entry.getValue()));}return nodes;}// 通过List创建对应的赫夫曼树private static Node createHuffmanTree(List<Node> nodes) {while (nodes.size() > 1) {// 排序,从小到大Collections.sort(nodes);// 取出第一个最小的二叉树Node leftNode = nodes.get(0);// 取出第二小的二叉树Node rightNode = nodes.get(1);// 创建一个新的二叉树,它的根节点:没有data,只有取值Node parent = new Node(null, leftNode.weight + rightNode.weight);parent.left = leftNode;parent.right = rightNode;// 将已经处理过的两颗二叉树从nodes删除nodes.remove(leftNode);nodes.remove(rightNode);// 将新的二叉树,接入到nodesnodes.add(parent);}// nodes最后的节点,就是赫夫曼树的根节点return nodes.get(0);}}//创建Node,带数据和权值
class Node implements Comparable<Node> {Byte data;// 存放数据(字符)本身,比如'a' => 97; ' ' => 32int weight;// 权值,表示字符出现的次数Node left;//Node right;public Node(Byte data, int weight) {this.data = data;this.weight = weight;}@Overridepublic int compareTo(Node o) {// 从小到大排序return this.weight - o.weight;}@Overridepublic String toString() {return "Node [data=" + data + ", weight=" + weight + "]";}// 前序遍历public void preOrder() {System.out.println(this);if (this.left != null) {this.left.preOrder();}if (this.right != null) {this.right.preOrder();}}}

运行结果:

在这里插入图片描述

2.2. 生成赫夫曼编码

前面已经生成了 赫夫曼树, 下面我们继续完成任务

步骤:

  1. 生成赫夫曼树对应的赫夫曼编码 , 如下表: =01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010 j=0010 k=1111 l=000 o=0011
字符编码字符编码字符编码
o0011u11001d11000
y11010i101a100
k1111e1110j0010
v11011l000(空格)01
  1. 使用赫夫曼编码来生成赫夫曼编码数据 ,即按照上面的赫夫曼编码,将"i like like like java do you like a java" 字符串生成对应的编码数据, 形式如下: 101 01 000 101 1111 1110 01 000 101 1111 1110 01 000 101 1111 1110 01 0010 100 11011 100 01 11000 0011 01 11010 0011 11001 01 000 101 1111 1110 01 100 01 0010 100 11011 100

2.2.1. 生成赫夫曼树对应的赫夫曼编码表

代码实现:

package 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();System.out.println(contentBytes.length);// 40List<Node> nodes = getNodes(contentBytes);System.out.println("nodes = " + nodes);// 测试,创建的二叉树System.out.println("赫夫曼树");Node huffmanTreeRoot = createHuffmanTree(nodes);System.out.println("前序遍历");huffmanTreeRoot.preOrder();// 测试是否生成了对应的赫夫曼编码Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);System.out.println("生成的赫夫曼编码表" + huffmanCodes);}// 生成赫夫曼树对应的赫夫曼编码表// 思路// 1. 将赫夫曼编码表存放在Map<Byte, String> 形式// 32->01 97->100 100->11000 等等[形式]static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();// 2. 在生成赫夫曼编码表示,需要去拼接路径,定义一个StringBuilder存储某个叶子结点的路径static StringBuilder stringBuilder = new StringBuilder();// 为了调用方便,重载getCodesprivate static Map<Byte, String> getCodes(Node root) {if (root == null) {return null;}// 处理root左子树getCodes(root.left, "0", stringBuilder);// 处理root右子树getCodes(root.right, "1", stringBuilder);return huffmanCodes;}/*** 功能:将传入的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);// 将code加入到stringBuilder2stringBuilder2.append(code);if (node != null) {// 如果node == null 不处理// 判断当前node是叶子结点还是非叶子节点if (node.data == null) {// 非叶子节点// 递归处理// 向左递归getCodes(node.left, "0", stringBuilder2);// 向右递归getCodes(node.right, "1", stringBuilder2);} else {// 说名明是一个叶子结点// 就表示找到了某一个叶子结点的最后huffmanCodes.put(node.data, stringBuilder2.toString());}}}// 前序遍历的方法private static void preOrder(Node root) {if (root != null) {root.preOrder();} else {System.out.println("赫夫曼树为空");}}/*** * @param bytes 接受一个字节数组* @return 返回的就是List形式: [Node[data=97 ,weight = 5], Node[data=32,weight = 9]…]*/private static List<Node> getNodes(byte[] bytes) {// 创建一个ArrayListArrayList<Node> nodes = new ArrayList<Node>();// 遍历bytes,统计每一个byte出现的次数->map[key, value]Map<Byte, Integer> counts = new HashMap<>();for (byte b : bytes) {Integer count = counts.get(b);if (count == null) {// Map还没有这个字符数据,第一次counts.put(b, 1);} else {counts.put(b, count + 1);}}// 把每个 键值对 转成一个Node对象,并加入到nodes集合// 遍历mapfor (Map.Entry<Byte, Integer> entry : counts.entrySet()) {nodes.add(new Node(entry.getKey(), entry.getValue()));}return nodes;}// 通过List创建对应的赫夫曼树private static Node createHuffmanTree(List<Node> nodes) {while (nodes.size() > 1) {// 排序,从小到大Collections.sort(nodes);// 取出第一个最小的二叉树Node leftNode = nodes.get(0);// 取出第二小的二叉树Node rightNode = nodes.get(1);// 创建一个新的二叉树,它的根节点:没有data,只有取值Node parent = new Node(null, leftNode.weight + rightNode.weight);parent.left = leftNode;parent.right = rightNode;// 将已经处理过的两颗二叉树从nodes删除nodes.remove(leftNode);nodes.remove(rightNode);// 将新的二叉树,接入到nodesnodes.add(parent);}// nodes最后的节点,就是赫夫曼树的根节点return nodes.get(0);}}//创建Node,带数据和权值
class Node implements Comparable<Node> {Byte data;// 存放数据(字符)本身,比如'a' => 97; ' ' => 32int weight;// 权值,表示字符出现的次数Node left;//Node right;public Node(Byte data, int weight) {this.data = data;this.weight = weight;}@Overridepublic int compareTo(Node o) {// 从小到大排序return this.weight - o.weight;}@Overridepublic String toString() {return "Node [data=" + data + ", weight=" + weight + "]";}// 前序遍历public void preOrder() {System.out.println(this);if (this.left != null) {this.left.preOrder();}if (this.right != null) {this.right.preOrder();}}}

运行结果:

在这里插入图片描述

2.2.2. 赫夫曼编码字节数组(赫夫曼编码后的数据)

编写一个方法,将字符串对应的byte[]数组,通过生成的赫夫曼编码表,返回一个赫夫曼编码压缩后的byte[]

代码实现:

package huffmancode;import java.util.ArrayList;
import java.util.Arrays;
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();System.out.println(contentBytes.length);// 40List<Node> nodes = getNodes(contentBytes);System.out.println("nodes = " + nodes);// 测试,创建的二叉树System.out.println("赫夫曼树");Node huffmanTreeRoot = createHuffmanTree(nodes);System.out.println("前序遍历");huffmanTreeRoot.preOrder();// 测试是否生成了对应的赫夫曼编码Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);System.out.println("生成的赫夫曼编码表" + huffmanCodes);// 测试byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);System.out.println("huffmanCodeBytes=" + Arrays.toString(huffmanCodeBytes));}// 编写一个方法,将字符串对应的byte[]数组,通过生成的赫夫曼编码表,返回一个护肤曼编码 压缩后的byte[]/*** * @param bytes        这是原始数组对应的byte[]* @param huffmanCodes 生成的赫夫曼编码map* @return 返回赫夫曼编码处理后的byte[] 举例:String content = "i like like like java do you*         like a java";-->byte[] contentBytes = content.getBytes(); 返回的是:101 01*         000 101 1111 1110 01 000 101 1111 1110 01 000 101 1111 1110 01 0010*         100 11011 100 01 11000 0011 01 11010 0011 11001 01 000 101 1111 1110*         01 100 01 0010 100 11011 100 -->对应的byte[] huffmanCodeBytes,*         即8位对应一个byte,放入到huffmanCodeBytes 其中,前8位对应的:huffmanCodeBytes[0] =*         10101000(补码)= 11011000 --> -88* */private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {// 1. 利用huffmanCodes 将bytes 转成赫夫曼编码对应的字符串StringBuilder stringBuilder = new StringBuilder();// 遍历bytes数组for (byte b : bytes) {stringBuilder.append(huffmanCodes.get(b));}System.out.println("测试stringBuilder=" + stringBuilder.toString());// 将"1010100010111..."转成byte[]// 统计返回的byte[] huffmanCodeBytes的长度// int len = (stringBuilder.length() + 7) / 8;int len;if (stringBuilder.length() % 8 == 0) {len = stringBuilder.length() / 8;} else {len = stringBuilder.length() / 8 + 1;}// 创建 存储压缩后的byte数组byte[] huffmanCodeBytes = new byte[len];int index = 0;// 记录是第几个bytefor (int i = 0; i < stringBuilder.length(); i += 8) {// 因为是每8位对应一个byte,所以步长 +8String strByte;if (i + 8 > stringBuilder.length()) {// 不够8位strByte = stringBuilder.substring(i);} else {strByte = stringBuilder.substring(i, i + 8);}// 将strByte 转成一个byte,放入到huffmanCodeByteshuffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);index++;}return huffmanCodeBytes;}// 生成赫夫曼树对应的赫夫曼编码表// 思路// 1. 将赫夫曼编码表存放在Map<Byte, String> 形式// 32->01 97->100 100->11000 等等[形式]static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();// 2. 在生成赫夫曼编码表示,需要去拼接路径,定义一个StringBuilder存储某个叶子结点的路径static StringBuilder stringBuilder = new StringBuilder();// 为了调用方便,重载getCodesprivate static Map<Byte, String> getCodes(Node root) {if (root == null) {return null;}// 处理root左子树getCodes(root.left, "0", stringBuilder);// 处理root右子树getCodes(root.right, "1", stringBuilder);return huffmanCodes;}/*** 功能:将传入的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);// 将code加入到stringBuilder2stringBuilder2.append(code);if (node != null) {// 如果node == null 不处理// 判断当前node是叶子结点还是非叶子节点if (node.data == null) {// 非叶子节点// 递归处理// 向左递归getCodes(node.left, "0", stringBuilder2);// 向右递归getCodes(node.right, "1", stringBuilder2);} else {// 说名明是一个叶子结点// 就表示找到了某一个叶子结点的最后huffmanCodes.put(node.data, stringBuilder2.toString());}}}// 前序遍历的方法private static void preOrder(Node root) {if (root != null) {root.preOrder();} else {System.out.println("赫夫曼树为空");}}/*** * @param bytes 接受一个字节数组* @return 返回的就是List形式: [Node[data=97 ,weight = 5], Node[data=32,weight = 9]…]*/private static List<Node> getNodes(byte[] bytes) {// 创建一个ArrayListArrayList<Node> nodes = new ArrayList<Node>();// 遍历bytes,统计每一个byte出现的次数->map[key, value]Map<Byte, Integer> counts = new HashMap<>();for (byte b : bytes) {Integer count = counts.get(b);if (count == null) {// Map还没有这个字符数据,第一次counts.put(b, 1);} else {counts.put(b, count + 1);}}// 把每个 键值对 转成一个Node对象,并加入到nodes集合// 遍历mapfor (Map.Entry<Byte, Integer> entry : counts.entrySet()) {nodes.add(new Node(entry.getKey(), entry.getValue()));}return nodes;}// 通过List创建对应的赫夫曼树private static Node createHuffmanTree(List<Node> nodes) {while (nodes.size() > 1) {// 排序,从小到大Collections.sort(nodes);// 取出第一个最小的二叉树Node leftNode = nodes.get(0);// 取出第二小的二叉树Node rightNode = nodes.get(1);// 创建一个新的二叉树,它的根节点:没有data,只有取值Node parent = new Node(null, leftNode.weight + rightNode.weight);parent.left = leftNode;parent.right = rightNode;// 将已经处理过的两颗二叉树从nodes删除nodes.remove(leftNode);nodes.remove(rightNode);// 将新的二叉树,接入到nodesnodes.add(parent);}// nodes最后的节点,就是赫夫曼树的根节点return nodes.get(0);}}//创建Node,带数据和权值
class Node implements Comparable<Node> {Byte data;// 存放数据(字符)本身,比如'a' => 97; ' ' => 32int weight;// 权值,表示字符出现的次数Node left;//Node right;public Node(Byte data, int weight) {this.data = data;this.weight = weight;}@Overridepublic int compareTo(Node o) {// 从小到大排序return this.weight - o.weight;}@Overridepublic String toString() {return "Node [data=" + data + ", weight=" + weight + "]";}// 前序遍历public void preOrder() {System.out.println(this);if (this.left != null) {this.left.preOrder();}if (this.right != null) {this.right.preOrder();}}}

运行结果:

在这里插入图片描述


赫夫曼编码字节数组的封装

代码实现:

package huffmancode;import java.util.ArrayList;
import java.util.Arrays;
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();System.out.println("原字符串的长度=" + contentBytes.length);// 40byte[] huffmanCodesBytes = huffmanZip(contentBytes);System.out.println("压缩后的结果是:" + Arrays.toString(huffmanCodesBytes) + "; 长度=" + huffmanCodesBytes.length);// 分步过程/** List<Node> nodes = getNodes(contentBytes); System.out.println("nodes = " +* nodes);* * // 测试,创建的二叉树 System.out.println("赫夫曼树"); Node huffmanTreeRoot =* createHuffmanTree(nodes); System.out.println("前序遍历");* huffmanTreeRoot.preOrder();* * // 测试是否生成了对应的赫夫曼编码 Map<Byte, String> huffmanCodes =* getCodes(huffmanTreeRoot); System.out.println("生成的赫夫曼编码表" + huffmanCodes);* * // 测试 byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);* System.out.println("huffmanCodeBytes=" + Arrays.toString(huffmanCodeBytes));*/}// 使用一个方法,将前面的方法封装起来,便于我们的调用/*** * @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;}// 编写一个方法,将字符串对应的byte[]数组,通过生成的赫夫曼编码表,返回一个护肤曼编码 压缩后的byte[]/*** * @param bytes        这是原始数组对应的byte[]* @param huffmanCodes 生成的赫夫曼编码map* @return 返回赫夫曼编码处理后的byte[] 举例:String content = "i like like like java do you*         like a java";-->byte[] contentBytes = content.getBytes(); 返回的是:101 01*         000 101 1111 1110 01 000 101 1111 1110 01 000 101 1111 1110 01 0010*         100 11011 100 01 11000 0011 01 11010 0011 11001 01 000 101 1111 1110*         01 100 01 0010 100 11011 100 -->对应的byte[] huffmanCodeBytes,*         即8位对应一个byte,放入到huffmanCodeBytes 其中,前8位对应的:huffmanCodeBytes[0] =*         10101000(补码)= 11011000 --> -88* */private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {// 1. 利用huffmanCodes 将bytes 转成赫夫曼编码对应的字符串StringBuilder stringBuilder = new StringBuilder();// 遍历bytes数组for (byte b : bytes) {stringBuilder.append(huffmanCodes.get(b));}System.out.println("测试stringBuilder=" + stringBuilder.toString());// 将"1010100010111..."转成byte[]// 统计返回的byte[] huffmanCodeBytes的长度// int len = (stringBuilder.length() + 7) / 8;int len;if (stringBuilder.length() % 8 == 0) {len = stringBuilder.length() / 8;} else {len = stringBuilder.length() / 8 + 1;}// 创建 存储压缩后的byte数组byte[] huffmanCodeBytes = new byte[len];int index = 0;// 记录是第几个bytefor (int i = 0; i < stringBuilder.length(); i += 8) {// 因为是每8位对应一个byte,所以步长 +8String strByte;if (i + 8 > stringBuilder.length()) {// 不够8位strByte = stringBuilder.substring(i);} else {strByte = stringBuilder.substring(i, i + 8);}// 将strByte 转成一个byte,放入到huffmanCodeByteshuffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);index++;}return huffmanCodeBytes;}// 生成赫夫曼树对应的赫夫曼编码表// 思路// 1. 将赫夫曼编码表存放在Map<Byte, String> 形式// 32->01 97->100 100->11000 等等[形式]static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();// 2. 在生成赫夫曼编码表示,需要去拼接路径,定义一个StringBuilder存储某个叶子结点的路径static StringBuilder stringBuilder = new StringBuilder();// 为了调用方便,重载getCodesprivate static Map<Byte, String> getCodes(Node root) {if (root == null) {return null;}// 处理root左子树getCodes(root.left, "0", stringBuilder);// 处理root右子树getCodes(root.right, "1", stringBuilder);return huffmanCodes;}/*** 功能:将传入的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);// 将code加入到stringBuilder2stringBuilder2.append(code);if (node != null) {// 如果node == null 不处理// 判断当前node是叶子结点还是非叶子节点if (node.data == null) {// 非叶子节点// 递归处理// 向左递归getCodes(node.left, "0", stringBuilder2);// 向右递归getCodes(node.right, "1", stringBuilder2);} else {// 说名明是一个叶子结点// 就表示找到了某一个叶子结点的最后huffmanCodes.put(node.data, stringBuilder2.toString());}}}// 前序遍历的方法private static void preOrder(Node root) {if (root != null) {root.preOrder();} else {System.out.println("赫夫曼树为空");}}/*** * @param bytes 接受一个字节数组* @return 返回的就是List形式: [Node[data=97 ,weight = 5], Node[data=32,weight = 9]…]*/private static List<Node> getNodes(byte[] bytes) {// 创建一个ArrayListArrayList<Node> nodes = new ArrayList<Node>();// 遍历bytes,统计每一个byte出现的次数->map[key, value]Map<Byte, Integer> counts = new HashMap<>();for (byte b : bytes) {Integer count = counts.get(b);if (count == null) {// Map还没有这个字符数据,第一次counts.put(b, 1);} else {counts.put(b, count + 1);}}// 把每个 键值对 转成一个Node对象,并加入到nodes集合// 遍历mapfor (Map.Entry<Byte, Integer> entry : counts.entrySet()) {nodes.add(new Node(entry.getKey(), entry.getValue()));}return nodes;}// 通过List创建对应的赫夫曼树private static Node createHuffmanTree(List<Node> nodes) {while (nodes.size() > 1) {// 排序,从小到大Collections.sort(nodes);// 取出第一个最小的二叉树Node leftNode = nodes.get(0);// 取出第二小的二叉树Node rightNode = nodes.get(1);// 创建一个新的二叉树,它的根节点:没有data,只有取值Node parent = new Node(null, leftNode.weight + rightNode.weight);parent.left = leftNode;parent.right = rightNode;// 将已经处理过的两颗二叉树从nodes删除nodes.remove(leftNode);nodes.remove(rightNode);// 将新的二叉树,接入到nodesnodes.add(parent);}// nodes最后的节点,就是赫夫曼树的根节点return nodes.get(0);}}//创建Node,带数据和权值
class Node implements Comparable<Node> {Byte data;// 存放数据(字符)本身,比如'a' => 97; ' ' => 32int weight;// 权值,表示字符出现的次数Node left;//Node right;public Node(Byte data, int weight) {this.data = data;this.weight = weight;}@Overridepublic int compareTo(Node o) {// 从小到大排序return this.weight - o.weight;}@Overridepublic String toString() {return "Node [data=" + data + ", weight=" + weight + "]";}// 前序遍历public void preOrder() {System.out.println(this);if (this.left != null) {this.left.preOrder();}if (this.right != null) {this.right.preOrder();}}}

运行结果:

在这里插入图片描述

3. 实例应用-赫夫曼编码实现数据解压

问题:
使用赫夫曼编码来解码数据,具体要求是
(1)前面我们得到了赫夫曼编码和对应的编码byte[] , 即:[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
(2)现在要求使用赫夫曼编码, 进行解码,又重新得到原来的字符串"i like like like java do you like a java"

思路:
解码过程,就是编码的一个逆向操作。

代码实现:

package huffmancode;import java.util.ArrayList;
import java.util.Arrays;
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();System.out.println("原字符串的长度=" + contentBytes.length);// 40byte[] huffmanCodesBytes = huffmanZip(contentBytes);System.out.println("压缩后的结果是:" + Arrays.toString(huffmanCodesBytes) + "; 长度=" + huffmanCodesBytes.length);// 测试:byteToBitString方法
//		System.out.println(byteToBitString((byte) 1));byte[] sourceBytes = decode(huffmanCodes, huffmanCodesBytes);System.out.println("原来的字符串=" + new String(sourceBytes));// 分步过程/** List<Node> nodes = getNodes(contentBytes); System.out.println("nodes = " +* nodes);* * // 测试,创建的二叉树 System.out.println("赫夫曼树"); Node huffmanTreeRoot =* createHuffmanTree(nodes); System.out.println("前序遍历");* huffmanTreeRoot.preOrder();* * // 测试是否生成了对应的赫夫曼编码 Map<Byte, String> huffmanCodes =* getCodes(huffmanTreeRoot); System.out.println("生成的赫夫曼编码表" + huffmanCodes);* * // 测试 byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);* System.out.println("huffmanCodeBytes=" + Arrays.toString(huffmanCodeBytes));*/}// 完成数据的解压// 思路:// 1. 将huffmanCodesBytes:[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24,// -14, -117, -4, -60, -90, 28]// 重写,先转成 赫夫曼编码对应的二进制的字符串"10101000101111..."// 2. 赫夫曼编码对应的二进制的字符串"10101000101111..." --> 对照 赫夫曼编码 --> "i like like like java// do you like a java"// 编写一个方法,完成对压缩数据的解码/*** * @param huffmanCodes 赫夫曼编码表map* @param huffmanBytes 赫夫曼编码得到的字节数组* @return 就是原来字符串对应的数组*/private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {// 1. 先得到huffmanBytes对应的 二进制的字符串,形式:10101000101111...StringBuilder stringBuilder = new StringBuilder();// 将byte数组转成二进制的字符串for (int i = 0; i < huffmanBytes.length; i++) {byte b = huffmanBytes[i];// 判断是不是最后一个字节boolean flag = (i == huffmanBytes.length - 1);stringBuilder.append(byteToBitString(!flag, b));}System.out.println("赫夫曼字节数组对应的二进制字符串=" + stringBuilder.toString());// 把字符串按照指定的赫夫曼编码进行解码// 把赫夫曼编码表进行调换,因为反向查询 a->100 100->aMap<String, Byte> map = new HashMap<String, Byte>();for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {map.put(entry.getValue(), entry.getKey());}System.out.println("map=" + map);// 创建一个集合,存放byteList<Byte> list = new ArrayList<>();// i 可以理解成就是索引,扫描stringBuilderfor (int i = 0; i < stringBuilder.length();) {int count = 1;// 小的计数器boolean flag = true;Byte b = null;while (flag) {// 10101000101111...// 递增的取出key 1或0String key = stringBuilder.substring(i, i + count);// i不动,让count移动,指定匹配到一个字符b = map.get(key);if (b == null) {// 说明没有匹配到count++;} else {// 匹配到flag = false;}}list.add(b);i += count;// i 直接移动到count}// 当for循环结束后,list中就存放了所有的字符// 把list中的数据放到byte[]数组 并返回byte b[] = new byte[list.size()];for (int i = 0; i < b.length; i++) {b[i] = list.get(i);}return b;}/*** 功能: 将一个byte转成一个二进制的字符串* * @param b    传入byte* @param flag 标志是否需要补高位:如果是true,表示需要补高位;如果是false,表示不补高位;如果是最后一个字节,无需补高位* @return 是该b 对应的二进制的字符串(注意:是按补码返回)*/private static String byteToBitString(boolean flag, byte b) {// 使用变量保存bint temp = b;// 将b转成int// 如果是正数,需要补高位if (flag) {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;}}// 使用一个方法,将前面的方法封装起来,便于我们的调用/*** * @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;}// 编写一个方法,将字符串对应的byte[]数组,通过生成的赫夫曼编码表,返回一个护肤曼编码 压缩后的byte[]/*** * @param bytes        这是原始数组对应的byte[]* @param huffmanCodes 生成的赫夫曼编码map* @return 返回赫夫曼编码处理后的byte[] 举例:String content = "i like like like java do you*         like a java";-->byte[] contentBytes = content.getBytes(); 返回的是:101 01*         000 101 1111 1110 01 000 101 1111 1110 01 000 101 1111 1110 01 0010*         100 11011 100 01 11000 0011 01 11010 0011 11001 01 000 101 1111 1110*         01 100 01 0010 100 11011 100 -->对应的byte[] huffmanCodeBytes,*         即8位对应一个byte,放入到huffmanCodeBytes 其中,前8位对应的:huffmanCodeBytes[0] =*         10101000(补码)= 11011000 --> -88* */private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {// 1. 利用huffmanCodes 将bytes 转成赫夫曼编码对应的字符串StringBuilder stringBuilder = new StringBuilder();// 遍历bytes数组for (byte b : bytes) {stringBuilder.append(huffmanCodes.get(b));}System.out.println("测试stringBuilder=" + stringBuilder.toString());// 将"1010100010111..."转成byte[]// 统计返回的byte[] huffmanCodeBytes的长度// int len = (stringBuilder.length() + 7) / 8;int len;if (stringBuilder.length() % 8 == 0) {len = stringBuilder.length() / 8;} else {len = stringBuilder.length() / 8 + 1;}// 创建 存储压缩后的byte数组byte[] huffmanCodeBytes = new byte[len];int index = 0;// 记录是第几个bytefor (int i = 0; i < stringBuilder.length(); i += 8) {// 因为是每8位对应一个byte,所以步长 +8String strByte;if (i + 8 > stringBuilder.length()) {// 不够8位strByte = stringBuilder.substring(i);} else {strByte = stringBuilder.substring(i, i + 8);}// 将strByte 转成一个byte,放入到huffmanCodeByteshuffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);index++;}return huffmanCodeBytes;}// 生成赫夫曼树对应的赫夫曼编码表// 思路// 1. 将赫夫曼编码表存放在Map<Byte, String> 形式// 32->01 97->100 100->11000 等等[形式]static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();// 2. 在生成赫夫曼编码表示,需要去拼接路径,定义一个StringBuilder存储某个叶子结点的路径static StringBuilder stringBuilder = new StringBuilder();// 为了调用方便,重载getCodesprivate static Map<Byte, String> getCodes(Node root) {if (root == null) {return null;}// 处理root左子树getCodes(root.left, "0", stringBuilder);// 处理root右子树getCodes(root.right, "1", stringBuilder);return huffmanCodes;}/*** 功能:将传入的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);// 将code加入到stringBuilder2stringBuilder2.append(code);if (node != null) {// 如果node == null 不处理// 判断当前node是叶子结点还是非叶子节点if (node.data == null) {// 非叶子节点// 递归处理// 向左递归getCodes(node.left, "0", stringBuilder2);// 向右递归getCodes(node.right, "1", stringBuilder2);} else {// 说名明是一个叶子结点// 就表示找到了某一个叶子结点的最后huffmanCodes.put(node.data, stringBuilder2.toString());}}}// 前序遍历的方法private static void preOrder(Node root) {if (root != null) {root.preOrder();} else {System.out.println("赫夫曼树为空");}}/*** * @param bytes 接受一个字节数组* @return 返回的就是List形式: [Node[data=97 ,weight = 5], Node[data=32,weight = 9]…]*/private static List<Node> getNodes(byte[] bytes) {// 创建一个ArrayListArrayList<Node> nodes = new ArrayList<Node>();// 遍历bytes,统计每一个byte出现的次数->map[key, value]Map<Byte, Integer> counts = new HashMap<>();for (byte b : bytes) {Integer count = counts.get(b);if (count == null) {// Map还没有这个字符数据,第一次counts.put(b, 1);} else {counts.put(b, count + 1);}}// 把每个 键值对 转成一个Node对象,并加入到nodes集合// 遍历mapfor (Map.Entry<Byte, Integer> entry : counts.entrySet()) {nodes.add(new Node(entry.getKey(), entry.getValue()));}return nodes;}// 通过List创建对应的赫夫曼树private static Node createHuffmanTree(List<Node> nodes) {while (nodes.size() > 1) {// 排序,从小到大Collections.sort(nodes);// 取出第一个最小的二叉树Node leftNode = nodes.get(0);// 取出第二小的二叉树Node rightNode = nodes.get(1);// 创建一个新的二叉树,它的根节点:没有data,只有取值Node parent = new Node(null, leftNode.weight + rightNode.weight);parent.left = leftNode;parent.right = rightNode;// 将已经处理过的两颗二叉树从nodes删除nodes.remove(leftNode);nodes.remove(rightNode);// 将新的二叉树,接入到nodesnodes.add(parent);}// nodes最后的节点,就是赫夫曼树的根节点return nodes.get(0);}}//创建Node,带数据和权值
class Node implements Comparable<Node> {Byte data;// 存放数据(字符)本身,比如'a' => 97; ' ' => 32int weight;// 权值,表示字符出现的次数Node left;//Node right;public Node(Byte data, int weight) {this.data = data;this.weight = weight;}@Overridepublic int compareTo(Node o) {// 从小到大排序return this.weight - o.weight;}@Overridepublic String toString() {return "Node [data=" + data + ", weight=" + weight + "]";}// 前序遍历public void preOrder() {System.out.println(this);if (this.left != null) {this.left.preOrder();}if (this.right != null) {this.right.preOrder();}}}

运行结果:

在这里插入图片描述

4. 实例应用-使用赫夫曼编码压缩文件

4.1. 压缩文件

问题:
    我们学习了通过赫夫曼编码对一个字符串进行编码和解码, 下面我们来完成对文件的压缩和解压, 具体要求:给你一个图片文件,要求对其进行无损压缩, 看看压缩效果如何。

思路:读取文件-> 得到赫夫曼编码表 -> 完成压缩

代码实现:

package huffmancode;import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Arrays;
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 srcFile = "C://Users//14532//Desktop//demo.png";String dstFile = "C://Users//14532//Desktop//dst.zip";zipFile(srcFile, dstFile);System.out.println("压缩文件ok~");}// 编写方法,将一个文件压缩/*** * @param srcFile 传入的希望压缩的文件的全路径* @param dstFile 压缩后将压缩文件放到哪个目录*/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);// 创建一个和文件输出流关联的ObjectOutputStreamoos = new ObjectOutputStream(os);// 把oos.writeObject(huffmanBytes);// 先把// 这里我们以对象流的方式写入赫夫曼编码,是为了以后恢复源文件时使用// 注意一定要把赫夫曼编码写入压缩文件oos.writeObject(huffmanCodes);} catch (Exception e) {// TODO: handle exceptionSystem.out.println(e.getMessage());} finally {try {is.close();oos.close();os.close();} catch (Exception e) {// TODO: handle exceptionSystem.out.println(e.getMessage());}}}// 完成数据的解压// 思路:// 1. 将huffmanCodesBytes:[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24,// -14, -117, -4, -60, -90, 28]// 重写,先转成 赫夫曼编码对应的二进制的字符串"10101000101111..."// 2. 赫夫曼编码对应的二进制的字符串"10101000101111..." --> 对照 赫夫曼编码 --> "i like like like java// do you like a java"// 编写一个方法,完成对压缩数据的解码/*** * @param huffmanCodes 赫夫曼编码表map* @param huffmanBytes 赫夫曼编码得到的字节数组* @return 就是原来字符串对应的数组*/private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {// 1. 先得到huffmanBytes对应的 二进制的字符串,形式:10101000101111...StringBuilder stringBuilder = new StringBuilder();// 将byte数组转成二进制的字符串for (int i = 0; i < huffmanBytes.length; i++) {byte b = huffmanBytes[i];// 判断是不是最后一个字节boolean flag = (i == huffmanBytes.length - 1);stringBuilder.append(byteToBitString(!flag, b));}
//		System.out.println("赫夫曼字节数组对应的二进制字符串=" + stringBuilder.toString());// 把字符串按照指定的赫夫曼编码进行解码// 把赫夫曼编码表进行调换,因为反向查询 a->100 100->aMap<String, Byte> map = new HashMap<String, Byte>();for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {map.put(entry.getValue(), entry.getKey());}//		System.out.println("map=" + map);// 创建一个集合,存放byteList<Byte> list = new ArrayList<>();// i 可以理解成就是索引,扫描stringBuilderfor (int i = 0; i < stringBuilder.length();) {int count = 1;// 小的计数器boolean flag = true;Byte b = null;while (flag) {// 10101000101111...// 递增的取出key 1或0String key = stringBuilder.substring(i, i + count);// i不动,让count移动,指定匹配到一个字符b = map.get(key);if (b == null) {// 说明没有匹配到count++;} else {// 匹配到flag = false;}}list.add(b);i += count;// i 直接移动到count}// 当for循环结束后,list中就存放了所有的字符// 把list中的数据放到byte[]数组 并返回byte b[] = new byte[list.size()];for (int i = 0; i < b.length; i++) {b[i] = list.get(i);}return b;}/*** 功能: 将一个byte转成一个二进制的字符串* * @param b    传入byte* @param flag 标志是否需要补高位:如果是true,表示需要补高位;如果是false,表示不补高位;如果是最后一个字节,无需补高位* @return 是该b 对应的二进制的字符串(注意:是按补码返回)*/private static String byteToBitString(boolean flag, byte b) {// 使用变量保存bint temp = b;// 将b转成int// 如果是正数,需要补高位if (flag) {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;}}// 使用一个方法,将前面的方法封装起来,便于我们的调用/*** * @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;}// 编写一个方法,将字符串对应的byte[]数组,通过生成的赫夫曼编码表,返回一个护肤曼编码 压缩后的byte[]/*** * @param bytes        这是原始数组对应的byte[]* @param huffmanCodes 生成的赫夫曼编码map* @return 返回赫夫曼编码处理后的byte[] 举例:String content = "i like like like java do you*         like a java";-->byte[] contentBytes = content.getBytes(); 返回的是:101 01*         000 101 1111 1110 01 000 101 1111 1110 01 000 101 1111 1110 01 0010*         100 11011 100 01 11000 0011 01 11010 0011 11001 01 000 101 1111 1110*         01 100 01 0010 100 11011 100 -->对应的byte[] huffmanCodeBytes,*         即8位对应一个byte,放入到huffmanCodeBytes 其中,前8位对应的:huffmanCodeBytes[0] =*         10101000(补码)= 11011000 --> -88* */private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {// 1. 利用huffmanCodes 将bytes 转成赫夫曼编码对应的字符串StringBuilder stringBuilder = new StringBuilder();// 遍历bytes数组for (byte b : bytes) {stringBuilder.append(huffmanCodes.get(b));}//		System.out.println("测试stringBuilder=" + stringBuilder.toString());// 将"1010100010111..."转成byte[]// 统计返回的byte[] huffmanCodeBytes的长度// int len = (stringBuilder.length() + 7) / 8;int len;if (stringBuilder.length() % 8 == 0) {len = stringBuilder.length() / 8;} else {len = stringBuilder.length() / 8 + 1;}// 创建 存储压缩后的byte数组byte[] huffmanCodeBytes = new byte[len];int index = 0;// 记录是第几个bytefor (int i = 0; i < stringBuilder.length(); i += 8) {// 因为是每8位对应一个byte,所以步长 +8String strByte;if (i + 8 > stringBuilder.length()) {// 不够8位strByte = stringBuilder.substring(i);} else {strByte = stringBuilder.substring(i, i + 8);}// 将strByte 转成一个byte,放入到huffmanCodeByteshuffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);index++;}return huffmanCodeBytes;}// 生成赫夫曼树对应的赫夫曼编码表// 思路// 1. 将赫夫曼编码表存放在Map<Byte, String> 形式// 32->01 97->100 100->11000 等等[形式]static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();// 2. 在生成赫夫曼编码表示,需要去拼接路径,定义一个StringBuilder存储某个叶子结点的路径static StringBuilder stringBuilder = new StringBuilder();// 为了调用方便,重载getCodesprivate static Map<Byte, String> getCodes(Node root) {if (root == null) {return null;}// 处理root左子树getCodes(root.left, "0", stringBuilder);// 处理root右子树getCodes(root.right, "1", stringBuilder);return huffmanCodes;}/*** 功能:将传入的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);// 将code加入到stringBuilder2stringBuilder2.append(code);if (node != null) {// 如果node == null 不处理// 判断当前node是叶子结点还是非叶子节点if (node.data == null) {// 非叶子节点// 递归处理// 向左递归getCodes(node.left, "0", stringBuilder2);// 向右递归getCodes(node.right, "1", stringBuilder2);} else {// 说名明是一个叶子结点// 就表示找到了某一个叶子结点的最后huffmanCodes.put(node.data, stringBuilder2.toString());}}}// 前序遍历的方法private static void preOrder(Node root) {if (root != null) {root.preOrder();} else {System.out.println("赫夫曼树为空");}}/*** * @param bytes 接受一个字节数组* @return 返回的就是List形式: [Node[data=97 ,weight = 5], Node[data=32,weight = 9]…]*/private static List<Node> getNodes(byte[] bytes) {// 创建一个ArrayListArrayList<Node> nodes = new ArrayList<Node>();// 遍历bytes,统计每一个byte出现的次数->map[key, value]Map<Byte, Integer> counts = new HashMap<>();for (byte b : bytes) {Integer count = counts.get(b);if (count == null) {// Map还没有这个字符数据,第一次counts.put(b, 1);} else {counts.put(b, count + 1);}}// 把每个 键值对 转成一个Node对象,并加入到nodes集合// 遍历mapfor (Map.Entry<Byte, Integer> entry : counts.entrySet()) {nodes.add(new Node(entry.getKey(), entry.getValue()));}return nodes;}// 通过List创建对应的赫夫曼树private static Node createHuffmanTree(List<Node> nodes) {while (nodes.size() > 1) {// 排序,从小到大Collections.sort(nodes);// 取出第一个最小的二叉树Node leftNode = nodes.get(0);// 取出第二小的二叉树Node rightNode = nodes.get(1);// 创建一个新的二叉树,它的根节点:没有data,只有取值Node parent = new Node(null, leftNode.weight + rightNode.weight);parent.left = leftNode;parent.right = rightNode;// 将已经处理过的两颗二叉树从nodes删除nodes.remove(leftNode);nodes.remove(rightNode);// 将新的二叉树,接入到nodesnodes.add(parent);}// nodes最后的节点,就是赫夫曼树的根节点return nodes.get(0);}}//创建Node,带数据和权值
class Node implements Comparable<Node> {Byte data;// 存放数据(字符)本身,比如'a' => 97; ' ' => 32int weight;// 权值,表示字符出现的次数Node left;//Node right;public Node(Byte data, int weight) {this.data = data;this.weight = weight;}@Overridepublic int compareTo(Node o) {// 从小到大排序return this.weight - o.weight;}@Overridepublic String toString() {return "Node [data=" + data + ", weight=" + weight + "]";}// 前序遍历public void preOrder() {System.out.println(this);if (this.left != null) {this.left.preOrder();}if (this.right != null) {this.right.preOrder();}}}

运行结果:

在这里插入图片描述
在桌面会看到dxt.zip压缩文件

在这里插入图片描述

4.2. 解压文件

具体要求:将前面压缩的文件,重新恢复成原来的文件。

思路:读取压缩文件(数据和赫夫曼编码表)-> 完成解压(文件恢复)

代码实现:

package huffmancode;import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Arrays;
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 srcFile = "C://Users//14532//Desktop//demo.png";
//		String dstFile = "C://Users//14532//Desktop//dst.zip";
//
//		zipFile(srcFile, dstFile);
//		System.out.println("压缩文件ok~");// 测试解压文件String zipFile = "C://Users//14532//Desktop//dst.zip";String dstFile = "C://Users//14532//Desktop//demo2.png";unZipFile(zipFile, dstFile);System.out.println("解压成功~");}// 编写方法:完成对压缩文件的解压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数组 huffmanBytesbyte[] huffmanBytes = (byte[]) ois.readObject();// 读取赫夫曼编码表Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();// 解码byte[] bytes = decode(huffmanCodes, huffmanBytes);// 将bytes[]写入到目标文件os = new FileOutputStream(dstFile);// 写数据到dsFile文件中os.write(bytes);} catch (Exception e) {// TODO: handle exceptionSystem.out.println(e.getMessage());} finally {try {os.close();ois.close();is.close();} catch (Exception e2) {System.out.println(e2.getMessage());}}}// 编写方法,将一个文件压缩/*** * @param srcFile 传入的希望压缩的文件的全路径* @param dstFile 压缩后将压缩文件放到哪个路径*/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);// 创建一个和文件输出流关联的ObjectOutputStreamoos = new ObjectOutputStream(os);// 把oos.writeObject(huffmanBytes);// 先把// 这里我们以对象流的方式写入赫夫曼编码,是为了以后恢复源文件时使用// 注意一定要把赫夫曼编码写入压缩文件oos.writeObject(huffmanCodes);} catch (Exception e) {// TODO: handle exceptionSystem.out.println(e.getMessage());} finally {try {is.close();oos.close();os.close();} catch (Exception e) {// TODO: handle exceptionSystem.out.println(e.getMessage());}}}// 完成数据的解压// 思路:// 1. 将huffmanCodesBytes:[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24,// -14, -117, -4, -60, -90, 28]// 重写,先转成 赫夫曼编码对应的二进制的字符串"10101000101111..."// 2. 赫夫曼编码对应的二进制的字符串"10101000101111..." --> 对照 赫夫曼编码 --> "i like like like java// do you like a java"// 编写一个方法,完成对压缩数据的解码/*** * @param huffmanCodes 赫夫曼编码表map* @param huffmanBytes 赫夫曼编码得到的字节数组* @return 就是原来字符串对应的数组*/private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {// 1. 先得到huffmanBytes对应的 二进制的字符串,形式:10101000101111...StringBuilder stringBuilder = new StringBuilder();// 将byte数组转成二进制的字符串for (int i = 0; i < huffmanBytes.length; i++) {byte b = huffmanBytes[i];// 判断是不是最后一个字节boolean flag = (i == huffmanBytes.length - 1);stringBuilder.append(byteToBitString(!flag, b));}
//		System.out.println("赫夫曼字节数组对应的二进制字符串=" + stringBuilder.toString());// 把字符串按照指定的赫夫曼编码进行解码// 把赫夫曼编码表进行调换,因为反向查询 a->100 100->aMap<String, Byte> map = new HashMap<String, Byte>();for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {map.put(entry.getValue(), entry.getKey());}//		System.out.println("map=" + map);// 创建一个集合,存放byteList<Byte> list = new ArrayList<>();// i 可以理解成就是索引,扫描stringBuilderfor (int i = 0; i < stringBuilder.length();) {int count = 1;// 小的计数器boolean flag = true;Byte b = null;while (flag) {// 10101000101111...// 递增的取出key 1或0String key = stringBuilder.substring(i, i + count);// i不动,让count移动,指定匹配到一个字符b = map.get(key);if (b == null) {// 说明没有匹配到count++;} else {// 匹配到flag = false;}}list.add(b);i += count;// i 直接移动到count}// 当for循环结束后,list中就存放了所有的字符// 把list中的数据放到byte[]数组 并返回byte b[] = new byte[list.size()];for (int i = 0; i < b.length; i++) {b[i] = list.get(i);}return b;}/*** 功能: 将一个byte转成一个二进制的字符串* * @param b    传入byte* @param flag 标志是否需要补高位:如果是true,表示需要补高位;如果是false,表示不补高位;如果是最后一个字节,无需补高位* @return 是该b 对应的二进制的字符串(注意:是按补码返回)*/private static String byteToBitString(boolean flag, byte b) {// 使用变量保存bint temp = b;// 将b转成int// 如果是正数,需要补高位if (flag) {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;}}// 使用一个方法,将前面的方法封装起来,便于我们的调用/*** * @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;}// 编写一个方法,将字符串对应的byte[]数组,通过生成的赫夫曼编码表,返回一个护肤曼编码 压缩后的byte[]/*** * @param bytes        这是原始数组对应的byte[]* @param huffmanCodes 生成的赫夫曼编码map* @return 返回赫夫曼编码处理后的byte[] 举例:String content = "i like like like java do you*         like a java";-->byte[] contentBytes = content.getBytes(); 返回的是:101 01*         000 101 1111 1110 01 000 101 1111 1110 01 000 101 1111 1110 01 0010*         100 11011 100 01 11000 0011 01 11010 0011 11001 01 000 101 1111 1110*         01 100 01 0010 100 11011 100 -->对应的byte[] huffmanCodeBytes,*         即8位对应一个byte,放入到huffmanCodeBytes 其中,前8位对应的:huffmanCodeBytes[0] =*         10101000(补码)= 11011000 --> -88* */private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {// 1. 利用huffmanCodes 将bytes 转成赫夫曼编码对应的字符串StringBuilder stringBuilder = new StringBuilder();// 遍历bytes数组for (byte b : bytes) {stringBuilder.append(huffmanCodes.get(b));}//		System.out.println("测试stringBuilder=" + stringBuilder.toString());// 将"1010100010111..."转成byte[]// 统计返回的byte[] huffmanCodeBytes的长度// int len = (stringBuilder.length() + 7) / 8;int len;if (stringBuilder.length() % 8 == 0) {len = stringBuilder.length() / 8;} else {len = stringBuilder.length() / 8 + 1;}// 创建 存储压缩后的byte数组byte[] huffmanCodeBytes = new byte[len];int index = 0;// 记录是第几个bytefor (int i = 0; i < stringBuilder.length(); i += 8) {// 因为是每8位对应一个byte,所以步长 +8String strByte;if (i + 8 > stringBuilder.length()) {// 不够8位strByte = stringBuilder.substring(i);} else {strByte = stringBuilder.substring(i, i + 8);}// 将strByte 转成一个byte,放入到huffmanCodeByteshuffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);index++;}return huffmanCodeBytes;}// 生成赫夫曼树对应的赫夫曼编码表// 思路// 1. 将赫夫曼编码表存放在Map<Byte, String> 形式// 32->01 97->100 100->11000 等等[形式]static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();// 2. 在生成赫夫曼编码表示,需要去拼接路径,定义一个StringBuilder存储某个叶子结点的路径static StringBuilder stringBuilder = new StringBuilder();// 为了调用方便,重载getCodesprivate static Map<Byte, String> getCodes(Node root) {if (root == null) {return null;}// 处理root左子树getCodes(root.left, "0", stringBuilder);// 处理root右子树getCodes(root.right, "1", stringBuilder);return huffmanCodes;}/*** 功能:将传入的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);// 将code加入到stringBuilder2stringBuilder2.append(code);if (node != null) {// 如果node == null 不处理// 判断当前node是叶子结点还是非叶子节点if (node.data == null) {// 非叶子节点// 递归处理// 向左递归getCodes(node.left, "0", stringBuilder2);// 向右递归getCodes(node.right, "1", stringBuilder2);} else {// 说名明是一个叶子结点// 就表示找到了某一个叶子结点的最后huffmanCodes.put(node.data, stringBuilder2.toString());}}}// 前序遍历的方法private static void preOrder(Node root) {if (root != null) {root.preOrder();} else {System.out.println("赫夫曼树为空");}}/*** * @param bytes 接受一个字节数组* @return 返回的就是List形式: [Node[data=97 ,weight = 5], Node[data=32,weight = 9]…]*/private static List<Node> getNodes(byte[] bytes) {// 创建一个ArrayListArrayList<Node> nodes = new ArrayList<Node>();// 遍历bytes,统计每一个byte出现的次数->map[key, value]Map<Byte, Integer> counts = new HashMap<>();for (byte b : bytes) {Integer count = counts.get(b);if (count == null) {// Map还没有这个字符数据,第一次counts.put(b, 1);} else {counts.put(b, count + 1);}}// 把每个 键值对 转成一个Node对象,并加入到nodes集合// 遍历mapfor (Map.Entry<Byte, Integer> entry : counts.entrySet()) {nodes.add(new Node(entry.getKey(), entry.getValue()));}return nodes;}// 通过List创建对应的赫夫曼树private static Node createHuffmanTree(List<Node> nodes) {while (nodes.size() > 1) {// 排序,从小到大Collections.sort(nodes);// 取出第一个最小的二叉树Node leftNode = nodes.get(0);// 取出第二小的二叉树Node rightNode = nodes.get(1);// 创建一个新的二叉树,它的根节点:没有data,只有取值Node parent = new Node(null, leftNode.weight + rightNode.weight);parent.left = leftNode;parent.right = rightNode;// 将已经处理过的两颗二叉树从nodes删除nodes.remove(leftNode);nodes.remove(rightNode);// 将新的二叉树,接入到nodesnodes.add(parent);}// nodes最后的节点,就是赫夫曼树的根节点return nodes.get(0);}}//创建Node,带数据和权值
class Node implements Comparable<Node> {Byte data;// 存放数据(字符)本身,比如'a' => 97; ' ' => 32int weight;// 权值,表示字符出现的次数Node left;//Node right;public Node(Byte data, int weight) {this.data = data;this.weight = weight;}@Overridepublic int compareTo(Node o) {// 从小到大排序return this.weight - o.weight;}@Overridepublic String toString() {return "Node [data=" + data + ", weight=" + weight + "]";}// 前序遍历public void preOrder() {System.out.println(this);if (this.left != null) {this.left.preOrder();}if (this.right != null) {this.right.preOrder();}}}

运行结果:

在这里插入图片描述

在桌面会看到dxt.zip压缩文件

在这里插入图片描述

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

  1. 如果文件本身就是经过压缩处理的,那么使用赫夫曼编码再压缩效率不会有明显变化, 比如视频,ppt 等等文件(我上面使用的png图片就没有明显变化,压缩之后数据量反而变大了)
  2. 赫夫曼编码是按字节来处理的,因此可以处理所有的文件(二进制文件、文本文件)
  3. 如果一个文件中的内容,重复的数据不多,压缩效果也不会很明显。

想获得明显的压缩效果,给一个bmp图片,供大家进行测试,如下

在这里插入图片描述

这篇关于【数据结构(十·树结构的实际应用)】赫夫曼编码(3)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/483197

相关文章

在Ubuntu上部署SpringBoot应用的操作步骤

《在Ubuntu上部署SpringBoot应用的操作步骤》随着云计算和容器化技术的普及,Linux服务器已成为部署Web应用程序的主流平台之一,Java作为一种跨平台的编程语言,具有广泛的应用场景,本... 目录一、部署准备二、安装 Java 环境1. 安装 JDK2. 验证 Java 安装三、安装 mys

Python中构建终端应用界面利器Blessed模块的使用

《Python中构建终端应用界面利器Blessed模块的使用》Blessed库作为一个轻量级且功能强大的解决方案,开始在开发者中赢得口碑,今天,我们就一起来探索一下它是如何让终端UI开发变得轻松而高... 目录一、安装与配置:简单、快速、无障碍二、基本功能:从彩色文本到动态交互1. 显示基本内容2. 创建链

Node.js 中 http 模块的深度剖析与实战应用小结

《Node.js中http模块的深度剖析与实战应用小结》本文详细介绍了Node.js中的http模块,从创建HTTP服务器、处理请求与响应,到获取请求参数,每个环节都通过代码示例进行解析,旨在帮... 目录Node.js 中 http 模块的深度剖析与实战应用一、引言二、创建 HTTP 服务器:基石搭建(一

Android数据库Room的实际使用过程总结

《Android数据库Room的实际使用过程总结》这篇文章主要给大家介绍了关于Android数据库Room的实际使用过程,详细介绍了如何创建实体类、数据访问对象(DAO)和数据库抽象类,需要的朋友可以... 目录前言一、Room的基本使用1.项目配置2.创建实体类(Entity)3.创建数据访问对象(DAO

java中VO PO DTO POJO BO DO对象的应用场景及使用方式

《java中VOPODTOPOJOBODO对象的应用场景及使用方式》文章介绍了Java开发中常用的几种对象类型及其应用场景,包括VO、PO、DTO、POJO、BO和DO等,并通过示例说明了它... 目录Java中VO PO DTO POJO BO DO对象的应用VO (View Object) - 视图对象

Go信号处理如何优雅地关闭你的应用

《Go信号处理如何优雅地关闭你的应用》Go中的优雅关闭机制使得在应用程序接收到终止信号时,能够进行平滑的资源清理,通过使用context来管理goroutine的生命周期,结合signal... 目录1. 什么是信号处理?2. 如何优雅地关闭 Go 应用?3. 代码实现3.1 基本的信号捕获和优雅关闭3.2

正则表达式高级应用与性能优化记录

《正则表达式高级应用与性能优化记录》本文介绍了正则表达式的高级应用和性能优化技巧,包括文本拆分、合并、XML/HTML解析、数据分析、以及性能优化方法,通过这些技巧,可以更高效地利用正则表达式进行复杂... 目录第6章:正则表达式的高级应用6.1 模式匹配与文本处理6.1.1 文本拆分6.1.2 文本合并6

python中的与时间相关的模块应用场景分析

《python中的与时间相关的模块应用场景分析》本文介绍了Python中与时间相关的几个重要模块:`time`、`datetime`、`calendar`、`timeit`、`pytz`和`dateu... 目录1. time 模块2. datetime 模块3. calendar 模块4. timeit

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

水位雨量在线监测系统概述及应用介绍

在当今社会,随着科技的飞速发展,各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中,水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术,其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成,形成了一个完整的闭环系统。 数据采集单元:这是系统的“眼睛”,