哈发曼编码是一种变长编码格式，广泛应用于数据文件压缩
定长编码：例如Ascii码转化
哈夫曼编码 :（可以解决自定义变长编码中的解码二义性问题）
统计各个字符对应的个数
次数作为权值构建一颗哈夫曼树（可能不唯一，会导致不同编码）
哈夫曼树的左路径为0，右路径为1，确定每个叶节点的字符的编码（前缀编码）。
编码过程
解码过程 import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; public class HuffmanMaTree { public static void main(String[] args) { char[] ss= {'i','l','i','k','e','y','o','u'}; //统计个数并保存 //使用List对所有Node进行管理,方便每次排序 List<HuffNode> nodes = new ArrayList<HuffNode>(); for(int i =0;i<ss.length;i++) { int j =0; for(;j<nodes.size();j++) { if((ss[i]+"").equals(nodes.get(j).getC().toString()) ) { nodes.get(j).setValue(nodes.get(j).getValue()+1); break; } } if(j == nodes.size()) { nodes.add(new HuffNode(ss[i]+"",1)); } } //构建哈夫曼树,最后nodes.get(0)即为哈夫曼树的根节点 while(nodes.size()>1) { //对节点进行排序 Collections.sort(nodes); //选当前List中最小的两个节点构成连接构成一个新的节点 HuffNode left = nodes.get(0); HuffNode right = nodes.get(1); HuffNode current = new HuffNode(null,left.value+right.value); current.setLeft(left); current.setRight(right); //将List中已连接的两个最小的节点删除，并将最新节点加入 nodes.remove(left); nodes.remove(right); nodes.add(current); } qian(nodes.get(0)); System.out.println(); //定义List<Map<key,value>>管理字符的字节码 Map<String,String> codes = new HashMap<String,String>(); //递归遍历哈夫曼树确定编码 qianHuffmanCodes(nodes.get(0),"","",codes); //输出编码集 System.out.println(codes.toString()); //压缩编码 //未压缩时存储 System.out.println("&&&&&&&&&&未压缩需存储的二进制编码位数&&&&&&&&&"); String str = "ilikeyou"; byte[] strBtyes = str.getBytes(); System.out.println(strBtyes.length); System.out.println("&&&&&&&&&&压缩后需存储的二进制编码位数&&&&&&&&&"); //哈夫曼编码对应的"0""1"字符串 String huffString = ""; for(int i=0;i<str.length();i++) { huffString = huffString + codes.get(str.charAt(i)+""); } System.out.println("01字符串："+huffString.toString()); //将01字符串转化为byte[] int len = 0; if(huffString.length()%8 == 0) { len = huffString.length()/8; }else { len = huffString.length()/8 + 1; } byte[] huffCodeBytes = new byte[len]; int index = 0; for(int i=0;i<huffString.length();i+=8) { String midstr; if(i+8>huffString.length()) { midstr = huffString.substring(i); }else { midstr = huffString.substring(i, i+8); } huffCodeBytes[index] = (byte) Integer.parseInt(midstr, 2); index++; } System.out.println(huffCodeBytes.length); //解压过程 //此处省略bytes[] => 01字符串的过程,编写从01字符串根据哈夫曼编码转为源字符串的过程 //将哈夫曼编码的key和value逆转。 Map<String,String> map = new HashMap<String,String>(); for(Map.Entry<String, String> entry : codes.entrySet()) { map.put(entry.getValue(),entry.getKey()); } //遍历01字符串 String yuanStr = ""; String midyuan = ""; for(int i = 0 ; i<huffString.length();i++) { midyuan = midyuan + huffString.charAt(i)+""; if(map.get(midyuan)!=null) { yuanStr = yuanStr + map.get(midyuan); midyuan = ""; } } System.out.println(yuanStr.toString()); } //输出哈夫曼编码，code左为0，右为1;string存放编码，allCodes编码集 public static void qianHuffmanCodes(HuffNode rootNode,String code,String string,Map<String,String> codes) { String currents = string + code; if(rootNode.getC() == null) {//非叶子节点 //左递归 if(rootNode.getLeft()!=null) { qianHuffmanCodes(rootNode.getLeft(),"0",currents,codes); } //右递归 if(rootNode.getRight()!=null) { qianHuffmanCodes(rootNode.getRight(),"1",currents,codes); } }else{ codes.put(rootNode.getC()+"", currents.toString()); } } //前序输出哈夫曼树进行验证 public static void qian(HuffNode rootNode) { System.out.print(rootNode.c +":"+ rootNode.value+" "); if(rootNode.getLeft()!=null) { qian(rootNode.getLeft()); } if(rootNode.getRight()!=null) { qian(rootNode.getRight()); } } } class HuffNode implements Comparable<HuffNode>{ String c; int value; HuffNode left; HuffNode right; public HuffNode(String c,int value) { super(); this.c = c; this.value = value; } public String getC() { return c; } public void setC(String c) { this.c = c; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public HuffNode getLeft() { return left; } public void setLeft(HuffNode left) { this.left = left; } public HuffNode getRight() { return right; } public void setRight(HuffNode right) { this.right = right; } @Override public String toString() { return "HuffNode [c=" + c + ", value=" + value + "]"; } /** * 用集合管理节点时，进行排序的规则 * 从小到大排序 return this.value - o.value */ @Override public int compareTo(HuffNode o) { return this.value - o.value; } }