JAVA——赫夫曼编码-译码器(Huffman Coding)_哈夫曼编码译码java

基本概念

哈夫曼编码(Huffman Coding)：又称霍夫曼编码、赫夫曼编码-，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

源代码 

HTNode.java 

package huffman;
 
public class HTNode implements Comparable<HTNode> {
	int id;
	int weight;
	char code;
	int parent,lchild,rchild;
	public HTNode(int id) {
		this.id=id;
		this.weight=-1;
		this.code='\0';
		this.parent=-1;
		this.lchild=-1;
		this.rchild=-1;
	}
	public HTNode(int id,int weight) {
		this.id=id;
		this.weight=weight;
		this.code='\0';
		this.parent=-1;
		this.lchild=-1;
		this.rchild=-1;
	}
	public HTNode(int id,char code,int weight) {
		this.id=id;
		this.weight=weight;
		this.code=code;
		this.parent=-1;
		this.lchild=-1;
		this.rchild=-1;
	}
	public HTNode(int id,char code,int weight,int lchild,int rchild) {
		this.id=id;
		this.weight=weight;
		this.code=code;
		this.parent=-1;
		this.lchild=lchild;
		this.rchild=rchild;
	}
	public HTNode(int id,char code,int weight,int parent,int lchild,int rchild) {
		this.id=id;
		this.weight=weight;
		this.code=code;
		this.parent=parent;
		this.lchild=lchild;
		this.rchild=rchild;
	}
    public int compareTo(HTNode x) {
        if (x.weight < this.weight) {
            return 1;
        } else if (x.weight > this.weight) {
            return -1;
        }
        return 0;
    }
}

HuffmanTree.java

/**
 * 
 */
package huffman;
 
import java.util.*;
 
/**
 * @author ShenTuZhiGang
 * @version 1.0
 * @since 1.0
 */
