浙江龙网

  1. 首页 > 生活百科 > >

数据结构与算法【Java】08---树结构的实际应用( 七 )

生活百科

数据压缩的结果：

数据结构与算法【Java】08---树结构的实际应用

文章插图
压缩率：（40-17）/40=57.5%
3.6、使用赫夫曼编码解码（数据解压）使用赫夫曼编码来解码数据，具体要求是
  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"
在数据解压的过程中我们需要两个方法，一个是将压缩后的结果转为二进制的字符串，一个是对压缩数据进行解码
/** * 将一个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; //按位与 2561 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 huffmanCodes 赫夫曼编码表 map（key = value） * @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->aMap<String, Byte>map = new HashMap<String,Byte>();for(Map.Entry<Byte, String> entry: huffmanCodes.entrySet()) {map.put(entry.getValue(), entry.getKey());//key = value变成 value = https://www.huyubaike.com/biancheng/key}//创建要给集合，存放byteList list = new ArrayList<>();//i 可以理解成就是索引,扫描 stringBuilderfor(inti = 0; i < stringBuilder.length(); ) {int count = 1; // 小的计数器boolean flag = true;Byte b = null;while(flag) {//1010100010111...//递增的取出 key 1(1，10,101...匹配)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[] sourceBytes = decode(huffmanCodes, huffmanCodesBytes);System.out.println("(解压后)原来的字符串="+new String(sourceBytes));
数据结构与算法【Java】08---树结构的实际应用

文章插图
3.6、文件压缩我们学习了通过赫夫曼编码对一个字符串进行编码和解码, 下面我们来完成对文件的压缩和解压， 具体要求：给你一个图片文件，要求对其进行无损压缩, 看看压缩效果如何
思路：读取文件-> 得到赫夫曼编码表 -> 完成压缩
首先我们创建一个图片文件
数据结构与算法【Java】08---树结构的实际应用

文章插图
压缩代码
//编写方法，将一个文件进行压缩/** * * @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) {System.out.println(e.getMessage());}finally {try {is.close();oos.close();os.close();}catch (Exception e) {System.out.println(e.getMessage());}}}

推荐阅读


上一篇：frp服务利用云主机实现Windows远程连接

下一篇：「Tubian」Tubian0.41!支持Windows QQ微信！