这个赫夫曼树,我整了两天差不多算是搞定了。这篇文章主要介绍:
赫夫曼树的构建
赫夫曼编码
借助赫夫曼树进行文件的压缩与解压缩
赫夫曼树 :给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度( wpl
)达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(HuffmanTree
)。
赫夫曼树的构建 给你一个数列 {13,7,8,3,29,6,1},要求转成一颗赫夫曼树
为之奈何?步骤如下:
从小到大进行排序,将每一个数据,每个数据都是一个节点,每个节点可以看成是一棵最简单的二叉树
取出根节点权值最小的两棵二叉树
组成一棵新的二叉树,该新的二叉树的根节点的权值是前面两棵二叉树根节点权值的和
新的二叉树节点再和剩余的节点排序,再找到最小的两棵二叉树再进行组合,依次循环,得到一棵赫夫曼树
最终形成的二叉树如下,叶子节点就是我们的数列节点:
我们先要定义一个 Node
节点类,它有左指针、右指针和权值三个属性:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Node implements Comparable <Node > { public Node left; public Node right; public int val; public Node (int val) { this .val = val; } @Override public String toString () { return "Node{" + "val=" + val + '}' ; } @Override public int compareTo (Node o) { return this .val-o.val; } }
构建方法如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 public static Node createHuffman (int [] arr) { ArrayList<Node> nodes = new ArrayList<>(); for (int t : arr) { nodes.add(new Node(t)); } while (nodes.size()>1 ){ Collections.sort(nodes); Node first = nodes.get(0 ); Node second = nodes.get(1 ); Node sum = new Node(first.val+second.val); sum.left = first; sum.right = second; nodes.add(sum); nodes.remove(first); nodes.remove(second); } return nodes.get(0 ); }
代码写完之后,我们可以在 main
方法中进行debug ,看看是否正确。
赫夫曼编码 我们会了构建赫夫曼树之后,还需要对它们进行编码,即赫夫曼编码。
我们的文件什么的都是二进制文件我,我们站在字节上,它们都是一个个字节。
编码之后要返回什么?肯定是一个 HashMap
呀,它的键是什么类型我们先不管,它的值肯定是字符串类型的,只有0和1构成的字符串 。这个不难理解,关键值怎么办?是一个数,那肯定,但是我们往后面继续做的时候,对文件进行压缩解压缩什么的,操作的是什么?
是字节,所以,干脆我们现在就用字节作为这个 HashMap
的键,每一个 byte
对应的赫夫曼编码就是它的值。
所以Node节点我们要改一下,给它增加一个字节成员属性:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Node implements Comparable <Node > { public Node left; public Node right; public Byte b; public int val; public Node (Byte b,int val) { this .b = b; this .val = val; } @Override public String toString () { return "Node{" + "b=" + b + ", val=" + val + '}' ; } @Override public int compareTo (Node o) { return this .val-o.val; } }
下面我们写这个赫夫曼编码的方法,传入的是构建的赫夫曼数的根节点:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 static HashMap<Byte,String> haffmanMap = new HashMap<>();public static HashMap<Byte,String> getCodes (Node root) { if (root==null ) return null ; StringBuffer sb = new StringBuffer(); getCodes(root.left,"0" ,sb); getCodes(root.right,"1" ,sb); return haffmanMap; } public static void getCodes (Node node, String s, StringBuffer sb) { if (node==null ) return ; StringBuffer sb2 = new StringBuffer(sb); sb2 = sb2.append(s); if (node.b!=null ){ haffmanMap.put(node.b, sb2.toString()); }else { getCodes(node.left,"0" ,sb2); getCodes(node.right,"1" ,sb2); } }
借助赫夫曼树对文件压缩 下面我们做一个案例,我特马搞了两天这个破玩意。
就是完成文件的压缩与解压缩,完成主要的两个方法:压缩与解压缩
它们都是传入两个 File
参数,一个完成压缩,另一个完成解压缩。
先看压缩文件,下面写一下步骤:
文件输入流读取文件的 byte
数组
getByte(bytes)
方法获取每个字节及其个数,返回的是 HashMap
根据上面的 HashMap
构建赫夫曼树,获取根节点 root
根据 root
使用 getCodes(root)
方法获取赫夫曼编码表(haffmanMap
),这个也是 HashMap
利用文件字节数组(bytes
)和赫夫曼编码表(haffmanMap
)得到采用赫夫曼编码后的字符串 sb
将压缩后的字符串 sb
用 toByte(sb)
方法转换成新的字节数组 haffmanBytes
将新的字节数组(haffmanBytes
)和赫夫曼编码表(haffmanMap
)写入到文件输出流中,压缩完成
下面写每个对应的方法:
读取文件字节流 我们看看我们总的步骤,其实我们做这些东西的目的就是根据读取的字节数组得到另一个新的字节数组,把它写入到输出流,那个赫夫曼编码表我们会直接写在类中。所以我们完全可以再进行进一步的抽象,再抽象出一个方法compressionByte
,它传入一个字节数组,返回赫夫曼编码的字节数组。
所以压缩的主方法里面可以这样写,获取到文件字节流之后,直接调用 compressionByte
,然后将返回的字节还有类的静态成员赫夫曼编码表(haffmanMap
)都写入到输出流中,如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 public static void compression (File file,File newFile) { FileInputStream fis = null ; FileOutputStream fos =null ; BufferedInputStream bis = null ; ObjectOutputStream oos = null ; try { fis = new FileInputStream(file); int len = fis.available(); fos = new FileOutputStream(newFile); bis = new BufferedInputStream(fis); oos = new ObjectOutputStream(fos); byte [] bytes = new byte [len]; bis.read(bytes); byte [] haffmanBytes = compressionByte(bytes); oos.writeObject(haffmanBytes); oos.writeObject(haffmanMap); oos.flush(); } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } finally { try { oos.close(); bis.close(); } catch (IOException e) { e.printStackTrace(); } } }
下面我们写 compressionByte
方法,我们把我们上面的步骤都抽象成方法,在这个 compressionByte
方法中按步骤调用即可,如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public static byte [] compressionByte(byte [] bytes){ HashMap<Byte, Integer> map = getByteCount(bytes); Node root = createHuffman(map); getCodes(root); String sb = getHaffmanString(bytes); byte [] haffmanBytes = toByte(sb.toString()); return haffmanBytes; }
下面我们再接着写对应的方法。
获取字节对应个数 就是遍历字节数组,如果我们的 HashMap
中不存在则添加,存在则将它的值加1。
1 2 3 4 5 6 7 8 9 10 11 12 13 public static HashMap<Byte,Integer> getByteCount (byte [] bytes) { HashMap<Byte, Integer> hashMap = new HashMap<>(); for (byte b : bytes) { if (!hashMap.containsKey(b)){ hashMap.put(b,1 ); }else { Integer integer = hashMap.get(b); hashMap.replace(b,integer+1 ); } } return hashMap; }
构建赫夫曼树 根据上面我们获得的 HashMap
,然后创建赫夫曼树,将它的根节点返回:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public static Node createHuffman (HashMap<Byte,Integer> hashMap) { ArrayList<Node> nodes = new ArrayList<>(); hashMap.forEach((k,v)->{ nodes.add(new Node(k,v)); }); while (nodes.size()>1 ){ Collections.sort(nodes); Node first = nodes.get(0 ); Node second = nodes.get(1 ); Node sum = new Node(null ,first.val+second.val); sum.left = first; sum.right = second; nodes.add(sum); nodes.remove(first); nodes.remove(second); } return nodes.get(0 ); }
获取赫夫曼编码 我们构建玩赫夫曼树之后,根据它的根节点对每一个字节进行赫夫曼编码,我们要先在类中定义一个静态的 HashMap<Byte,String>
,它就是我们最后要写入的赫夫曼编码表。代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 static HashMap<Byte,String> haffmanMap = new HashMap<>();public static HashMap<Byte,String> getCodes (Node root) { if (root==null ) return null ; StringBuffer sb = new StringBuffer(); getCodes(root.left,"0" ,sb); getCodes(root.right,"1" ,sb); return haffmanMap; } public static void getCodes (Node node, String s, StringBuffer sb) { if (node==null ) return ; StringBuffer sb2 = new StringBuffer(sb); sb2 = sb2.append(s); if (node.b!=null ){ haffmanMap.put(node.b, sb2.toString()); }else { getCodes(node.left,"0" ,sb2); getCodes(node.right,"1" ,sb2); } }
得到采用赫夫曼编码后的字符串 得到赫夫曼编码表后,我们就可以根据这个编码表和之前获得的字节数组,重新对这些字节进行编码,返回编码后的字符串,下面就是这个方法的代码:就是先构造一个 StringBuffer
,然后遍历字节数组,不断查询赫夫曼编码表,把对应的编码值追加到 StringBuffer
后面。
1 2 3 4 5 6 7 8 9 public static String getHaffmanString (byte [] bytes) { StringBuffer sb = new StringBuffer(); for (Byte b : bytes) { String s1 = haffmanMap.get(b); sb.append(s1); } return sb.toString(); }
将字符串转换成byte数组 有同学可能会想到,我们得到这个字符串之后如果直接就写到输出流不就行了,你可拉倒吧!
这个是字符串,每个01都是一个字节,这样反而比原来大的多,还压缩个锤子。
我们还要把这个字符串转换成字节数组,然后再写入到输出流。
所以我们还要完成最后一个 toByte
方法,它传入一个字符串,返回对应的字节数组。
但是其实蛮简单的,字符串每8个字符就能转换成一个字节,就是调个 Integer.parseInt(String s, int radix)
这个静态方法,第二个参数写成2即可。最后截取的时候还要留意不要截取多了,因为字符串的长度不一定是8的倍数,最后可能截不了8位这么多 ,我们得注意这个点。
我们可能会这样写:
1 2 3 4 5 6 7 8 9 10 11 12 13 public static byte [] toByte(String s){ int len = (s.length()+7 )/8 ; byte [] bytes = new byte [len]; int index = 0 ; for (int i = 0 ,length=s.length(); i < length; i+=8 ) { String substring = (i+8 )>length ? s.substring(i) : s.substring(i,i+8 ); bytes[index++] = (byte ) Integer.parseInt(substring,2 ); } return bytes; }
这样写确实没有问题。
但是特马的,解压缩的时候直接完蛋,我就是这个问题,给我整蒙了,我在解压缩的时候出了点错误,找它找了至少两个小时才发现,原来是这里存在一个小问题。
我们看看下面这样的情景(其实就是我出错的场景):
字符串转字节数组,字符串的长度不是8的倍数,它的长度%8等于7。比如最后还剩 0000 011
这7位。它会变成字节3。但是我们解压缩的时候,会把3转成字符串 0000 0011
,看到没?这里会多出一个0,其实不一定非得是多出一个0,因为我们不知道它本来的字符串长度是多少,这里是否会多0,还是多了多少个0,我们在解压缩的时候都不知道。那么译码的时候肯定会出错。
所以为之奈何?关键原因就是我们在解压缩的时候不知道最后一个字节是什么情况,对于每一个字节,我们都会把它们变成8位01的字符串,但是最后一个字节到底变成多少位,不知道。所以我们要解决这个问题,肯定要把这个数据传过去,解压缩的时候根据这个数据,进行截取。最好传的数据是 8-len%8
,为什么?我们姑且称它为 j ,我们拿到这个 j 之后,在最后一位的时候直接用 substring(j)
方法截取就行了,它就是我们截取要开始的位置呗!
所以,我们约定最后返回的byte数组,也是我们写入到输出流中的byte数组,第一个字节中存放一个数,它不是真正的字节数据, 而是我们上面的那个 j 。解压缩的时候拿到这个 j ,从 bytes[1]
再开始相关操作,最后一位用这个 j 截取即可。
所以这个方法应该这样写:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public static byte [] toByte(String s){ int len = (s.length()+7 )/8 ; len = len+1 ; byte [] bytes = new byte [len]; bytes[0 ] = (byte ) (8 -s.length()%8 ); int index = 1 ; for (int i = 0 ,length=s.length(); i < length; i+=8 ) { String substring = (i+8 )>length ? s.substring(i) : s.substring(i,i+8 ); bytes[index++] = (byte ) Integer.parseInt(substring,2 ); } return bytes; }
至此,方法全部完成,我们在main方法中应该就可以直接调用 compression
方法就行了,还有一点就是对于小的文件可能压缩后的大小还要比本来文件还大,正常,因为我们除了字节数组,还写入了赫夫曼编码表。但当文件大了之后应该就不会出现这种情况了,我这边测试一个 111KB 的 txt文件压缩后的大小是 79KB,还是可以的。
下面再来写解压缩的方法,这个应该就简单了,啊,累的一批!坚持住
解压缩 先写步骤:
输入流读取 byte
数组及赫夫曼编码表 haffmanMap
因为我们要反查询,要将编码变反转,然后用 byteToString(bytes)
方法将bytes转换成我们之前那个字符串 sb
遍历 sb
,根据赫夫曼反编码表,转成最本来的 byte
数组
byte写入到输出流,解压缩就完成了,文件就又回来了
读取字节流及赫夫曼编码表 我们还是老样子,先看看这个解压缩的输入和输出,把它抽象出来。其实就是输入字节数组和赫夫曼编码表,输出一个字节数组。把它抽象为 reCompressionByte
方法,所以我们的解压缩的代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 public static void reCompression (File file,File newFile) { FileInputStream fis = null ; FileOutputStream fos =null ; ObjectInputStream ois = null ; BufferedOutputStream bos = null ; try { fis = new FileInputStream(file); fos = new FileOutputStream(newFile); ois = new ObjectInputStream(fis); bos = new BufferedOutputStream(fos); byte [] bytes = (byte []) ois.readObject(); HashMap<Byte, String> reHaffmanMap = (HashMap<Byte, String>) ois.readObject(); byte [] newBytes = reCompressionByte(bytes,reHaffmanMap); bos.write(newBytes); bos.flush(); } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } catch (ClassNotFoundException e) { e.printStackTrace(); } finally { try { bos.close(); ois.close(); } catch (IOException e) { e.printStackTrace(); } } }
我们再把后面的步骤抽象为方法,写入到 reCompressionByte
方法中,如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public static byte [] reCompressionByte(byte [] bytes, HashMap<Byte, String> reHaffmanMap) { HashMap<String, Byte> reComToBytes = new HashMap<>(); reHaffmanMap.forEach((k,v)->{ reComToBytes.put(v,k); }); String sb = reComByteToString(bytes); ArrayList<Byte> byteList = reComToBytes(sb, reComToBytes); byte [] resbytes = ArrListToArr(byteList); return resbytes; }
先将赫夫曼编码表反转,然后得到字符串,再得到数组,将数组返回。
对了,中间我们返回原来的byte数组时,不能直接用数组,要先用 ArrayList
接受,后面再调用 ArrListToArr
方法将它转换成数组。
将字节数组转换成字符串 我们先写一个将一个字节转换成字符串的方法:
1 2 3 4 5 6 7 8 public static String byteToString (byte b) { int temp = b; temp |= 256 ; String s = Integer.toBinaryString(temp); return s.substring(s.length()-8 ); }
它主要调用 Integer.toBinaryString
这个静态方法,不过他传入的参数是 int
类型的,我们要通过 与运算和截取操作,把它变成8位。
然后再重载这个方法,这时传入的是一个字节数组:
1 2 3 4 5 6 7 8 public static String byteToString (byte [] bytes) { StringBuffer sb = new StringBuffer(); for (byte b : bytes) { sb.append(byteToString(b)); } return sb.toString(); }
这个不难理解的吧,然后再完成我们的 reComByteToString(bytes)
方法,不过不要玩了我们之前的约定:我们写入到输出流中的byte数组,第一个字节中存放一个数,它不是真正的字节数据, 而是我们上面的那个 j 。
所以代码如下:
1 2 3 4 5 6 7 8 9 10 11 public static String reComByteToString (byte [] bytes) { String sb = byteToString(bytes); int len = sb.length(); String front = sb.substring(8 ,len-8 ); String back = sb.substring(len-8 ,len); back = back.substring(bytes[0 ]); sb = front+back; return sb; }
返回原来的byte数组 下面我们先写返回 ArrayList
类型的那个方法(reComToBytes
),就是不断遍历查询添加:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public static ArrayList<Byte> reComToBytes (String sb,HashMap<String,Byte> reHaffmanMap) { ArrayList<Byte> byteList = new ArrayList<>(); int left = 0 ; int right = 0 ; int len = sb.length(); while (right<=len){ if (reHaffmanMap.containsKey(sb.substring(left,right))){ Byte b = reHaffmanMap.get(sb.substring(left, right)); byteList.add(b); left = right; } right++; } return byteList; }
下面将 ArrayList
转换成数组类型的 byte
:
1 2 3 4 5 6 7 8 9 10 11 12 13 public static byte [] ArrListToArr(ArrayList<Byte> byteList){ int size = byteList.size(); Byte[] resBytes = new Byte[size]; byteList.toArray(resBytes); byte [] resbytes = new byte [size]; for (int i = 0 ; i < size; i++) { resbytes[i] = resBytes[i]; } return resbytes; }
至此,全部完成!撒花,累死了,纪念我学了两天的赫夫曼树,还有今天写这一篇博客!