哈夫曼树与压缩

哈夫曼与压缩

带权路径长度（WPL）：
二叉树的带权（外部）路径长度是树的各叶结点所带的权值wi与该结点到根的路径长度li的乘积之和。

一、哈夫曼树
        哈夫曼树又称“最优树”，是带权路径长度达到最小的二叉树。

特点：在哈夫曼树中，权值越大的结点离根越近。

构建哈夫曼树：
1、由给定的n个权值，构造具有n棵二叉树的森林，其中每棵二叉树值有一个带权值的根结点其左右子树为空；
2、重复（直到森林中仅剩下一棵树）：
      1)在森林中选取两棵根结点权值最小的二叉树，作为左右子树构造一棵新的二叉树。设置新的二叉树的根节点的权值为其左右字数上根节点的权值之和；
      2)在森林中删去这两棵二叉树；
      3)把新的二叉树加入到森林中。
（该步骤重复次数为n-1，最终形成的哈夫曼树中共有2n-1个节点，起哄叶节点个数为n,度为2的结点个数为n-1个，没有度为1的结点。——严格二叉树/正则二叉树）

二、哈夫曼编码
以一段报文中出现的字符作为结点，各字符出现的次数作为权值，构建哈夫曼树，从根节点开始，对左子树分配代码0，右子树分配代码1，一直到达叶子结点为止，然后从根节点开始到每个叶子结点的路径上的代码连接起来，构成了哈夫曼编码。

因为哈夫曼树的带权路径长度是最小的，所以每个字符的编码长度乘以出现的次数的综合也是最小的，这样利用哈夫曼树构造的编码可以减少总编码的长度。

哈夫曼编码是一种无前缀编码（都由叶结点组成，路径不会重复）。解码时不会混淆。

三、压缩与解压缩
哈夫曼压缩时一种无损压缩方法，在压缩过程中不会丢失信息熵，而且在无损压缩算法中是最优的。对应用程序、重要资料等绝对不允许信息丢失的压缩场合，哈夫曼算法是非常好的选择。

计算机中存储一个字节型数据占用8个01位，因为计算机中所有数据都是转化为二进制位去存储的。所以我们就讲编码按照计算机的存储规则用为的方法写入进去就实现压缩。

压缩总体思路：
1、读文件，统计各字符的出现次数，并记录字符ASCII码的下标
2、对字符按照出现次数从小到大排序（优先队列）
3、构建哈夫曼树
4、遍历树，生成码表
5、写文件：
         1)头信息：出现的字符种类总数；
                   字符ASCII码，补了几个0，编码占几个byte，补零后的编码；
                   文件末尾补零的个数；
         2)写内容：每个字符不考虑补零，按照码表中的原始编码写入，
                    如果编码不够8位就读取下个字符将编码连接起来，
                    够8位就写入，剩下的编码再凑够8位写入，直到文件末尾补零。

import java.awt.BorderLayout;
import java.awt.Color;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.PriorityQueue;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JTextField;
/**
 * 哈夫曼压缩主类,实现压缩（英文可压缩）
 * @author 客
 *
 */
public class HuffmanTest extends JFrame{
	//压缩文章的路径
	static String path = "src\\lwq\\java\\HuffmanCode0729\\Untitled 1";
	//压缩到的路径
	static String newPath = "src\\lwq\\java\\HuffmanCode0729\\Untitled 2";
	//记录文章中字符和频率的数组，下标表示字符的ASCII码，数组内容表示该字符的出现次数
	int[] byteCount = new int[256];
	//哈夫曼树的根节点
	static hfmNode root;
	//传入“给叶子节点设置编码的方法”中
	static String s = "";
	//存储ascii为下标值的字符的编码对象,它是码表，是初始的编码，不补0的
	static Code SaveCode[] = new Code[256];
	//存储ascii为下标值的字符的编码需要的补0数
	int zeroCount[] = new int[256];
	FileInputStream fis;
	FileOutputStream fos;
         //记录文件内容所有的原始编码的字符串，用以统计文件末尾的补零个数
	int allString = 0;
         //文件末尾补零的个数
	int fileAddZero;
	