public class HuffmanTree {
	private HTNode[] HT=null; 
	private final int MAX_INDEX=128;
	private char[] code;
	private int[] weight;
	private int num;
	private int node_tot;
	private String[] HuffmanCodeList;
	private static final char[] default_code= {' ','A','B','C','D','E','F','G','H','I','J','K','L','M','N',
	                                   		   'O','P','Q','R','S','T','U','V','W','X','Y','Z'};
	private static final int[] default_weight= {186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};	
	private static final int default_num=27;
	/**
	 * 
	 */
	public HuffmanTree() {
		create();
	}
	/**
	 * @param code - 字符集
	 * @param weight - 频数
	 */
	public HuffmanTree(char[] code,int[] weight) {
		create(code,weight);
	}
	public void create() {
		// TODO 自动生成的方法存根
		create(default_code,default_weight);
	}
	/**
	 * @param code - 字符集
	 * @param weight - 频数
	 */
	public void create(char[] code,int[] weight) {
		num=code.length;	//获取字符集字符总数
		node_tot=2*num-1;	//总共需要2num－1个节点
		PriorityQueue<HTNode> Q = new PriorityQueue<HTNode>();	//优先队列排序
		HT=new HTNode[node_tot+1];
		HT[0]=new HTNode(0);
		//给叶子结点赋值
		for(int i=1;i<=num;i++) {
			HT[i]=new HTNode(i,code[i-1],weight[i-1]);
			Q.add(HT[i]);
		}
		int id=num;
		//Huffman编码
		while(Q.size()>=2) {
			//找到两个权值最小的结点作为左右子树的根节点构造新的二叉树。
			HTNode s1=Q.remove();
			HTNode s2=Q.remove();
			id++;
			//创建新的节点
			//新节点的权值是两个子节点之和
			HT[id]=new HTNode(id,'\0',s1.weight+s2.weight,s1.id,s2.id);		
			s1.parent=s2.parent=id;		//将两个子节点的父节点设置为 id;
			//新节点重新放入队列
			Q.add(HT[id]);
		}
	}
	/**
	 * 从叶子到根逆向求每个字符的Huffman编码
	 */
	public void createHuffmanCode() {
		int start,c,f;
		char[] cd=new char[num];
		HuffmanCodeList=new String[num+1];	//分配内存空间
		//依次对所有字符编码
		for(int i=1; i<=num; i++){
	        start=num;
	        //从叶子到根逆向求编码
	        for(c=i,f=HT[i].parent;f!=-1;c=f,f=HT[f].parent) {
	        	 if(HT[f].lchild==c) {
	                 cd[--start]='0';
	             }else{
	                 cd[--start]='1';
	             }
	        }
	        //复制编码到Huffman编码表
	        HuffmanCodeList[i]=new String(cd,start,num-start);
	    }
	}
	/**
	 * @return HuffmanTreeString - HuffmanTree的字符串显示形式（括号法）
	 */
	@Override 
	public String toString() {
		return super.toString()+":[size="+node_tot+","+toBrackets(node_tot)+"]";
	}
	/**
	 * @param code_str - 需要编码的字符串
	 * @return encode - 完成Huffman编码的字符串
	 */
	public String enCode(String code_str) {
		int len=code_str.length();
		String encode=new String();
		//依次与所有字符编码开始匹配
		for(int i=0;i<len;i++) {
			for(int j=1;j<=num;j++) {
				//匹配成功
				if(code_str.charAt(i)==HT[j].code ) {
					encode=encode+HuffmanCodeList[j];
				}
			}
			
		}
		return encode;
	}
	/**
	 * @param code_str - 需要译码的字符串
	 * @return encode - 完成Huffman译码的字符串
	 */
	public String deCode(String code_str) {
		int len=code_str.length();
		String decode=new String();
		String temp=new String();
		//依次与所有字符编码开始匹配
		for(int i=0;i<len;i++) {
			temp=temp+code_str.charAt(i);
			for(int j=1;j<=num;j++) {
				//匹配成功
				if(HuffmanCodeList[j].equals(temp)) {
					decode=decode+HT[j].code;
					temp="";
					break;
				}
			}
			
		}
		return decode;
	}
	/**
	 * 输出每个字符的Huffman编码
	 */
	public void printHuffmanCodeList() {
		print("字符集总数："+HT.length);
		for(int i=1;i<=num;i++) {
			 print("\'"+HT[i].code+"\':"+HuffmanCodeList[i]);
		}
	}
	/**
	 * 调用{@link huffman.HuffmanTree#toBrackets(int) toBrackets(int root)}方法，生成HuffmanTree的括号法表示形式
	 * 括号法显示HuffmanTree
	 * @return resstr - HuffmanTree的括号法表示形式
	 */
	public String printHuffmanTree() {
		return toBrackets(node_tot);
	}
	/**
	 *  括号法显示HuffmanTree
	 * 递归法
	 * @param root - HuffmanTree ROOT
	 * @return resstr - HuffmanTree的括号法表示形式
	 */
	public String toBrackets(int root) {
		String resstr="";
		if(root!=-1){
	        resstr+=(HT[root].code=='\0')?HT[root].weight:HT[root].code;
	        if(HT[root].lchild!=-1||HT[root].rchild!=-1){
	        	resstr+="("+toBrackets(HT[root].lchild)+","+toBrackets(HT[root].rchild)+")";
	        }
	    }
		return resstr;
	}
	
	public static void print(Object obj) {
		System.out.println(obj);
	}
}

Main.java

/**
 * 
 */
package huffman;
 
/**
 * @author ShenTuZhiGang
 *
 */
public class Main {
 
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		HuffmanTree MyHT=new HuffmanTree();
		MyHT.createHuffmanCode();
		MyHT.printHuffmanCodeList();
		print(MyHT.enCode("THIS PROGRAME  IS  MY  FAVORITE"));
		print(MyHT.deCode("1101000101100011111100001001010011000100010101011001001011111101100011111111110010100011111111110011101011000001001001001101101010"));
		print(MyHT.toString());
		print(MyHT.printHuffmanTree());
			
	}
	public static void print(Object obj) {
		System.out.println(obj);
	}
}

运行结果

参考文章

https://blog.csdn.net/Wood_Du/article/details/80366094

https://shentuzhigang.blog.csdn.net/article/details/103198604