思路：
- 把字符串转化为字节数组，对字符串中不同字符出现的次数进行统计，统计结果存储到一个Map中
- 键为字符字节,值为此字符字节在字符串中出现的次数
- 创建赫夫曼树
- 读取每一个字符字节的路径方向值，把字符串中的每个字符用路径方向值来表示
- 把得到的二进制字符串切分为有符号字节存储到字节数组中
- 打印原字符串，二进制字符串，字节数组
代码如下：
//Node类用于创建树结构
public class Node implements Comparable<Node>{Byte data;int weight;Node left;Node right;public Node(Byte data, int weight){this.data = data; this.weight = weight;}@Overridepublic String toString() {return "Node [data=" + data + ", weight=" + weight + "]";}@Overridepublic int compareTo(Node nodes) {// TODO Auto-generated method stubreturn nodes.weight - this.weight;}
}public class TestHuffmanCode {public static void main(String[] args) {//定义一个字符串String msg ="can you can a can as a can cannr can a can";//定义一个字节数组byte[] bytes = msg.getBytes();//进行赫夫曼编码byte[] byt = huffmanZip(bytes);//循环遍历字节数组中的值，也即赫夫曼编码值for(byte b:byt) {System.out.print(b+" ");}}/***进行赫夫曼编码的方法****/private static byte[] huffmanZip(byte[] bytes){//判断字节是否为空if(bytes ==null) {return null;}//先统计每一个byte出现的次数,并放入一个集合中List<Node> nodes = getNodes(bytes);//创建一个赫夫曼树Node tree = createHuffmanTree(nodes);//创建一个赫夫曼编码表Map<Byte, String>huffCodes = getCodes(tree); //压缩编码byte[] byt=zip(bytes,huffCodes);return byt;}//用于标识最后一个子字符串的长度static int bitFlag =0;//把二进制字符串转换为有符号十进制数存储到字节数组中private static byte[] zip(byte[] bytes, Map<Byte,String>huffCodes){//用于存储二进制字符串StringBuilder sb = new StringBuilder();//把需要压缩的byte数组处理成一个二进制的字符串for(byte b:bytes){sb.append(huffCodes.get(b));}//输出二进制字符串System.out.println(sb.toString());//定义长度用来存储压缩后的字符串int len;//判断二进制字符串能划分为几个字节if(sb.length()%8==0){len = sb.length()/8; }else{len = sb.length()/8 + 1;}//用于记录byte数组中的下标值int index = 0;//用于存储压缩后的bytebyte[] by = new byte[len];//循环遍历二进制字符串for(int i =0;i<sb.length();i+=8){//用于存储子字符串String strByte;if(i+8>sb.length()){//赋值最后一个字符串strByte = sb.substring(i);//用于记录最后一个二进制字符串的长度bitFlag = strByte.length();//把二进制字符串转换为有符号十进制数by[index] = (byte) Integer.parseInt(strByte,2); }else{//按照每八位截取二进制字符串strByte = sb.substring(i,i+8);//把二进制字符串转换为有符号十进制数by[index] = (byte) Integer.parseInt(strByte,2);index++;}} return by;}//用来存储符号的路径方向static StringBuilder sb = new StringBuilder();//用于存储符号字节值与对应的符号路径方向值static Map<Byte,String>huffCodes = new HashMap<>();//用于得到符号字节值与对应的符号路径方向值private static Map<Byte, String>getCodes(Node tree){//判断赫夫曼树是否为空 if(tree==null){return null;}//调用得到路径方向值方法getCodes(tree.left,"0",sb);getCodes(tree.right,"1",sb);return huffCodes; }//得到路径值private static void getCodes(Node node, String code,StringBuilder sb){//定义一个StringBuilder，把参数传进去 StringBuilder sb2 = new StringBuilder(sb);//追加路径值sb2.append(code);//递归getCodes方法if(node.data == null){getCodes(node.left,"0",sb2);getCodes(node.right,"1",sb2);}else{huffCodes.put(node.data,sb2.toString());}} private static Node createHuffmanTree(List<Node>nodes){ while(nodes.size()>1){//排序Collections.sort(nodes);//创建左子树Node left = nodes.get(nodes.size()-1);//创建右子树Node right = nodes.get(nodes.size()-2);//创建双亲节点Node parent = new Node(null, left.weight+right.weight);//把左子树赋值给双亲节点的左子树parent.left = left;//把右子树赋值给双亲节点的右子树parent.right = right;//去除左右子树nodes.remove(left);nodes.remove(right);//把双亲节点加入Node中nodes.add(parent);} return nodes.get(0);}private static List<Node> getNodes(byte[] bytes){//声明一个Node类型的动态数组List<Node> nodes = new ArrayList<>();//定义一个Map，用于存储一个字符值和此字符出现的次数 Map<Byte,Integer> counts = new HashMap<>();//循环遍历字节数组for(byte b:bytes){//得到Map中的value值,做一个标记或者记录Integer count = counts.get(b);if(count==null){//把子节数组中的数据存到Map中counts.put(b,1);}else{//依次把子节数组中的数据存入Map中counts.put(b,count+1);}}//把键值对存入到Node类型的Node中 for(Map.Entry<Byte,Integer>entry:counts.entrySet()){nodes.add(new Node(entry.getKey(),entry.getValue()));}//System.out.println(nodes);return nodes; }
}