	/**
	 * 程序入口，主方法
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException{
		HuffmanTest huffmantest = new HuffmanTest();
		//遍历文件统计每个字符的出现次数，并且记录字符的ASCII码
		huffmantest.countWeight(path);
		//根据字符出现次数，建立哈夫曼树，方法末尾得到树的根节点
		huffmantest.createTree();
		//给叶子节点设置编码
		huffmantest.setCode(root, s);
		//写入文件头信息
		huffmantest.writeHead(newPath);
		//写入文件
		huffmantest.writeFile(path);
	}
	/**
	 * 读取文件统计字符和字符的出现频率
	 * @param path 要压缩的文件路径
	 * @throws IOException 
	 */
	public void countWeight(String path) throws IOException{
		fis = new FileInputStream(path);
		while(fis.available()>0){
			int i = fis.read();
			byteCount[i]++;//i是字符的ASCII码，数组内容是该字符的出现次数
		}
	}
	
	/**
	 * 根据字符频率，将字符创建成结点加入到优先队列中，建立哈夫曼树
	 */
	public void createTree(){
		//使用优先队列
		PriorityQueue<hfmNode> nodeQueue = new PriorityQueue<hfmNode>();		
		for(int i=0;i<byteCount.length;i++){
//			System.out.println(byteCount[i]);
			if(byteCount[i]!=0){//文件中出现次数不为0的字符,建立哈夫曼结点，存入队列
				hfmNode node = new hfmNode(i,byteCount[i]);				
				nodeQueue.add(node);
			}
		}		
		//根据优先队列的排序，构建哈夫曼树
		while(nodeQueue.size()>1){//当队列中的元素个数大于1
			//取得最小的两个,并删除掉
			hfmNode min1 = nodeQueue.poll();
			hfmNode min2 = nodeQueue.poll();
			//建立新的结点
			hfmNode result = new hfmNode(0,min1.getTimes()+min2.getTimes());
			//设置新结点的左右子结点
			result.setlChild(min1);
			result.setrChild(min2);
			//新结点加入到优先队列中
			nodeQueue.add(result);
		}
		//循环结束后队列中只有一个元素，该元素就是根节点，获取到但不删除
		root = nodeQueue.peek();
		System.out.println("根!"+root.toString());
	}
	/**
	 * 给叶子节点设置编码
	 * @param root
	 * @param s
	 */
	public void setCode(hfmNode root,String s){
		//如果左右子结点都为空，即为叶子节点
		if(root.getlChild()==null&&root.getrChild()==null){
			//实例化一个code对象，设置编码和长度
			Code huffman_code = new Code();
			huffman_code.setCode(s);
			//把编码code对象放到SaveCode数组中下标为字符ascii值
			SaveCode[root.getAscii()] = huffman_code;
			//输出编码信息
//			System.out.println(SaveCode[root.getAscii()].toString());
		}
		//如果左子结点不为空，递归
		if(root.getlChild()!=null){
			setCode(root.getlChild(),s+'0');
		}
		//如果右子结点不为空，递归
		if(root.getrChild()!=null){
			setCode(root.getrChild(),s+'1');
		}		
	}

