字节转二进制字符串
// 完成数据的解压// 思路// 1 将huffmanCodeBytes [40, 46, -56, 46, -56, 46, -55, 5, -123, 6, -88, -46, -126, -20, -124, -126, 24 ]// 重新转成赫夫曼编码对应的字符串 100100100...// 2 将赫夫曼对应的二进制字符串 100100100... 对照 哈夫曼编码转成 i like java....../*** 将byte 转成一个二进制的字符串* @param flag 标志当前是否需要补高位 如果是true 需要补高位* @param b 传入的byte* @return 返回 b 对应二进制的字符串(补码返回)*/private static String byteToBitString(boolean flag,byte b){int temp = b; // 向上强转 b变成int// 如果是整数 需要补高位if(flag) { // 如果当前长度 没有8位 不用高位补码temp |= 256; // 按位与 256 =1 0000 0000 1 = 0000 0001 => 1 0000 0001}String str = Integer.toBinaryString(temp); // 返回temp 对应二进制的补码if (flag) {return str.substring(str.length() - 8); // 取最后8位}else {return str;}}数据解压——赫夫曼解码
/*** 编写有个方法 完成对压缩数据的编码* @param huffmanCode 哈夫曼编码表* @param huffmanBytes 哈夫曼编码的得到的字节数组* @return 原来的字符串对应的数组*/private static byte[] decode(Map<Byte,String> huffmanCode, byte[] huffmanBytes){// 1 先得到 huffmanBytes 的二进制的字符串 形式为"10101010..."StringBuilder stringBuilder = new StringBuilder();// 将byte数组转成二进制的字符串boolean flag = false;for(int i = 0; i < huffmanBytes.length; i++){// 判断是不是最后一个字节if (huffmanBytes.length-1 == i){flag = true;}stringBuilder.append(byteToBitString(!flag,huffmanBytes[i]));//拿到二进制字符串}// System.out.println("哈弗曼树对应的二进制字符串是 "+stringBuilder.toString());// 把字符串安装到指定的哈夫曼编码进行解码// 把哈夫曼树编码进行调换 因为反向查询 a -> 100 100->aMap<String, Byte> map = new HashMap<>();for (Map.Entry<Byte,String> entry : huffmanCode.entrySet()){map.put(entry.getValue(), entry.getKey());}//System.out.println(map);//创键一个集合 存放byteList<Byte> list = new ArrayList<>();// i理解成是一个索引 扫描stringBuilderfor (int i = 0; i < stringBuilder.length();){int count = 1; // 小的计数器flag = true;Byte b = null;while (flag) {// 取出一个'1'或'0' 组建key 去map{000=108, 01=32, 001=105, 01000=100, 01011=118...中查找String key = stringBuilder.substring(i, i + count);// i 不动 让count移动// 直到匹配到一个字符b = map.get(key);if (b == null) {count++;} else {//匹配到了flag = false;}}list.add(b); 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;}测试
package huffmancode;import java.nio.charset.StandardCharsets;
import java.util.*;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(StandardCharsets.UTF_8);System.out.println(contentBytes.length);//40byte[] huffmanCodesBytes = huffmanZip(contentBytes);System.out.println("压缩后的结果是:"+Arrays.toString(huffmanCodesBytes)+"长度="+huffmanCodesBytes.length);byte[] sourceBytes = decode(huffmanCode, 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));//17个//发送huffmanCodeBytes 数组*/// 完成数据的解压// 思路// 1 将huffmanCodeBytes [40, 46, -56, 46, -56, 46, -55, 5, -123, 6, -88, -46, -126, -20, -124, -126, 24 ]// 重新转成赫夫曼编码对应的字符串 100100100...// 2 将赫夫曼对应的二进制字符串 100100100... 对照 哈夫曼编码转成 i like java....../*** 将byte 转成一个二进制的字符串* @param flag 标志当前是否需要补高位 如果是true 需要补高位* @param b 传入的byte* @return 返回 b 对应二进制的字符串(补码返回)*/private static String byteToBitString(boolean flag,byte b){int temp = b; // 向上强转 b变成int// 如果是整数 需要补高位if(flag) { // 如果当前长度 没有8位 不用高位补码temp |= 256; // 按位与 256 =1 0000 0000 1 = 0000 0001 => 1 0000 0001}String str = Integer.toBinaryString(temp); // 返回temp 对应二进制的补码if (flag) {return str.substring(str.length() - 8); // 取最后8位}else {return str;}}/*** 编写有个方法 完成对压缩数据的编码* @param huffmanCode 哈夫曼编码表* @param huffmanBytes 哈夫曼编码的得到的字节数组* @return 原来的字符串对应的数组*/private static byte[] decode(Map<Byte,String> huffmanCode, byte[] huffmanBytes){// 1 先得到 huffmanBytes 的二进制的字符串 形式为"10101010..."StringBuilder stringBuilder = new StringBuilder();// 将byte数组转成二进制的字符串boolean flag = false;for(int i = 0; i < huffmanBytes.length; i++){// 判断是不是最后一个字节if (huffmanBytes.length-1 == i){flag = true;}stringBuilder.append(byteToBitString(!flag,huffmanBytes[i]));//拿到二进制字符串}// System.out.println("哈弗曼树对应的二进制字符串是 "+stringBuilder.toString());// 把字符串安装到指定的哈夫曼编码进行解码// 把哈夫曼树编码进行调换 因为反向查询 a -> 100 100->aMap<String, Byte> map = new HashMap<>();for (Map.Entry<Byte,String> entry : huffmanCode.entrySet()){map.put(entry.getValue(), entry.getKey());}//System.out.println(map);//创键一个集合 存放byteList<Byte> list = new ArrayList<>();// i理解成是一个索引 扫描stringBuilderfor (int i = 0; i < stringBuilder.length();){int count = 1; // 小的计数器flag = true;Byte b = null;while (flag) {// 取出一个'1'或'0' 组建key 去map{000=108, 01=32, 001=105, 01000=100, 01011=118...中查找String key = stringBuilder.substring(i, i + count);// i 不动 让count移动// 直到匹配到一个字符b = map.get(key);if (b == null) {count++;} else {//匹配到了flag = false;}}list.add(b); 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;}// 使用一个方法 将前面的方法封装起来 ,便于调用/*** @param bytes 原始的字符串对应的字节数组* @return 返回的是经过哈夫曼编码处理后(压缩后)的数组*/private static byte[] huffmanZip(byte[] bytes) {List<Node> nodes = getNodes(bytes);// 根据node创建哈夫曼树Node huffmanTreeRoot = createHuffmanTree(nodes);// 根据哈夫曼树生成对应的哈夫曼编码Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);// 根据生成的哈夫曼编码 压缩得到压缩后的哈夫曼编码字节数组byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);return huffmanCodeBytes;}/*** 构建字节Node数组* @param bytes 字节数组* @return 返回node数组*/public static List<Node> getNodes(byte[] bytes){//1创建一个ArrayListArrayList<Node> nodes = new ArrayList<>();//遍历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);//创建一颗新的二叉树Node parent = new Node(null, leftNode.weight + rightNode.weight);parent.left=leftNode;parent.right=rightNode;//将已经处理的二叉树从nodes删除nodes.remove(leftNode);nodes.remove(rightNode);//将新的二叉树，加到nodes中nodes.add(parent);}//nodes 最后的节点，也就是哈夫曼树的根节点return nodes.get(0);}/*** 编写一个方法将字符串对应的byte[]数组 通过生成的哈夫曼编码表 返回一个哈夫曼编码 压缩后的byte数组* @param bytes 原始的字符串对应的byte[]数组* @param huffmanCode 生成得Huffman编码* @return 返回哈夫曼树编码处理后的byte[]* 当前例子将会返回(类似 因为生成得Huffman树的结构不同 但是长度会相同)1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000* 101111111100110001001010011011100* =>对应的byte[] 数组 放入 8个数字 对应一个byte 放入数组 例如* 10101000(补码) => byte (10101000 => 10101000 -1 => 10100111(反码) => 11011000(源码) =>-88)*/private static byte[] zip(byte[] bytes, Map<Byte,String> huffmanCode){// 1 先用Huffman编码表 将bytes 转成 Huffman编码对应的字符串StringBuilder stringBuilder = new StringBuilder();// 遍历byte数组for(byte b : bytes){stringBuilder.append(huffmanCode.get(b));}//System.out.println(stringBuilder.toString());//将101010001011111...转成bute[]//统计返回byte[]huffmanCodeBytes 长度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){// 步长为8String strByte;if(i + 8 > stringBuilder.length()) {// 不够8位strByte = stringBuilder.substring(i); // i-结束}else {strByte = stringBuilder.substring(i, i + 8);}huffmanCodeBytes[index++] = (byte) Integer.parseInt(strByte,2); // 二进制}return huffmanCodeBytes;}// 生成哈夫曼对应的哈夫曼编码// 1 将哈夫曼树放在Map<Byte,String> 形式大概为 a->100 d->11000 u->11001 e->1110 v->11011 i->101 y->11010 j->0010 k->1111 l->000 o->0011// 2 在生成哈夫曼编码表时 需要拼接路径 定义一个stringBuilder 存储某个叶子节点的路径static Map<Byte,String> huffmanCode = new HashMap<>();static StringBuilder stringBuilder = new StringBuilder();//为了调用方便。我们重载geyCodesprivate static Map<Byte,String > getCodes(Node root){if (root==null){return null;}//处理左子树getCodes(root.left,"0",stringBuilder);//处理右子树getCodes(root.right,"1",stringBuilder);return huffmanCode;}/*** 将传入的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){//判断是叶子节点还是非叶子节点if (node.data == null){ // 非叶子节点//递归处理//像左递归getCodes(node.left,"0",stringBuilder2);//像右递归getCodes(node.right,"1",stringBuilder2);}else {//说明是叶子节点//就表示找到某个叶子节点的最后huffmanCode.put(node.data, stringBuilder2.toString());}}}//前序遍历的方法private static void preOrder(Node root){if (root==null){System.out.println("哈夫曼树为空");}else {root.preOrder();}}
}// 创建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) {// weight 升序排列，从小到大排序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();}}
}输出
使用哈夫曼编码压缩文件
新增方法
/*** 编写一个方法 对文件进行压缩* @param srcFile 传入文件的路径* @param dsFile 压缩后的文件的存储位置*/public static void zipFile(String srcFile, String dsFile) {// 创建输入输出流// 创建文件的输入流FileInputStream is = null;OutputStream os = null;ObjectOutputStream oos = null;try {is = new FileInputStream(srcFile);// 创建和源文件大小一样的数组byte[]byte[] b = new byte[is.available()];is.read(b);// 获取到文件对应的哈夫曼编码// 对源文件进行压缩byte[] huffmanBytes = huffmanZip(b);// 创建文件的输出流,存放压缩文件os = new FileOutputStream(dsFile);// 创建一个和文件输出关联的ObjectOutputStreamoos = new ObjectOutputStream(os);// 这里以对象流的方式写入哈夫曼编码后的字节数组，// 注意一定要把赫夫曼树 写入压缩文件 是为了我们以后恢复源文件的时候使用oos.write(huffmanBytes);oos.writeObject(huffmanCode);}catch (Exception e){e.printStackTrace();}finally {try {is.close();os.close();oos.close();} catch (IOException e) {e.printStackTrace();}}}主方法添加代码
//测试压缩文件String srcFile="d://R-C.png";String destFile="d://a.zip";zipFile(srcFile,destFile);System.out.println("压缩文件ok");全部代码
package huffmancode;import java.io.*;
import java.nio.charset.StandardCharsets;
import java.util.*;public class HuffmanCode {public static void main(String[] args) {//测试压缩文件String srcFile="d://R-C.png";String destFile="d://a.zip";zipFile(srcFile,destFile);System.out.println("压缩文件ok");/* String content = "i like like like java do you like a java";byte[] contentBytes = content.getBytes(StandardCharsets.UTF_8);System.out.println(contentBytes.length);//40for (byte contentByte : contentBytes) {System.out.println(contentByte);}byte[] huffmanCodesBytes = huffmanZip(contentBytes);System.out.println("压缩后的结果是:"+Arrays.toString(huffmanCodesBytes)+"长度="+huffmanCodesBytes.length);byte[] sourceBytes = decode(huffmanCode, 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));//17个//发送huffmanCodeBytes 数组*//*** 编写一个方法 对文件进行压缩* @param srcFile 传入文件的路径* @param dsFile 压缩后的文件的存储位置*/public static void zipFile(String srcFile, String dsFile) {// 创建输入输出流// 创建文件的输入流FileInputStream is = null;OutputStream os = null;ObjectOutputStream oos = null;try {is = new FileInputStream(srcFile);// 创建和源文件大小一样的数组byte[]byte[] b = new byte[is.available()];is.read(b);// 获取到文件对应的哈夫曼编码// 对源文件进行压缩byte[] huffmanBytes = huffmanZip(b);// 创建文件的输出流,存放压缩文件os = new FileOutputStream(dsFile);// 创建一个和文件输出关联的ObjectOutputStreamoos = new ObjectOutputStream(os);// 这里以对象流的方式写入哈夫曼编码后的字节数组，// 注意一定要把赫夫曼树 写入压缩文件 是为了我们以后恢复源文件的时候使用oos.write(huffmanBytes);oos.writeObject(huffmanCode);}catch (Exception e){e.printStackTrace();}finally {try {is.close();os.close();oos.close();} catch (IOException e) {e.printStackTrace();}}}// 完成数据的解压// 思路// 1 将huffmanCodeBytes [40, 46, -56, 46, -56, 46, -55, 5, -123, 6, -88, -46, -126, -20, -124, -126, 24 ]// 重新转成赫夫曼编码对应的字符串 100100100...// 2 将赫夫曼对应的二进制字符串 100100100... 对照 哈夫曼编码转成 i like java....../*** 将byte 转成一个二进制的字符串* @param flag 标志当前是否需要补高位 如果是true 需要补高位* @param b 传入的byte* @return 返回 b 对应二进制的字符串(补码返回)*/private static String byteToBitString(boolean flag,byte b){int temp = b; // 向上强转 b变成int// 如果是整数 需要补高位if(flag) { // 如果当前长度 没有8位 不用高位补码temp |= 256; // 按位与 256 =1 0000 0000 1 = 0000 0001 => 1 0000 0001}String str = Integer.toBinaryString(temp); // 返回temp 对应二进制的补码if (flag) {return str.substring(str.length() - 8); // 取最后8位}else {return str;}}/*** 编写有个方法 完成对压缩数据的编码* @param huffmanCode 哈夫曼编码表* @param huffmanBytes 哈夫曼编码的得到的字节数组* @return 原来的字符串对应的数组*/private static byte[] decode(Map<Byte,String> huffmanCode, byte[] huffmanBytes){// 1 先得到 huffmanBytes 的二进制的字符串 形式为"10101010..."StringBuilder stringBuilder = new StringBuilder();// 将byte数组转成二进制的字符串boolean flag = false;for(int i = 0; i < huffmanBytes.length; i++){// 判断是不是最后一个字节if (huffmanBytes.length-1 == i){flag = true;}stringBuilder.append(byteToBitString(!flag,huffmanBytes[i]));//拿到二进制字符串}// System.out.println("哈弗曼树对应的二进制字符串是 "+stringBuilder.toString());// 把字符串安装到指定的哈夫曼编码进行解码// 把哈夫曼树编码进行调换 因为反向查询 a -> 100 100->aMap<String, Byte> map = new HashMap<>();for (Map.Entry<Byte,String> entry : huffmanCode.entrySet()){map.put(entry.getValue(), entry.getKey());}//System.out.println(map);//创键一个集合 存放byteList<Byte> list = new ArrayList<>();// i理解成是一个索引 扫描stringBuilderfor (int i = 0; i < stringBuilder.length();){int count = 1; // 小的计数器flag = true;Byte b = null;while (flag) {// 取出一个'1'或'0' 组建key 去map{000=108, 01=32, 001=105, 01000=100, 01011=118...中查找String key = stringBuilder.substring(i, i + count);// i 不动 让count移动// 直到匹配到一个字符b = map.get(key);if (b == null) {count++;} else {//匹配到了flag = false;}}list.add(b); 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;}// 使用一个方法 将前面的方法封装起来 ,便于调用/*** @param bytes 原始的字符串对应的字节数组* @return 返回的是经过哈夫曼编码处理后(压缩后)的数组*/private static byte[] huffmanZip(byte[] bytes) {List<Node> nodes = getNodes(bytes);// 根据node创建哈夫曼树Node huffmanTreeRoot = createHuffmanTree(nodes);// 根据哈夫曼树生成对应的哈夫曼编码Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);// 根据生成的哈夫曼编码 压缩得到压缩后的哈夫曼编码字节数组byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);return huffmanCodeBytes;}/*** 构建字节Node数组* @param bytes 字节数组* @return 返回node数组*/public static List<Node> getNodes(byte[] bytes){//1创建一个ArrayListArrayList<Node> nodes = new ArrayList<>();//遍历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);//创建一颗新的二叉树Node parent = new Node(null, leftNode.weight + rightNode.weight);parent.left=leftNode;parent.right=rightNode;//将已经处理的二叉树从nodes删除nodes.remove(leftNode);nodes.remove(rightNode);//将新的二叉树，加到nodes中nodes.add(parent);}//nodes 最后的节点，也就是哈夫曼树的根节点return nodes.get(0);}/*** 编写一个方法将字符串对应的byte[]数组 通过生成的哈夫曼编码表 返回一个哈夫曼编码 压缩后的byte数组* @param bytes 原始的字符串对应的byte[]数组* @param huffmanCode 生成得Huffman编码* @return 返回哈夫曼树编码处理后的byte[]* 当前例子将会返回(类似 因为生成得Huffman树的结构不同 但是长度会相同)1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000* 101111111100110001001010011011100* =>对应的byte[] 数组 放入 8个数字 对应一个byte 放入数组 例如* 10101000(补码) => byte (10101000 => 10101000 -1 => 10100111(反码) => 11011000(源码) =>-88)*/private static byte[] zip(byte[] bytes, Map<Byte,String> huffmanCode){// 1 先用Huffman编码表 将bytes 转成 Huffman编码对应的字符串StringBuilder stringBuilder = new StringBuilder();// 遍历byte数组for(byte b : bytes){stringBuilder.append(huffmanCode.get(b));}//System.out.println(stringBuilder.toString());//将101010001011111...转成bute[]//统计返回byte[]huffmanCodeBytes 长度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){// 步长为8String strByte;if(i + 8 > stringBuilder.length()) {// 不够8位strByte = stringBuilder.substring(i); // i-结束}else {strByte = stringBuilder.substring(i, i + 8);}huffmanCodeBytes[index++] = (byte) Integer.parseInt(strByte,2); // 二进制}return huffmanCodeBytes;}// 生成哈夫曼对应的哈夫曼编码// 1 将哈夫曼树放在Map<Byte,String> 形式大概为 a->100 d->11000 u->11001 e->1110 v->11011 i->101 y->11010 j->0010 k->1111 l->000 o->0011// 2 在生成哈夫曼编码表时 需要拼接路径 定义一个stringBuilder 存储某个叶子节点的路径static Map<Byte,String> huffmanCode = new HashMap<>();static StringBuilder stringBuilder = new StringBuilder();//为了调用方便。我们重载geyCodesprivate static Map<Byte,String > getCodes(Node root){if (root==null){return null;}//处理左子树getCodes(root.left,"0",stringBuilder);//处理右子树getCodes(root.right,"1",stringBuilder);return huffmanCode;}/*** 将传入的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){//判断是叶子节点还是非叶子节点if (node.data == null){ // 非叶子节点//递归处理//像左递归getCodes(node.left,"0",stringBuilder2);//像右递归getCodes(node.right,"1",stringBuilder2);}else {//说明是叶子节点//就表示找到某个叶子节点的最后huffmanCode.put(node.data, stringBuilder2.toString());}}}//前序遍历的方法private static void preOrder(Node root){if (root==null){System.out.println("哈夫曼树为空");}else {root.preOrder();}}
}// 创建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) {// weight 升序排列，从小到大排序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();}}
}输出：
使用哈夫曼编码解压文件
//编写一个方法，完成对压缩文件的解压/**** @param zipFile 准备解压的文件* @param dstFile 将文件解压到哪个路径*/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();System.out.println(huffmanCodes);
//解码byte[] bytes = decode(huffmanCodes, huffmanBytes);System.out.println(bytes);
//将 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) {
// TODO: handle exceptionSystem.out.println(e2.getMessage());}}}主方法添加代码
//测试解压文件String zipFile="d://a.zip";String destFile1="d://A.png";unZipFile(zipFile,destFile1);System.out.println("解压成功");
完整代码
package huffmancode;import java.io.*;
import java.nio.charset.StandardCharsets;
import java.util.*;public class HuffmanCode {public static void main(String[] args) {/* //测试压缩文件String srcFile="d://R-C.png";String destFile="d://a.zip";zipFile(srcFile,destFile);System.out.println("压缩文件ok");*///测试解压文件String zipFile="d://a.zip";String destFile1="d://A.png";unZipFile(zipFile,destFile1);System.out.println("解压成功");/* String content = "i like like like java do you like a java";byte[] contentBytes = content.getBytes(StandardCharsets.UTF_8);System.out.println(contentBytes.length);//40for (byte contentByte : contentBytes) {System.out.println(contentByte);}byte[] huffmanCodesBytes = huffmanZip(contentBytes);System.out.println("压缩后的结果是:"+Arrays.toString(huffmanCodesBytes)+"长度="+huffmanCodesBytes.length);byte[] sourceBytes = decode(huffmanCode, 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));//17个//发送huffmanCodeBytes 数组*//*** 编写一个方法 对文件进行压缩* @param srcFile 传入文件的路径* @param dsFile 压缩后的文件的存储位置*/public static void zipFile(String srcFile, String dsFile) {// 创建输入输出流// 创建文件的输入流FileInputStream is = null;OutputStream os = null;ObjectOutputStream oos = null;try {is = new FileInputStream(srcFile);// 创建和源文件大小一样的数组byte[]byte[] b = new byte[is.available()];is.read(b);// 获取到文件对应的哈夫曼编码// 对源文件进行压缩byte[] huffmanBytes = huffmanZip(b);// 创建文件的输出流,存放压缩文件os = new FileOutputStream(dsFile);// 创建一个和文件输出关联的ObjectOutputStreamoos = new ObjectOutputStream(os);// 这里以对象流的方式写入哈夫曼编码后的字节数组，// 注意一定要把赫夫曼树 写入压缩文件 是为了我们以后恢复源文件的时候使用oos.write(huffmanBytes);oos.writeObject(huffmanCode);}catch (Exception e){e.printStackTrace();}finally {try {is.close();os.close();oos.close();} catch (IOException e) {e.printStackTrace();}}}//编写一个方法，完成对压缩文件的解压/**** @param zipFile 准备解压的文件* @param dstFile 将文件解压到哪个路径*/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();System.out.println(huffmanCodes);
//解码byte[] bytes = decode(huffmanCodes, huffmanBytes);System.out.println(bytes);
//将 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) {
// TODO: handle exceptionSystem.out.println(e2.getMessage());}}}// 完成数据的解压// 思路// 1 将huffmanCodeBytes [40, 46, -56, 46, -56, 46, -55, 5, -123, 6, -88, -46, -126, -20, -124, -126, 24 ]// 重新转成赫夫曼编码对应的字符串 100100100...// 2 将赫夫曼对应的二进制字符串 100100100... 对照 哈夫曼编码转成 i like java....../*** 将byte 转成一个二进制的字符串* @param flag 标志当前是否需要补高位 如果是true 需要补高位* @param b 传入的byte* @return 返回 b 对应二进制的字符串(补码返回)*/private static String byteToBitString(boolean flag,byte b){int temp = b; // 向上强转 b变成int// 如果是整数 需要补高位if(flag) { // 如果当前长度 没有8位 不用高位补码temp |= 256; // 按位与 256 =1 0000 0000 1 = 0000 0001 => 1 0000 0001}String str = Integer.toBinaryString(temp); // 返回temp 对应二进制的补码if (flag) {return str.substring(str.length() - 8); // 取最后8位}else {return str;}}/*** 编写有个方法 完成对压缩数据的编码* @param huffmanCode 哈夫曼编码表* @param huffmanBytes 哈夫曼编码的得到的字节数组* @return 原来的字符串对应的数组*/private static byte[] decode(Map<Byte,String> huffmanCode, byte[] huffmanBytes){// 1 先得到 huffmanBytes 的二进制的字符串 形式为"10101010..."StringBuilder stringBuilder = new StringBuilder();// 将byte数组转成二进制的字符串boolean flag = false;for(int i = 0; i < huffmanBytes.length; i++){// 判断是不是最后一个字节if (huffmanBytes.length-1 == i){flag = true;}stringBuilder.append(byteToBitString(!flag,huffmanBytes[i]));//拿到二进制字符串}// System.out.println("哈弗曼树对应的二进制字符串是 "+stringBuilder.toString());// 把字符串安装到指定的哈夫曼编码进行解码// 把哈夫曼树编码进行调换 因为反向查询 a -> 100 100->aMap<String, Byte> map = new HashMap<>();for (Map.Entry<Byte,String> entry : huffmanCode.entrySet()){map.put(entry.getValue(), entry.getKey());}//System.out.println(map);//创键一个集合 存放byteList<Byte> list = new ArrayList<>();// i理解成是一个索引 扫描stringBuilderfor (int i = 0; i < stringBuilder.length();){int count = 1; // 小的计数器flag = true;Byte b = null;while (flag) {// 取出一个'1'或'0' 组建key 去map{000=108, 01=32, 001=105, 01000=100, 01011=118...中查找String key = stringBuilder.substring(i, i + count);// i 不动 让count移动// 直到匹配到一个字符b = map.get(key);if (b == null) {count++;} else {//匹配到了flag = false;}}list.add(b); 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;}// 使用一个方法 将前面的方法封装起来 ,便于调用/*** @param bytes 原始的字符串对应的字节数组* @return 返回的是经过哈夫曼编码处理后(压缩后)的数组*/private static byte[] huffmanZip(byte[] bytes) {List<Node> nodes = getNodes(bytes);// 根据node创建哈夫曼树Node huffmanTreeRoot = createHuffmanTree(nodes);// 根据哈夫曼树生成对应的哈夫曼编码Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);// 根据生成的哈夫曼编码 压缩得到压缩后的哈夫曼编码字节数组byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);return huffmanCodeBytes;}/*** 构建字节Node数组* @param bytes 字节数组* @return 返回node数组*/public static List<Node> getNodes(byte[] bytes){//1创建一个ArrayListArrayList<Node> nodes = new ArrayList<>();//遍历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);//创建一颗新的二叉树Node parent = new Node(null, leftNode.weight + rightNode.weight);parent.left=leftNode;parent.right=rightNode;//将已经处理的二叉树从nodes删除nodes.remove(leftNode);nodes.remove(rightNode);//将新的二叉树，加到nodes中nodes.add(parent);}//nodes 最后的节点，也就是哈夫曼树的根节点return nodes.get(0);}/*** 编写一个方法将字符串对应的byte[]数组 通过生成的哈夫曼编码表 返回一个哈夫曼编码 压缩后的byte数组* @param bytes 原始的字符串对应的byte[]数组* @param huffmanCode 生成得Huffman编码* @return 返回哈夫曼树编码处理后的byte[]* 当前例子将会返回(类似 因为生成得Huffman树的结构不同 但是长度会相同)1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000* 101111111100110001001010011011100* =>对应的byte[] 数组 放入 8个数字 对应一个byte 放入数组 例如* 10101000(补码) => byte (10101000 => 10101000 -1 => 10100111(反码) => 11011000(源码) =>-88)*/private static byte[] zip(byte[] bytes, Map<Byte,String> huffmanCode){// 1 先用Huffman编码表 将bytes 转成 Huffman编码对应的字符串StringBuilder stringBuilder = new StringBuilder();// 遍历byte数组for(byte b : bytes){stringBuilder.append(huffmanCode.get(b));}//System.out.println(stringBuilder.toString());//将101010001011111...转成bute[]//统计返回byte[]huffmanCodeBytes 长度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){// 步长为8String strByte;if(i + 8 > stringBuilder.length()) {// 不够8位strByte = stringBuilder.substring(i); // i-结束}else {strByte = stringBuilder.substring(i, i + 8);}huffmanCodeBytes[index++] = (byte) Integer.parseInt(strByte,2); // 二进制}return huffmanCodeBytes;}// 生成哈夫曼对应的哈夫曼编码// 1 将哈夫曼树放在Map<Byte,String> 形式大概为 a->100 d->11000 u->11001 e->1110 v->11011 i->101 y->11010 j->0010 k->1111 l->000 o->0011// 2 在生成哈夫曼编码表时 需要拼接路径 定义一个stringBuilder 存储某个叶子节点的路径static Map<Byte,String> huffmanCode = new HashMap<>();static StringBuilder stringBuilder = new StringBuilder();//为了调用方便。我们重载geyCodesprivate static Map<Byte,String > getCodes(Node root){if (root==null){return null;}//处理左子树getCodes(root.left,"0",stringBuilder);//处理右子树getCodes(root.right,"1",stringBuilder);return huffmanCode;}/*** 将传入的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){//判断是叶子节点还是非叶子节点if (node.data == null){ // 非叶子节点//递归处理//像左递归getCodes(node.left,"0",stringBuilder2);//像右递归getCodes(node.right,"1",stringBuilder2);}else {//说明是叶子节点//就表示找到某个叶子节点的最后huffmanCode.put(node.data, stringBuilder2.toString());}}}//前序遍历的方法private static void preOrder(Node root){if (root==null){System.out.println("哈夫曼树为空");}else {root.preOrder();}}
}// 创建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) {// weight 升序排列，从小到大排序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();}}
}注意事项
