【尚硅谷】数据结构与算法（Java数据结构与算法）.zip

package com.atguigu.huffmancode; import java.io.*; import java.util.*; /** * @author Peter * @date 2022/8/28 11:42 * @description Usage */ public class HuffmanCode { static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>(); static StringBuilder stringBuilder = new StringBuilder(); public static void main(String[] args) { String content = "i like like like java do you like a java"; System.out.println("content = " + content); byte[] bytes = content.getBytes(); System.out.println("bytes = " + bytes.length); byte[] huffmanZip = huffmanZip(bytes); System.out.println("huffmanZip = " + Arrays.toString(huffmanZip)); System.out.println("huffmanZip.length = " + huffmanZip.length); /** * 解码 */ byte[] sourceBytes = decode(huffmanCodes, huffmanZip); System.out.println("sourceBytes = " + new String(sourceBytes)); /** * 压缩文件 */ String srcFile = "d://test-1.bmp"; String dstFile = "d://test-1.zip"; zipFile(srcFile, dstFile); System.out.println("文件压缩成功"); /** * 解压文件 * TODO 解压后的文件不能打开 */ String zipFile = "d://test-1.zip"; String dstFiles = "d://test-2.bmp"; unZipFile(zipFile, dstFiles); System.out.println("解压完成"); /* List<Node> nodes = getNodes(bytes); System.out.println("nodes = " + nodes); System.out.println("霍夫曼树--前序遍历"); Node huffmanTreeRoot = createHuffmanTree(nodes); huffmanTreeRoot.preOrder(); //测试生成了对应的霍夫曼编码 getCodes(huffmanTreeRoot); System.out.println("huffmanCodes = " + huffmanCodes); byte[] zip = zip(bytes, huffmanCodes); //zip = [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28] System.out.println("zip = " + Arrays.toString(zip)); */ } /** * 文件解压 * * @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); ois = new ObjectInputStream(is); byte[] huffmanBytes = (byte[]) ois.readObject(); Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject(); //解码 byte[] decodes = decode(huffmanCodes, huffmanBytes); //将decodes写入文件 os = new FileOutputStream(dstFile); os.write(decodes); } catch (IOException | ClassNotFoundException e) { e.printStackTrace(); } finally { try { //与打开顺序相反 if (os != null) { os.close(); } if (ois != null) { ois.close(); } if (is != null) { is.close(); } } catch (IOException e) { e.printStackTrace(); } } } /** * 将一个文件进行压缩 * * @param srcFile 待压缩的文件路径 * @param dstFile 压缩后的文件存储位置 */ public static void zipFile(String srcFile, String dstFile) { FileInputStream fis = null; OutputStream os = null; ObjectOutputStream oos = null; try { fis = new FileInputStream(srcFile); //创建一个与原文件大小一样的byte[] byte[] bytes = new byte[fis.available()]; //读取文件 fis.read(bytes); //获取文件对应的霍夫曼编码表 byte[] huffmanZipBytes = huffmanZip(bytes); os = new FileOutputStream(dstFile); //创建一个与文件输出流关联的ObjectOutputStream oos = new ObjectOutputStream(os); //以对象流的方式写入霍夫曼编码 oos.writeObject(huffmanZipBytes); //这里我们以对象流的方式写入 赫夫曼编码，是为了以后我们恢复源文件时使用 //注意一定要把赫夫曼编码 写入压缩文件 oos.writeObject(huffmanCodes); } catch (IOException e) { e.printStackTrace(); } finally { try { if (oos != null) { oos.close(); } if (os != null) { os.close(); } if (fis != null) { fis.close(); } } catch (IOException e) { e.printStackTrace(); } } } /** * @param huffmanCodes 霍夫曼编码表map * @param huffmanBytes 霍夫曼编码得到的字节数组 * @return */ private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) { //1.先得到huffmanBytes对应的二进制的字符串 StringBuilder stringBuilder = new StringBuilder(); //将byte数组转成二进制的字符串 for (int i = 0; i < huffmanBytes.length; i++) { byte b = huffmanBytes[i]; //判读是否最后1个字节 boolean flag = (i == huffmanBytes.length - 1); stringBuilder.append(byteToBitString(!flag, b)); } //System.out.println("stringBuilder = " + stringBuilder.toString()); //把字符串按照指定的霍夫曼编码进行解码 Map<String, Byte> map = new HashMap<>(); for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) { map.put(entry.getValue(), entry.getKey()); } //System.out.println("map = " + map); //创建集合，存放byte ArrayList<Byte> list = new ArrayList<>(); for (int i = 0; i < stringBuilder.length(); ) { int count = 1; boolean flag = true; Byte b = null; while (flag) { /** * TODO 解压时StringIndexOutOfBoundsException: String index out of range: 64587 * Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 64587 * at java.lang.AbstractStringBuilder.substring(AbstractStringBuilder.java:933) * at java.lang.StringBuilder.substring(StringBuilder.java:76) * at com.atguigu.huffmancode.HuffmanCode.decode(HuffmanCode.java:212) * at com.atguigu.huffmancode.HuffmanCode.unZipFile(HuffmanCode.java:92) * at com.atguigu.huffmancode.HuffmanCode.main(HuffmanCode.java:48) */ String key = stringBuilder.substring(i, i + count); b = map.get(key); if (b == null) { count++; } else { //匹配到 flag = false; } } list.add(b); //i移动到count位置 i += count; } //把list中的数据放到byte[]中 byte[] bytes = new byte[list.size()]; for (int i = 0; i < bytes.length; i++) { bytes[i] = list.get(i); } return bytes; } /** * 将一个byte转换成一个二进制的字符串 * * @param flag 标志是否需要补高位；如true则需要补高位 * @param b 传入的byte * @return b对应的二进制字符串(补码返回) */ private static String byteToBitString(boolean flag, byte b) { int temp = b; //如果是正数，须补高位 //按位