	/**
	 * 写入文件头信息，写入的编码是补零后的编码
	 * 然后把码表写入文件头信息
	 * @throws IOException 
	 */
	public void writeHead(String newPath) throws IOException{
		fos = new FileOutputStream(newPath);
		//统计文件总共用到的字符总数，即编码个数
		int codeNum = 0;
		for(int i=0;i<256;i++){
			if(SaveCode[i]!=null){
				codeNum++;
				allString += byteCount[i]*SaveCode[i].getCode().length();
			}
		}
		//写入总文件中总共有多少个用到的字符
		fos.write(codeNum);
		System.out.println(codeNum);
		//循环输出码表，包括（按顺序）：字符、补了几个0、编码含有的byte个数、编码（整型）。
		for(int i=0;i<256;i++){
			//如果该字符在文件中出现过，即编码不为空
			if(SaveCode[i]!=null){
				//写入：字符的ASCII码值
				fos.write(i);	
				System.out.print(i+"\t"+(char)i);
				//第i个字符的补零数
				if(SaveCode[i].getCode().length()%8!=0){//如果编码字符串程度不是8的整倍数
					zeroCount[i] = 8-SaveCode[i].getCode().length()%8;//设置补零的个数	
				}else{//如果是8的整倍数
					zeroCount[i] = 0;
				}
				//写入：每个编码末尾补了几个0
				fos.write(zeroCount[i]);
				//补零后的编码，写入头信息
				String addZero = SaveCode[i].getCode();
				System.out.println(SaveCode[i].getCode()+"需要补零的个数"+zeroCount[i]);
				for(int j=0;j<zeroCount[i];j++){//循环次数为：需要补零的个数
					//每次在编码后补一个0
//					SaveCode[i].setCode(SaveCode[i].getCode()+'0');
					addZero = addZero+'0';
				}
				//在补0完成后，写入：编码有几个byte
				fos.write(addZero.length()/8);
//				System.out.print(addZero.length()/8+"\t");
				//对于补齐0的编码，每次取出一个字节
				for(int j=0;j<addZero.length()/8;j++){
					String subString = "";
					//取出一个字节中的8位赋值给codeString
					for(int k=j*8;k<(j+1)*8;k++){
						subString = subString+addZero.charAt(k);					
					}					
					//读取每个字节，将01串转化成整型数
					int cs = changeString(subString);				
					fos.write(cs);
//					System.out.print(cs+"  ");
				}//每个字符读取完毕
				
//				System.out.println("\t"+zeroCount[i]);
			}
		}
		if(allString%8==0){
			fos.write(0);
		}else{
			fileAddZero = 8-allString%8;
			fos.write(fileAddZero);
			System.out.println("文章末尾补零"+fileAddZero);
		}
	}
	/**
	 * 读文件并写入内容
	 * @throws IOException 
	 */
	public void writeFile(String path) throws IOException{
		System.out.println("xxxxxxx");
		//等待中的编码字符串
		String str = "";
		fis = new FileInputStream(path);
		//如果文件可读内容大于0
		while(fis.available()>0){
			//读取一个字节字符
			int i = fis.read();
			//得到该字符的码表中的编码----没有补零的，加入到等待中的字符串后
			str = str+SaveCode[i].getCode();
			
			System.out.println("!!~~!!"+str);
			
			//如果该编码长度大于等于8
			while(str.length()>=8){
				//截取8位编码的字符串
				String subString = "";
				for(int j=0;j<8;j++){
					subString = subString+str.charAt(j);
				}
				//读取每个字节，将01串转化成整型数
				int cs = changeString(subString);
				fos.write(cs);
				//删除str的前八位
				String tranString = str;
				str = "";
				for(int j=8;j<tranString.length();j++){
					str = str+tranString.charAt(j);
				}
			}
//			System.out.println("sssssssssssssssssssss"+str);
		}
		//文件末尾最后的字符串
		System.out.println("mm"+str);
		for(int t=0;t<fileAddZero;t++){
			str = str+'0';
		}
		System.out.println(str);
		//写入文件
		int cs = changeString(str);	
		fos.write(cs);
	}	
	/**
	 * 将8个字符的字符串转换成01串对应的整数
	 * @param s
	 * @return
	 */
	private int changeString(String s) {
		return ((int)s.charAt(0)-48)*128+((int)s.charAt(1)-48)*64
				+((int)s.charAt(2)-48)*32+((int)s.charAt(3)-48)*16
				+((int)s.charAt(4)-48)*8+((int)s.charAt(5)-48)*4
				+((int)s.charAt(6)-48)*2+((int)s.charAt(7)-48);
	}
}

压缩用到的其他类：

/**
 * 哈夫曼树中给叶子节点设置的编码类
 * @author 客
 *
 */
public class Code {
	//哈夫曼编码
	private String code = "";	
	/**
	 * 输出Code类对象的方法
	 */
	public String toString(){
		return "编码："+code+"  长度："+code.length();
	}
	/**
	 * 得到编码内容
	 * @return
	 */
	public String getCode() {
		return code;
	}
	/**
	 * 设置编码内容
	 * @param code
	 */
	public void setCode(String code) {
		this.code = code;
	}
}

/**
 * 哈夫曼树结点类
 * @author 客
 *
 */
public class hfmNode implements Comparable<hfmNode>{
	//字符的ASCII码值
	private int ascii;
	//字符的出现次数
	private int times;
	//当前结点的左子结点
	private hfmNode lChild;
	//当前结点的右子结点
	private hfmNode rChild;		
	/**
	 * 构造方法
	 * @param i ASCII的值
	 * @param times 文件中的出现次数
	 */
	public hfmNode(int ascii,int times){
		this.ascii = ascii;
		this.setTimes(times);
	}	
	/**
	 * 得到结点字符ASCII值得方法
	 * @return ASCII码值
	 */
	public int getAscii() {
		return ascii;
	}	
	/**
	 * 设置结点字符的ASCII值
	 * @param ascii
	 */
	public void setAscii(int ascii) {
		this.ascii = ascii;
	}	
	/**
	 * 得到当前结点字符出现次数的方法
	 * @return
	 */
	public int getTimes() {
		return times;
	}
	/**
	 * 设置当前结点字符出现次数的方法
	 * @param times
	 */
	public void setTimes(int times) {
		this.times = times;
	}
	/**
	 * 得到当前结点左孩子的方法
	 * @return 左子结点
	 */
	public hfmNode getlChild() {
		return lChild;
	}
	/**
	 * 设置当前结点左孩子的方法
	 * @param lChild
	 */
	public void setlChild(hfmNode lChild) {
		this.lChild = lChild;
	}
	/**
	 * 得到当前结点右孩子的方法
	 * @return 右子结点
	 */
	public hfmNode getrChild() {
		return rChild;
	}
	/**
	 * 设置当前结点右孩子的方法
	 * @param rChild
	 */
	public void setrChild(hfmNode rChild) {
		this.rChild = rChild;
	}
	/**
	 * 输出hfmNode类对象--哈夫曼结点的方法
	 */
	public String toString(){
		return "ascii="+(char)ascii+"             times="+times;
	}		
	/**
	 * 定义在队列中进行排序比较的属性
	 */
	public int compareTo(hfmNode o) {
		return times-o.getTimes();
	}	
}

