基本介绍哈夫曼编码又译为（哈夫曼编码）一种程序算法。哈夫曼编码是哈夫曼树在电信领域的经典应用场景之一。霍夫曼编码广泛用于数据文件压缩。压缩率通常在20%到90%之间。霍夫曼码是一种可变字长编码（VLC）。胡夫曼于1952年提出了一种编码方法，称为最优编码。原理分析通信领域的信息处理方法1：定长码如：ilikelikejavadoyoulikeajava共40个字符，包括空格，对应的ASCII码，二进制码以二进制传输如下图信息，总长度为359（包括空格）。通信领域信息处理方法2：变长编码ilikelikelikejavadoyoulikeajava共40个字符，包括空格。变长编码处理下图所示字符的编码不能作为其他字符编码的前缀。满足这种要求的编码称为前缀编码，即不能匹配重复的编码。通信领域信息处理方法3：哈夫曼编码ilikelikelikelikejavadoyoulikeajava共40个字符，包括空格。变长编码过程如下图所示，根据上述字符的出现次数构造哈夫曼树，以次数作为权重。根据哈夫曼树，给每个字符一个编码（前缀编码），向左的路径为0，向右的路径为1：代码如下：根据上面的哈夫曼编码，我们的“ilikelikelikejavadoYoulikeajava”字符串对应的编码（注意我们这里使用的是无损压缩）如下图。解释：原长度为359，压缩后为(359-133)/359=62.9%这种编码满足前缀编码，即该字符编码不能是其他字符编码的前缀。不会造成匹配歧义。霍夫曼编码是无损压缩！！注意：这个哈夫曼树可能会根据排序方式不同，所以对应的哈夫曼编码不完全一样，但是wpl是一样的，都是最小的，比如我们让每次生成的新二叉树总是always排在权重相同的二叉树的最后，则生成的二叉树为：创建对应的哈夫曼树根据哈夫曼编码压缩数据的原理，需要创建“ilikelikelikelikejavadoyoulikeajava》对应的哈夫曼树思想：首先创建一个Node节点，Node{data{storedata},weight(权重),left,right};get"我喜欢likelikejava你喜欢likeajava对应的byte[]数组";写一个方法，将要构建哈夫曼树的node节点放入List集合中；可以通过集合List创建对应的哈夫曼树；哈夫曼树应用案例将一个String字符串进行压缩和解压();System.out.println("contentBytes="+Arrays.toString(contentBytes));Listnodes=getNodes(contentBytes);//生成哈夫曼树NodehufffmanTreeRoot=createHufffmanTree(nodes);//生成哈夫曼编码表getCodes(huffmanTreeRoot,"",stringBuilder);byte[]huffmanCodeBytes=zip(contentBytes,huffmanCodes);System.out.println("huffmanCodeBytes="+Arrays.toString(huffmanCodeBytes));byte[]decode=decode(huffmanCodes,huffmanCodeBytes);System.out.println("哈夫曼解码对应数组"+newString(decode));/***contentBytes=[105,32,108,105,107,101,32,108,105,107,101,32,108,105,107,101,32,106,97,118,97,32,100,111,32,121,111,117,32,108,105,107,101,32,97,32,106,97,118,97]*huffmanCodeBytes=[-88,-65,-56,-65,-56,-65,-55,757,6,-24,-14,-117,-4,-60,-90,28]*Huffman解码对应数组ilikelikelikejavadoyoulikeajava*/}//完成数据的解压思路//1.设置huffmanCodeBytes[-88,-65,-56,-65,-56,-65,-55,77,-57,6,-24,-14,-117,-4,-60,-90,28]//重新转换为哈夫曼编码“101010001011111111001000101111....”对应的二进制字符串//2.哈夫曼编码对应的二进制字符串"101010001011111111001000101111...."=>对比哈夫曼编码表=>"ilikelikejavadoyoulikeajava"/***完成压缩数据解码**@paramhuffmanCodes哈夫曼编码表*@paramhuffmanBytes哈夫曼编码字节数组*@return原字符串对应的数组*/publicstaticbyte[]decode(MaphuffmanCodes,byte[]huffmanBytes){StringBuilderstringBuilder=newStringBuilder();for(inti=0;imap=newHashMap<>();for(Map.Entryentry:huffmanCodes.entrySet()){Bytek=entry.getKey();Stringv=entry.getValue();map.put(v,k);}Listlist=newArrayList<>();for(inti=0;i100000000|00000001=>100000001temp|=256;}//返回的是temp二进制补码StringbitStr=Integer.toBinaryString(temp);if(flag){//取后8位returnbitStr.substring(bitStr.length()-8);}else{returnbitStr;}}/***包原bytearraytoHuffmanbytearray**@parambytes*@return*/publicstaticbyte[]huffmanZip(byte[]bytes){Listnodes=getNodes(bytes);//创建哈夫曼树NodehufffmanTreeRoot=createHufffmanTree(nodes);//生成哈夫曼码getCodes(hufffmanTreeRoot,"",stringBuilder);//返回压缩后的哈夫曼码字节数组returnzip(bytes,huffmanCodes);}/***字符字符串对应的byte[]数组，通过哈夫曼码表，返回一个哈夫曼码压缩byte[]**@parambytes由哈夫曼码生成的byte[]*@paramhuffmanCodes对应原字符串*@returnreturnsbyte[]*/publicstaticbyte[]zip(byte[]bytes,MaphuffmanCodes){//使用huffmanCodes将bytes转换成Huffman编码对应的stringStringBuilderstringBuilder=newStringBuilder();for(byteb:bytes){stringBuilder.append(huffmanCodes.get(b));}//将"101010001011111111001000101111...."转换为byte[]//统计返回byte[]huffmanCodeByteslengthintlen;if(stringBuilder.length()%8==0){len=stringBuilder.length()/8;}else{len=stringBuilder.length()/8+1;}//压缩后创建存储byte[]数组byte[]huffmanCodeBytes=newbyte[len];intindex=0;for(inti=0;istringBuilder.length()){strByte=stringBuilder.substring(i);}else{strByte=stringBuilder.substring(i,i+8);}//将strByte转换成byte放入huffmanCodeByteshuffmanCodeBytes[index]=(byte)Integer.parseInt(strByte,2);index++;}returnhuffmanCodeBytes;}//生成哈夫曼树对应的哈夫曼码表//思路：//1.将哈夫曼码表存储在Map中，形式为32->01,97->100...staticMaphuffmanCodes=newHashMap<>();//2。生成哈夫曼码表时，需要拼接路径，定义一个StringBuilder存储某叶节点的路径staticStringBuilderstringBuilder=newStringBuilder();/***获取入节点节点的所有叶节点的哈夫曼码和将它们放入huffmanCodes集合中**@paramnode传入节点*@paramcode路径：左子节点为0，右子节点为1*@paramstringBuilder用于拼接路径*/publicstaticvoidgetCodes(Nodenode,Stringcode,StringBuilderstringBuilder){StringBuilderstringBuilder2=newStringBuilder(stringBuilder);stringBuilder2.append(code);if(node!=null){//判断当前节点是叶子节点还是非叶子节点if(node.data==null){//非叶子节点//递归处理到左边codes(node.left,"0",stringBuilder2);//递归处理getCodes(node.right,"1",stringBuilder2);}else{//叶子节点huffmanCodes.put(node.data,stringBuilder2.toString());}}}//前序遍历publicstaticvoidpreOrder(Noderoot){if(root!=null){root.preOrder();}else{System.out.println("哈夫曼树不能为空~~");}}/***将字节数组转换为节点集合**@parambytes字节数组*@return*/publicstaticListgetNodes(byte[]bytes){ArrayListnodes=newArrayList<>();//存储每个字节出现的次数Mapcounts=newHashMap<>();for(byteb:bytes){counts.merge(b,1,(a,b1)->a+b1);}//将每个键值对转换为一个节点对象，并添加到节点集合counts.forEach((k,v)->nodes.add(newNode(k,v)));returnnodes;}/***GenerateHuffmantree*@paramnodesincomingnodes*@return*/publicstaticNodecreateHufffmanTree(Listnodes){while(nodes.size()>1){//排序，从小到大Collections。sort(nodes);//(1)取出权重最小的节点(二叉树)NodeleftNode=nodes.get(0);//(2)取出权重次小的节点(二叉树)NoderightNode=nodes.get(1);//(3)新建一棵二叉树Nodeparent=newNode(null,leftNode.weight+rightNode.重量）;parent.left=左节点；parent.right=rightNode;//(4)从ArrayList中删除处理后的二叉树nodes.remove(leftNode);nodes.remove(rightNode);//(5)添加父节点nodes.add(parent);}//nodes的最后一个节点为哈夫曼树的根节点returnnodes.get(0);}}//创建节点withdataandweightclassNodeimplementsComparable{//存储数据本身，如'a'=>'97',''=>'32'Bytedata;//权重，表示一个字符出现的次数intweight;Nodeleft;Noderight;publicNode(Bytedata,intweight){this.data=data;this.weight=weight;}publicvoidpreOrder(){System.out.println(this);if(this.left!=null){this.left.preOrder();}if(this.right!=null){this.right.preOrder();}}@OverridepublicintcompareTo(Nodeo){//从小到大排序returnthis.weight-o.weight;}@OverridepublicStringtoString(){return"Node{"+"data="+data+",weight="+weight+'}';}}哈夫曼压缩文件注意事项如果文件本身已经压缩过，那么使用哈夫曼编码再压缩效率不会有明显变化，比如视频、ppt等文件哈夫曼编码按字节处理，所以它可以处理所有文件（二进制文件，文本文件）。如果文件中的重复数据不多，压缩效果不会很明显。
