二叉树路径长度_哈夫曼树的构造_哈夫曼树路径长度

哈夫曼与压缩

带权路径长度（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);
	}
}

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-33591-1.html