解压缩总体思路：（怎么写进去的就要怎么读出来）
1、读取文件头信息：1)字符种类总数；
                   2)各字符信息：字符ASCII码，补零个数，占用byte数，编码
                     （在这过程中，需要把读到的编码转换成与码表中相同的编码）
                   3)文件末尾补零个数。
2、读取文件信息：读取每个字节转换成01串，前面补零成8位，
                加到等待匹配的字符串后，与码表中的编码匹配，写入。
                 读到文件末尾将加上去的0去掉。

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
/**
 * 实现文件解压缩
 * @author 客
 *
 */
public class OpenTest {
	//文件输入输出流
	FileInputStream fis;
	FileOutputStream fos;
	//被解压缩文件路径
	static String path = "src\\lwq\\java\\HuffmanCode0729\\Untitled 2";
	//解压缩后的文件路径
	static String newPath = "src\\lwq\\java\\HuffmanCode0729\\Untitled 3";
	//存储文件头信息--即各个字符信息的数组
	HeadInfo[] head;
	//文件末尾补零的数
	int fileAddZero;
	//记录总共有多少个字符
	int codeNum;

	public static void main(String[] args) throws IOException{
		OpenTest opentest = new OpenTest();
		//读取文件头信息
		opentest.readHead(path);
		//读取文件内容并输出
		opentest.readFile(path,newPath);		
	}	
	/**
	 * 读取文件头信息，按写入的顺序依次读出：
	 * 1、字符种类总数，
	 * 2、字符ASCII码，编码末尾补零数，字符占字节数，编码
	 * 3、文件末尾补零数
	 * 
	 * @throws IOException 
	 */
	public void readHead(String path) throws IOException{
		fis = new FileInputStream(path);
		
		//读取字符种类总数
		codeNum = fis.read();
		System.out.println(codeNum);
		//实例化记录文件头信息的数组，数组长度为字符种类总数
		head = new HeadInfo[codeNum];
		System.out.println("ascii\t字节数\t补零数\t编码");
		//以字符种类总数作为循环限制条件，读取每个字符的编码细则
		for(int i=0;i<codeNum;i++){
			//创建文件头信息对象
			HeadInfo info = new HeadInfo();
			
			//读取字符ASCII码，给对象设置ASCII码
			info.setAscii(fis.read());
			System.out.print(info.getAscii()+"\t"+(char)info.getAscii()+"  ");
			
			//读取编码末尾补零数，并给对象设置
			info.setZeroNum(fis.read());
			
			//读取编码所占字节数，给对象设置
			info.setByteNum(fis.read());
			System.out.print(info.getByteNum()+"\t");
			
			//读取当前编码的每个字节
			for(int j=0;j<info.getByteNum();j++){
				int code_int = fis.read();
				//读取到的整数转换成String---0,1串，该01串不会以0开头
				String code_string = Integer.toBinaryString(code_int);
//				System.out.println("s++"+code_string);
				int length = code_string.length();
				//01串不足8位的在前面补零
				if(length%8!=0){
					for(int k=0;k<8-length;k++){
						code_string = '0'+code_string;						
					}
				}
				//给info对象设置编码,含补零，每个字节的前面补零的01串相加
				info.setCode(info.getCode()+code_string);				
			}
			//得到完整的补零后的01串，即文件头信息存储的编码
			System.out.print(info.getZeroNum()+"\t");
			
			//根据编码末尾补零个数，恢复编码不补零的编码，即码表中存储的编码，
			for(int t=0;t<info.getZeroNum();t++){
				info.setCode(info.getCode().substring(0, info.getCode().length()-1));
			}
			System.out.println("去0后  "+info.getCode());	
			//将info对象添加到数组中
			head[i] = info;
		}
		//读取头信息的最后一个内容：文章末尾的补零的个数
		fileAddZero = fis.read();
		System.out.println("文件末尾补零"+fileAddZero);		
	}	
	/**
	 * 读取文件内容，写入新文件，完成解压缩
	 * @throws IOException 
	 */
	public void readFile(String path,String newPath) throws IOException{
		fos = new FileOutputStream(newPath);
		//等待转换的字符串
		String str = "";
		//当文件可读信息大于零时
		while(fis.available()>0){
			//读取一个字节，赋值给整数txt
			int txt = fis.read();
			//将该整数转换成01串，该字符串不会以0开头
			String temp = Integer.toBinaryString(txt);
			System.out.println(temp+"   nnnn");
			
			//给转换成的01串，前面补零成完整的8位的字符串
			int frontAddZero = temp.length()%8;
			if(frontAddZero!=0){
				for(int i=0;i<8-frontAddZero;i++){
					temp = '0'+temp;				
				}
			}
			System.out.println(temp+">>>>>>>>>>>>");
			//加到等待转换的字符串后，等待转换
			str = str+temp;
			System.out.println(str+" ！！！！等待转换！！！！");
		
			for(int j=0;j<codeNum;j++){
				//判断当前等待转换的字符串，是否以码表中的某个编码开头
				if(str.startsWith((head[j].getCode()))){
					//如果是，写入这个编码对应的字符
					System.out.println(str+"  ========  "+head[j].getCode());						
//					System.out.println("qqqq"+i);
					System.out.println((char)head[j].getAscii());
					fos.write(head[j].getAscii());
//					
					//将等待转换的字符串去掉已经写入的编码部分
					String tran = str;
					str = "";
					for(int k=head[j].getCode().length();k<tran.length();k++){
						str = str+tran.charAt(k);
					}
					//设置循环从头开始判断现在的str是否以某编码开头
					j = -1;
					//如果此时已经没有可读的文件信息了
					if(fis.available()==0){
						//将文件末尾添加的0的个数，在str中删去
						String tra = str;
						str = "";
						for(int t=0;t<tra.length()-fileAddZero;t++){
							str = str+tra.charAt(t);
						}
						//如果删去之后字符串空了，那么跳出循环，文件读取完毕
						if(str==""){
							break;
						}
						//如果str不为空，那么继续j=-1的地方循环判断是否以某编码开头
					}
				}			
			}//for循环	
		}//while循环
		//确认文件读取完毕
		System.out.println(str.length()+" 最后str的长度");
	}		
}

