数据结构与相关算法.zip

package com.atguigu.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 = "d://Uninstall.xml"; // String dstFile = "d://Uninstall.zip"; // // zipFile(srcFile, dstFile); // System.out.println("压缩文件ok~~"); //测试解压文件 String zipFile = "d://Uninstall.zip"; String dstFile = "d://Uninstall2.xml"; unZipFile(zipFile, dstFile); System.out.println("解压成功!"); /* String content = "i like like like java do you like a java"; byte[] contentBytes = content.getBytes(); System.out.println(contentBytes.length); //40 byte[] 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)); // "i like like like java do you like a java" */ //如何将 数据进行解压(解码) //分步过程 /* 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 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数组 huffmanBytes byte[] huffmanBytes = (byte[])ois.readObject(); //读取赫夫曼编码表 Map<Byte,String> huffmanCodes = (Map<Byte,String>)ois.readObject(); //解码 byte[] bytes = decode(huffmanCodes, huffmanBytes); //将bytes 数组写入到目标文件 os = new FileOutputStream(dstFile); //写数据到 dstFile 文件 os.write(bytes); } catch (Exception e) { // TODO: handle exception System.out.println(e.getMessage()); } finally { try { os.close(); ois.close(); is.close(); } catch (Exception e2) { // TODO: handle exception 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); //创建一个和文件输出流关联的ObjectOutputStream oos = new ObjectOutputStream(os); //把 赫夫曼编码后的字节数组写入压缩文件 oos.writeObject(huffmanBytes); //我们是把 //这里我们以对象流的方式写入 赫夫曼编码，是为了以后我们恢复源文件时使用 //注意一定要把赫夫曼编码 写入压缩文件 oos.writeObject(huffmanCodes); }catch (Exception e) { // TODO: handle exception System.out.println(e.getMessage()); }finally { try { is.close(); oos.close(); os.close(); }catch (Exception e) { // TODO: handle exception System.out.println(e.getMessage()); } } } //完成数据的解压 //思路 //1. 将huffmanCodeBytes [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28] // 重写先转成 赫夫曼编码对应的二进制的字符串 "1010100010111..." //2. 赫夫曼编码对应的二进制的字符串 "1010100010111..." =》 对照 赫夫曼编码 =》 "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 对应的 二进制的字符串 ， 形式 1010100010111... 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)); } //把字符串安装指定的赫夫曼编码进行解码 //把赫夫曼编码表进行调换，因为反向查询 a->100 100->a Map<String, Byte> map = new HashMap<String,Byte>(); for(Map.Entry<Byte, String> entry: huffmanCodes.entrySet()) { map.put(entry.getValue(), entry.getKey()); } //创建要给集合，存放byte List<Byte> list = new ArrayList<>(); //i 可以理解成就是索引,扫描 stringBuilder for(int i = 0; i < stringBuilder.length(); ) { int count = 1; // 小的计数器 boolean flag = true; Byte b = null; while(flag) { //1010100010111... //递增的取出 key 1 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;//i 直接移动到 count } //当for循环结束后，我们list中就存放了所有的字符 "i like like like java do you like a java" //把list 中的数据放入到byte[] 并返回 byte b[] = new byte[list.size()]; for(int i = 0;i < b.length; i++) { b[i] = list.get(i); } return b; } /** * 将一个byte 转成一个二进制的字符串, 如果看不懂，可以参考我讲的Java基础 二进制的原码，反码，补码 * @param b 传入的 byte * @param flag 标志是否需要补高位如果是true ，表示需要补高位，如果是false表示不补, 如果是最后一个字节，无需补高位 * @return 是该b 对应的二进制的字符串，（注意是按补码返回） */ private static String byteToBitString(boolean flag, byte b) { //使用变量保存 b int 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 这时原