详解Huffman编码算法之Java实现
Huffman编码介绍
Huffman编码处理的是字符以及字符对应的二进制的编码配对问题，分为编码和解码，目的是压缩字符对应的二进制数据长度。我们知道字符存贮和传输的时候都是二进制的(计算机只认识0/1)，那么就有字符与二进制之间的mapping关系。字符属于字符集(Charset),字符需要通过编码(encode)为二进制进行存贮和传输，显示的时候需要解码(decode)回字符，字符集与编码方法是一对多关系(Unicode可以用UTF-8,UTF-16等编码)。理解了字符集，编码以及解码，满天飞的乱码问题也就游刃而解了。以英文字母小写a为例,ASCII编码中，十进制为97，二进制为01100001。ASCII的每一个字符都用8个Bit(1Byte)编码，假如有1000个字符要传输，那么就要传输8000个Bit。问题来了，英文中字母e的使用频率为12.702%，而z为0.074%，前者是后者的100多倍，但是确使用相同位数的二进制。可以做得更好，方法就是可变长度编码，指导原则就是频率高的用较短的位数编码，频率低的用较长位数编码。Huffman编码算法就是处理这样的问题。
Huffman编码Java实现
Huffman编码算法主要用到的数据结构是完全二叉树(fullbinarytree)和优先级队列。后者用的是Java.util.PriorityQueue，前者自己实现(都为内部类)，代码如下:
staticclassTree{
privateNoderoot;
publicNodegetRoot(){
returnroot;
}
publicvoidsetRoot(Noderoot){
this.root=root;
}
}
staticclassNodeimplementsComparable<Node>{
privateStringchars="";
privateintfrequence=0;
privateNodeparent;
privateNodeleftNode;
privateNoderightNode;
@Override
publicintcompareTo(Noden){
returnfrequence-n.frequence;
}
publicbooleanisLeaf(){
returnchars.length()==1;
}
publicbooleanisRoot(){
returnparent==null;
}
publicbooleanisLeftChild(){
returnparent!=null&&this==parent.leftNode;
}
publicintgetFrequence(){
returnfrequence;
}
publicvoidsetFrequence(intfrequence){
this.frequence=frequence;
}
publicStringgetChars(){
returnchars;
}
publicvoidsetChars(Stringchars){
this.chars=chars;
}
publicNodegetParent(){
returnparent;
}
publicvoidsetParent(Nodeparent){
this.parent=parent;
}
publicNodegetLeftNode(){
returnleftNode;
}
publicvoidsetLeftNode(NodeleftNode){
this.leftNode=leftNode;
}
publicNodegetRightNode(){
returnrightNode;
}
publicvoidsetRightNode(NoderightNode){
this.rightNode=rightNode;
}
}
统计数据
既然要按频率来安排编码表，那么首先当然得获得频率的统计信息。我实现了一个方法处理这样的问题。如果已经有统计信息，那么转为Map<Character,Integer>即可。如果你得到的信息是百分比，乘以100或1000，或10000。总是可以转为整数。比如12.702%乘以1000为12702，Huffman编码只关心大小问题。统计方法实现如下：
publicstaticMap<Character,Integer>statistics(char[]charArray){
Map<Character,Integer>map=newHashMap<Character,Integer>();
for(charc:charArray){
Charactercharacter=newCharacter(c);
if(map.containsKey(character)){
map.put(character,map.get(character)+1);
}else{
map.put(character,1);
}
}
returnmap;
}
构建树
构建树是Huffman编码算法的核心步骤。思想是把所有的字符挂到一颗完全二叉树的叶子节点，任何一个非页子节点的左节点出现频率不大于右节点。算法为把统计信息转为Node存放到一个优先级队列里面，每一次从队列里面弹出两个最小频率的节点，构建一个新的父Node(非叶子节点),字符内容刚弹出来的两个节点字符内容之和，频率也是它们的和，最开始的弹出来的作为左子节点，后面一个作为右子节点，并且把刚构建的父节点放到队列里面。重复以上的动作N-1次，N为不同字符的个数(每一次队列里面个数减1)。结束以上步骤，队列里面剩一个节点，弹出作为树的根节点。代码如下:
privatestaticTreebuildTree(Map<Character,Integer>statistics,
List<Node>leafs){
Character[]keys=statistics.keySet().toArray(newCharacter[0]);
PriorityQueue<Node>priorityQueue=newPriorityQueue<Node>();
for(Charactercharacter:keys){
Nodenode=newNode();
node.chars=character.toString();
node.frequence=statistics.get(character);
priorityQueue.add(node);
leafs.add(node);
}
intsize=priorityQueue.size();
for(inti=1;i<=size-1;i++){
Nodenode1=priorityQueue.poll();
Nodenode2=priorityQueue.poll();
NodesumNode=newNode();
sumNode.chars=node1.chars+node2.chars;
sumNode.frequence=node1.frequence+node2.frequence;
sumNode.leftNode=node1;
sumNode.rightNode=node2;
node1.parent=sumNode;
node2.parent=sumNode;
priorityQueue.add(sumNode);
}
Treetree=newTree();
tree.root=priorityQueue.poll();
returntree;
}
编码
某个字符对应的编码为，从该字符所在的叶子节点向上搜索，如果该字符节点是父节点的左节点，编码字符之前加0，反之如果是右节点，加1，直到根节点。只要获取了字符和二进制码之间的mapping关系，编码就非常简单。代码如下:
publicstaticStringencode(StringoriginalStr,
Map<Character,Integer>statistics){
if(originalStr==null||originalStr.equals("")){
return"";
}
char[]charArray=originalStr.toCharArray();
List<Node>leafNodes=newArrayList<Node>();
buildTree(statistics,leafNodes);
Map<Character,String>encodInfo=buildEncodingInfo(leafNodes);
StringBufferbuffer=newStringBuffer();
for(charc:charArray){
Charactercharacter=newCharacter(c);
buffer.append(encodInfo.get(character));
}
returnbuffer.toString();
}
privatestaticMap<Character,String>buildEncodingInfo(List<Node>leafNodes){
Map<Character,String>codewords=newHashMap<Character,String>();
for(NodeleafNode:leafNodes){
Charactercharacter=newCharacter(leafNode.getChars().charAt(0));
Stringcodeword="";
NodecurrentNode=leafNode;
do{
if(currentNode.isLeftChild()){
codeword="0"+codeword;
}else{
codeword="1"+codeword;
}
currentNode=currentNode.parent;
}while(currentNode.parent!=null);
codewords.put(character,codeword);
}
returncodewords;
}
解码
因为Huffman编码算法能够保证任何的二进制码都不会是另外一个码的前缀，解码非常简单，依次取出二进制的每一位，从树根向下搜索，1向右，0向左，到了叶子节点(命中)，退回根节点继续重复以上动作。代码如下:
publicstaticStringdecode(StringbinaryStr,
Map<Character,Integer>statistics){
if(binaryStr==null||binaryStr.equals("")){
return"";
}
char[]binaryCharArray=binaryStr.toCharArray();
LinkedList<Character>binaryList=newLinkedList<Character>();
intsize=binaryCharArray.length;
for(inti=0;i<size;i++){
binaryList.addLast(newCharacter(binaryCharArray[i]));
}
List<Node>leafNodes=newArrayList<Node>();
Treetree=buildTree(statistics,leafNodes);
StringBufferbuffer=newStringBuffer();
while(binaryList.size()>0){
Nodenode=tree.root;
do{
Characterc=binaryList.removeFirst();
if(c.charValue()=='0'){
node=node.leftNode;
}else{
node=node.rightNode;
}
}while(!node.isLeaf());
buffer.append(node.chars);
}
returnbuffer.toString();
}
测试以及比较
以下测试Huffman编码的正确性(先编码，后解码，包括中文)，以及Huffman编码与常见的字符编码的二进制字符串比较。代码如下:
publicstaticvoidmain(String[]args){
StringoriStr="Huffmancodescompressdataveryeffectively:savingsof20%to90%aretypical,"
+"dependingonthecharacteristicsofthedatabeingcompressed.中华崛起";
Map<Character,Integer>statistics=statistics(oriStr.toCharArray());
StringencodedBinariStr=encode(oriStr,statistics);
StringdecodedStr=decode(encodedBinariStr,statistics);
System.out.println("Originalsstring:"+oriStr);
System.out.println("Huffmanencoedbinarystring:"+encodedBinariStr);
System.out.println("decodedstringfrombinariystring:"+decodedStr);
System.out.println("binarystringofUTF-8:"
+getStringOfByte(oriStr,Charset.forName("UTF-8")));
System.out.println("binarystringofUTF-16:"
+getStringOfByte(oriStr,Charset.forName("UTF-16")));
System.out.println("binarystringofUS-ASCII:"
+getStringOfByte(oriStr,Charset.forName("US-ASCII")));
System.out.println("binarystringofGB2312:"
+getStringOfByte(oriStr,Charset.forName("GB2312")));
}
publicstaticStringgetStringOfByte(Stringstr,Charsetcharset){
if(str==null||str.equals("")){
return"";
}
byte[]byteArray=str.getBytes(charset);
intsize=byteArray.length;
StringBufferbuffer=newStringBuffer();
for(inti=0;i<size;i++){
bytetemp=byteArray[i];
buffer.append(getStringOfByte(temp));
}
returnbuffer.toString();
}
publicstaticStringgetStringOfByte(byteb){
StringBufferbuffer=newStringBuffer();
for(inti=7;i>=0;i--){
bytetemp=(byte)((b>>i)&0x1);
buffer.append(String.valueOf(temp));
}
returnbuffer.toString();
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。