解压缩用到的其他类

/**
 * 文件解压缩时用到的文件头信息中每个字符的信息类
 * @author 客
 *
 */
public class HeadInfo {

	//字符ASCII码
	private int ascii;
	//字符编码占用字节数
	private int byteNum;
	//编码末尾补零数
	private int zeroNum;
	//编码
	private String code = "";
	
	/**
	 * 得到ASCII码
	 * @return
	 */
	public int getAscii() {
		return ascii;
	}
	
	/**
	 * 设置ASCII码 
	 * @param ascii
	 */
	public void setAscii(int ascii) {
		this.ascii = ascii;
	}
	
	/**
	 * 得到编码占字节数
	 * @return
	 */
	public int getByteNum() {
		return byteNum;
	}
	
	/**
	 * 设置编码占字节数
	 * @param byteNum
	 */
	public void setByteNum(int byteNum) {
		this.byteNum = byteNum;
	}
	
	/**
	 * 得到编码
	 * @return
	 */
	public String getCode() {
		return code;
	}
	
	/**
	 * 设置编码
	 * @param code
	 */
	public void setCode(String code) {
		this.code = code;
	}
	
	/**
	 * 得到编码末尾补零个数
	 * @return
	 */
	public int getZeroNum() {
		return zeroNum;
	}
	
	/**
	 * 设置编码末尾补零个数
	 * @param zeroNum
	 */
	public void setZeroNum(int zeroNum) {
		this.zeroNum = zeroNum;
	}	
}

据我测试，简单的英文压缩和解压缩应该没有问题，可能还有很多不足的地方，欢迎指正！

评论

2 楼 little_paper 2012-08-01  

别的不说 代码绝对规范 必须顶

1 楼 syi6 2012-08-01  

美女啊。。。浮出水面是必须的。。。。