`
1641606815
  • 浏览: 39625 次
  • 性别: Icon_minigender_1
  • 来自: 湖南
社区版块
存档分类
最新评论

java实现哈夫曼压缩

阅读更多
哈夫曼压缩的原理:
通过统计文件中每个字节出现的频率,将8位的01串转换为位数较短的哈夫曼编码.
其中哈夫曼编码是根据文件中字节出现的频率构建的,其中出现频率越高的字节,其路径长度越短;
出现频率越低的字节其路径长度越长.从而达到压缩的目的.
如何构造哈夫曼树?
一.  定义字节类
        我的字节类定义了一下属性
        public int data;//节点数据
public int weight;//该节点的权值
public int point;//该节点所在的左右位置 0-左 1-右
private NodeData parent;//父节点引用
private NodeData left;//左节点引用
private NodeData right;//右节点引用
二.建哈夫曼树
1.定义一个存储字节信息的数组: int array_Bytes[256];
  其中数组的下标[0,256)代表字节数值(一个字节8位,其值在[0,256)范围内);数组存储字节出现的次数.
2.遍历要压缩的文件,统计字节出现的次数.
  InputStream data = new FileInputStream(path);
  /******** 文件中字符个数 ********/
  int number = data.available();
  for (int i = 0; i < number; i++) {
int b = data.read();
array_Bytes[b] ++;
  }
data.close();
3.将字节类对象存入优先队列
4.运用HashMap 构造码表
哈夫曼压缩代码如下:
1.字节类
package compressFile;
/**
 * 节点数据
 * 功能:定义数据,及其哈夫曼编码
 * @author Andrew
 *
 */
public class NodeData {
	public NodeData(){
		
	}
	public int data;//节点数据
	public int weight;//该节点的权值
	public int point;//该节点所在的左右位置 0-左 1-右
	private NodeData parent;
	private NodeData left;
	private NodeData right;
	
	public int getData(){
		return data;
	}
	public NodeData getParent() {
		return parent;
	}
	public void setParent(NodeData parent) {
		this.parent = parent;
	}
	public NodeData getLeft() {
		return left;
	}
	public void setLeft(NodeData left) {
		this.left = left;
	}
	public NodeData getRight() {
		return right;
	}
	public void setRight(NodeData right) {
		this.right = right;
	}
}

2.统计字节的类,并生成码表
package compressFile;

import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;



/**
 * 统计指定文件中每个字节数 功能:定义数组,将文件中的字节类型及个数写入数组
 * 创建优先队列和哈夫曼树
 * @author Andrew
 * 
 */
public class StatisticBytes {

	
	/**
	 * 第一步:
	 * 统计文件中字节的方法
	 * 
	 * @param path
	 *            所统计的文件路径
	 * @return 字节个数数组
	 */
	private int[] statistic(String path) {
		/******储存字节数据的数组--索引值代表字节类型-存储值代表权值******/
		int[] array_Bytes = new int[256];
		try {
			InputStream data = new FileInputStream(path);
			BufferedInputStream buffered = new BufferedInputStream(data);
			/******** 文件中字符个数 ********/
			int number = data.available();
			System.out.println("字节个数》》》"+number);
			for (int i = 0; i < number; i++) {
				int b = data.read();
				array_Bytes[b] ++;
			}
			
			data.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return array_Bytes;
	}
	/**
	 * 第二步:
	 * 根据统计的字节数组创建优先队列
	 * @param array  统计文件字节的数组
	 * @return       优先队列
	 */
	private PriorityQueue<NodeData> createQueue(int[] array){
		//定义优先队列,根据数据的权值排序从小到大
		PriorityQueue<NodeData> queue = 
				new PriorityQueue<NodeData>(array.length,new Comparator<NodeData>(){
			public int compare(NodeData o1, NodeData o2) {
				return o1.weight - o2.weight;
			}
		});
		
		for(int i=0; i<array.length; i++){
			if(0 != array[i]){
				NodeData node = new NodeData();
				node.data = i;//设置该节点的数据
				node.weight = array[i];//设置该节点的权值
				queue.add(node);
			}
		}
		return queue;
	}
	/**
	 * 第三步:
	 * 根据优先队列创建哈夫曼树
	 * @param queue   优先队列   
	 * @return		   哈夫曼树根节点
	 */
	private NodeData createTree(PriorityQueue<NodeData> queue){
		while(queue.size() > 1){
			
			NodeData left = queue.poll();//取得左节点
			NodeData right = queue.poll();//取得右节点
			
			NodeData root = new NodeData();//创建新节点
			root.weight = left.weight + right.weight;
			
			root.setLeft(left);
			root.setRight(right);
			left.setParent(root);
			right.setParent(root);
			
			left.point = 0;
			right.point = 1;
			
			queue.add(root);
		}
		NodeData firstNode = queue.poll();
		return firstNode;
	}
	/**
	 * 第四步:
	 * 寻找叶节点并获得哈夫曼编码
	 * @param root   根节点
	 */
	private void achievehfmCode(NodeData root){
		
		if(null == root.getLeft() && null == root.getRight()){
			array_Str[root.data] = this.achieveLeafCode(root);
			/**
			 * 
			 * 得到将文件转换为哈夫曼编码后的文集长度
			 * 文件长度 = 一种编码的长度 * 该编码出现的次数
			 */
			WriteFile.size_File += (array_Str[root.data].length())*(root.weight);
		}
		if(null != root.getLeft()){
			achievehfmCode(root.getLeft());
		}
		if(null != root.getRight()){
			achievehfmCode(root.getRight());
		}
	}
	/**
	 * 根据某叶节点获得该叶节点的哈夫曼编码
	 * @param leafNode   叶节点对象
	 */
	private String achieveLeafCode(NodeData leafNode){
		String str = "";
		/*****************存储节点 01 编码的队列****************/
		List<Integer> list_hfmCode =  new ArrayList<Integer>();
		list_hfmCode.add(leafNode.point);
		NodeData parent = leafNode.getParent();
		
		while(null != parent){
			list_hfmCode.add(parent.point);
			parent = parent.getParent();
		}
		
		int size = list_hfmCode.size();
		for(int i=size-2; i>=0; i--){
			str += list_hfmCode.get(i);
		}
		System.out.println(leafNode.weight+"的哈夫曼编码为>>>"+str);
		return str;
	}
	/**
	 * 第五步:
	 * 根据获得的哈夫曼表创建 码表
	 * Integer 为字节byte [0~256)
	 * String  为哈夫曼编码
	 * @return	码表
	 */
	public Map<Integer,String> createMap(){
		int[] hfm_Codes = this.statistic("F:\\JAVA\\压缩前.txt");//获得文件字节信息
		PriorityQueue<NodeData> queue = this.createQueue(hfm_Codes);//获得优先队列
		/*
		 * 获得哈夫曼树的根节点,
		 * this.createTree(queue)方法调用之后(含有poll()),queue.size()=0
		 */
		NodeData root = this.createTree(queue);
		this.achievehfmCode(root);//获得哈夫曼编码并将其存入数组中
		
		Map<Integer,String> map = new HashMap<Integer,String>();
		for(int i=0; i<256; i++){
			if(null != array_Str[i]){
				map.put(i, array_Str[i]);
			}
		}
		return map;
	}
	/**
	 * 存储字节哈夫曼编码的数组
	 * 下标:字节数据
	 * 元素:哈夫曼编码
	 */
	public String[] array_Str = new String[256];
}

3.将码表写入压缩文件并压缩正文
package compressFile;

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.DataOutputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
 * 将码表和文件写入新的文件中
 * @author Andrew
 * 
 */
public class WriteFile {

	// 实例化创建码表类对象
	private StatisticBytes statistic = new StatisticBytes();
	private Map<Integer, String> map = statistic.createMap();// 获得码表
	// 字节接收变量,接收哈夫曼编码连接够8位时转换的字节
	private int exmpCode;
	public static int size_File;

	public static void main(String[] args) {
		WriteFile writeFile = new WriteFile();
		writeFile.init();
	}

	private void init() {

		String filePath = "F:\\JAVA\\压缩后.txt";
		this.writeFile(filePath);
	}

	/**
	 * 第一步: 向文件中写入码表
	 * 
	 * @param dataOut
	 *            基本数据流
	 */
	private void writeCodeTable(DataOutputStream dataOut) {
		Set<Integer> set = map.keySet();
		Iterator<Integer> p = set.iterator();

		try {
			//向文件中写入码表的长度
			dataOut.writeInt(map.size());
			while (p.hasNext()) {
				Integer key = p.next();
				String hfmCode = map.get(key);

				dataOut.writeInt(key);//写入字节
				//写入哈夫曼编码的长度
				dataOut.writeByte(hfmCode.length());
				for(int i=0; i<hfmCode.length(); i++){
					dataOut.writeChar(hfmCode.charAt(i));//写入哈夫曼编码
				}
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	/**
	 * 第二步: 向压缩文件中写入编码
	 * 
	 * @param path
	 */
	private void writeFile(String path) {

		try {
			// 输入流
			FileInputStream in = new FileInputStream("F:\\JAVA\\压缩前.txt");
			BufferedInputStream bIn = new BufferedInputStream(in);
			// 输出流
			FileOutputStream out = new FileOutputStream(path);
			DataOutputStream dataOut = new DataOutputStream(out);
			BufferedOutputStream bOut = new BufferedOutputStream(out);
			// 向文件中写入码表
			this.writeCodeTable(dataOut);
			/********************写入补零个数*********************/
			if(0 != size_File % 8){
				dataOut.writeByte(8 - (size_File % 8));
			}
			
			String transString = "";//中转字符串,存储字符串直到size大于8
			String waiteString = "";//转化字符串,
			
			int size_File = in.available();
			for(int i=0; i<size_File; i++){
				int j = bIn.read();
				System.out.println("]]]]]]]]]]]>>");
				waiteString = this.changeStringToByte(transString + statistic.array_Str[j]);
				if(waiteString != ""){	
					bOut.write(exmpCode);
					transString = waiteString;
				}else{
					transString += statistic.array_Str[j];
				}
			}
			if("" != transString){
				int num = 8-transString.length()%8;
				for(int i=0; i<num; i++){
					transString += 0;
				}
			}
			transString = this.changeStringToByte(transString);
			bOut.write(exmpCode);
			
			bIn.close();
			bOut.flush();
			bOut.close();
			out.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	/**
	 * 附属第二步:
	 * 将字符串转化为byte
	 * 
	 * @param str
	 *            要转化的字符串
	 * @return 如果str的长度大于8返回一个截取前8位后的str
	 *          否则返回""
	 */
	private String changeStringToByte(String str) {
		if (8 <= str.length()) {
			exmpCode = ((str.charAt(0) - 48) * 128
					+ (str.charAt(1) - 48) * 64 + (str.charAt(2) - 48) * 32
					+ (str.charAt(3) - 48) * 16 + (str.charAt(4) - 48) * 8
					+ (str.charAt(5) - 48) * 4  + (str.charAt(6) - 48) * 2 
					+ (str.charAt(7) - 48));
			str = str.substring(8);
			return str;
		}
		return "";
	}
}


二.哈夫曼解压
   原理:将压缩的逆向,即你是如何压缩的就怎样去解压。相当于你根据自己定义的协议进行压缩与解压缩文件。
代码如下:
package decompressionFile;

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 解压文件 从压缩文件中读入数据解压
 * 
 * @author Andrew
 * 
 */
public class ReadFile {
	/**
	 * 码表 Integter: 字节 [0,255) String: 哈夫曼编码
	 */
	private Map<Integer, String> code_Map = new HashMap<Integer, String>();

	public static void main(String[] args) {
		ReadFile readFile = new ReadFile();
		readFile.readFile();
	}

	/**
	 * 第一步: 从文件中读出码表
	 * 
	 * @param dataInput
	 *            基本数据输入流
	 * 
	 */
	private void readMap(DataInputStream dataInput) {

		try {
			// 读出码表的长度
			int size_Map = dataInput.readInt();
			/**************** 读出码表信息 ************************************/
			for (int i = 0; i < size_Map; i++) {
				int data = dataInput.readInt();// 读入字节信息
				String str = "";// 哈夫曼编码
				// 哈夫曼编码长度,存储时以字符写入
				byte codeSize = dataInput.readByte();
				for (byte j = 0; j < codeSize; j++) {
					str += dataInput.readChar();
				}
				System.out.println("&&&&&&&&&&>>>>"+data+"!!!!!!!>>"+str);
				code_Map.put(data, str);
			}
			/***************************************************************/
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	/**
	 * 第二步: 解压正式文件
	 */
	private void readFile() {
		try {
			// 文件输入流
			InputStream input = new FileInputStream("F:\\JAVA\\压缩后.txt");
			// BufferedInputStream bIn = new BufferedInputStream(input);
			DataInputStream dInput = new DataInputStream(input);
			// 调用读出码表的方法
			this.readMap(dInput);
			byte zerofill = dInput.readByte();// 读出文件补零个数
			System.out.println("补零个数》》》>>>>"+zerofill);
			// 文件输出流
			OutputStream out = new FileOutputStream("F:\\JAVA\\解压后.txt");
			
			String transString = "";//接收用于匹配码表中哈夫曼编码的字符串
			String waiteString = "";//接收截取哈夫曼编码后剩余的字符串
			
			/***********************************不耗内存的方法*****************************************/
			int readCode = input.read();//从压缩文件中读出一个数据
			int size = input.available();
			for(int j=0; j<=size; j++){
				System.out.println("readCodereadCodereadCode》》>>>>"+readCode);
				waiteString += this.changeIntToBinaryString(readCode);//将读到的整数转化为01字符串
				for(int i=0; i<waiteString.length(); i++){
					//将从文件中读出的01串一个一个字节的截取添加与码表中的哈夫曼编码比较
					transString += waiteString.charAt(i);
					if(this.searchHC(transString, out)){
//						waiteString = waiteString.substring( i+1 );
						transString = "";
					}
				}
				waiteString = "";
				readCode = input.read();
				if(j == size-1){
					break;
				}
			}
			/************************************处理最后一个字***************************************/
//			int lastByte = input.read();
			String lastWord = this.changeIntToBinaryString(readCode);
			waiteString = transString + lastWord.substring(0, 8-zerofill);
			transString = "";
			for(int i=0; i<waiteString.length(); i++){
				//将从文件中读出的01串一个一个字节的截取添加与码表中的哈夫曼编码比较
				transString += waiteString.charAt(i);
				if(this.searchHC(transString, out)){
//					waiteString = waiteString.substring( i+1 );
					transString = "";
				}
			}
//			this.searchHC(transString, out);
			/***********************************队列法,耗内存****************************************/
//			int readCode = input.read();//从压缩文件中读出一个数据
//			List<Character> list = new ArrayList<Character>();
//			while(-1 != readCode){
//				String str = this.changeIntToBinaryString(readCode);
//				for(int i=0; i<str.length(); i++){
//					list.add(str.charAt(i));
//				}
//				readCode = input.read();
//			}
//			for(int j=0; j<list.size()-zerofill; j++){
//				transString += list.get(j);
//				if(this.searchHC(transString, out)){
//					transString = "";
//				}
//			}
			/*****************************************************************************************/
			input.close();
			out.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	/**
	 * 将从文件中读到的01 串与码表中的哈夫曼编码比较
	 * 若在码表中含有与之对应的哈夫曼编码则将码表中对应的
	 * 数据写入解压文件,否则不写入
	 * @param str  从文件中读到的01 字符串
	 * @param out  文件输出流
	 * @return     若写入文件返回true,否则返回false
	 * @throws IOException  写入发生错误时抛出异常
	 */
	private boolean searchHC(String str, OutputStream out) throws IOException{
		Set<Integer> set = code_Map.keySet();
		Iterator<Integer> p = set.iterator();
		while (p.hasNext()) {
			Integer key = p.next();//获得码表中的字节数据
			String hfmCode = code_Map.get(key);//获得哈夫曼编码
			if(hfmCode.equals(str)){
				out.write(key);
				return true;
			}
		}
		return false;
	}
	/**
	 * 根据 "除2取余,逆序排列"法
	 * 将十进制数字转化为二进制字符串
	 * @param a   要转化的数字
	 * @return    01 字符串
	 */
	private String changeIntToBinaryString(int a) {
		int b = a;
		int count = 0; //记录 a 可转化为01串的个数,在不够8为时便于补零
		String str = "";// 逆序二进制字符串
		String exmpStr = "";// 顺序二进制字符串

		while (a != 0) {
			b = a/2;
			if (a % 2 != 0) {
				str += 1;
			} else {
				str += 0;
			}
			a = b;
			count++;
		}
		//不够8位的地方补零
		for (int i = 0; i < 8 - count; i++) {
			str += 0;
		}
		//将转化后的二进制字符串正序
		for (int j = 7; j >= 0; j--) {
			System.out.print(str.charAt(j));
			exmpStr += str.charAt(j);
		}
		System.out.println("转化后的字符串>>>>>>>>>"+exmpStr);
		return exmpStr;
	}
}
分享到:
评论
1 楼 zsc_976529378 2012-08-25  
你好,今天看了你的博客,感觉你蛮强的。我看了用java实现的利用哈夫曼原理做的压缩解压缩程序有点不太懂,而且我感觉你在求哈夫曼编码的时候好像应该从size - 1,而不是size - 2。我有点不懂的就是压缩文件的部分。我很想向你学习学习,我的QQ1132833044,可以加一下哈!

相关推荐

    java实现哈夫曼压缩的实例

    在Java中实现哈夫曼压缩涉及到的主要步骤包括统计字节频率、构建哈夫曼树以及生成哈夫曼编码。首先,我们需要创建一个字节类(`NodeData`)来表示每个字节及其对应的权重(频率)。下面我们将详细讲解这些步骤: 1....

    java实现哈夫曼压缩与解压缩的方法

    "java实现哈夫曼压缩与解压缩的方法" 哈夫曼压缩是一种高效的压缩算法,广泛应用于文件压缩、数据压缩、图像压缩等领域。Java语言是实现哈夫曼压缩的不二之选,本文将详细介绍Java实现哈夫曼压缩与解压缩的方法。 ...

    java哈夫曼压缩和解压

    Java哈夫曼编码是一种数据压缩技术,它基于哈夫曼树进行编码,通过构建最优的二叉树结构来实现高效的数据编码与解码。在Java中实现哈夫曼压缩和解压涉及到以下几个关键知识点: 1. **哈夫曼树**: 哈夫曼树...

    哈夫曼编码实现压缩解压缩java

    下面将详细介绍哈夫曼编码的原理、构建过程以及在Java中的实现。 1. **哈夫曼编码原理**: 哈夫曼编码是建立在频率统计基础上的,通过对输入文本中各个字符出现频率的统计,构造一棵特殊的二叉树——哈夫曼树。在...

    HaffmanCode.rar_java 哈夫曼_压缩 解压 java_哈夫曼 编码_哈夫曼压缩

    综上所述,"HaffmanCode.rar_java 哈夫曼_压缩 解压 java_哈夫曼 编码_哈夫曼压缩"是一个包含Java实现的哈夫曼编码压缩和解压工具。它涉及到了哈夫曼树的构建、编码生成、文件压缩和解压的算法,以及Java中处理二...

    java 哈夫曼压缩算法的分析与实现[源码][附图]

    在Java中实现哈夫曼压缩涉及到以下几个关键步骤: 1. **统计字符频率**:首先,需要遍历输入文本,统计每个字符出现的次数,生成一个字符频率表。这是构建哈夫曼树的基础。 2. **构建哈夫曼树**:使用字符频率表,...

    java实现哈夫曼算法

    【Java实现哈夫曼编码】在Java中实现哈夫曼编码,首先需要创建一个`TreeNode`类来表示树的节点,包含字符、权重以及左右子节点。接着,通过以下步骤来构建哈夫曼树: 1. **初始化树**:输入的字符及其频率存储在...

    哈夫曼压缩与解压缩程序(JAVA)

    在Java编程环境中实现哈夫曼压缩与解压缩程序,我们可以利用面向对象的特性,设计多个类来完成不同部分的功能。 1. **FileChooserDemo.java**:这是一个用户界面类,通常包含用于让用户选择输入和输出文件的控件。...

    利用C++实现哈夫曼算法

    利用C++实现哈夫曼算法 哈夫曼算法是数据压缩的一种重要算法,它的...通过正确地实现哈夫曼算法,可以有效地压缩数据,提高数据存储和传输的效率。同时,哈夫曼算法也可以应用于其他领域,如数据压缩、编码和解码等。

    Java哈夫曼编码实现压缩文本文件

    霍夫曼编码实现压缩文本文件,见文件huffman.rar. 对文件数据读写等功能已经实现,程序在Q2Resources.zip中。Q2Resources.zip中的文件禁止修改。请将TextZip.java文件所有未实现的函数按照要求给以实现

    java哈夫曼压缩

    在Java中实现哈夫曼压缩通常包括以下几个关键步骤: 1. **构建哈夫曼树**:首先,需要统计输入文本中每个字符出现的频率。然后,根据这些频率创建一个哈夫曼树。哈夫曼树是一种特殊的二叉树,其特点是叶子节点代表...

    Java实现哈夫曼编码

    ### Java实现哈夫曼编码:深入解析与代码解读 #### 哈夫曼编码简介 哈夫曼编码(Huffman Coding)是一种广泛应用于数据压缩领域的编码技术,它是由David Huffman在1952年提出的。这种编码方式的核心思想是根据数据...

    哈夫曼编码算法与分析(java实现)

    哈夫曼编码算法与分析(java实现) 哈夫曼编码是一种广泛用于数据文件压缩的十分有效的编码方法,它通过对文件中各个字符出现的频率进行分析,生成各个字符的哈夫曼编码方案。哈夫曼编码的主要思想是通过构造一棵...

    哈夫曼树实现的压缩工具Java源代码

    在Java中实现哈夫曼树的压缩工具,首先要理解以下几个关键步骤: 1. **字符频率统计**:首先,需要统计输入文本中各个字符的出现频率。这可以通过遍历文本并使用哈希表记录每个字符及其出现次数来完成。 2. **构建...

    Java实现哈夫曼编码和解码

    哈夫曼编码是一种高效的数据压缩方法,通过构建特定的二叉树(哈夫曼树)来为字符分配短编码,使得频繁出现...通过理解这些概念,并结合Java编程,可以实现一个完整的哈夫曼编码和解码系统,适用于数据压缩和加密传输。

    xsjl.rar_Java哈夫曼编码_哈夫曼_哈夫曼 编码_哈夫曼压缩

    总结来说,Java哈夫曼编码是利用数据结构和算法理论实现的一种压缩技术,它在处理大量重复字符的数据时表现优秀。通过合理地分配编码长度,哈夫曼编码可以有效地减少存储空间,同时保持数据的可恢复性,因此在文本...

    java swing哈夫曼编码可视化,哈夫曼压缩率算法

    在这个项目中,我们用Java Swing来实现一个哈夫曼编码的可视化程序,同时展示了哈夫曼压缩率的计算。 首先,我们需要理解哈夫曼编码的基本原理。哈夫曼编码是通过构造一棵特殊的二叉树——哈夫曼树(或最小带权路径...

    java哈夫曼编码,压缩,解压缩

    总的来说,哈夫曼编码是数据压缩领域的一个重要概念,它在Java编程中可以通过构建哈夫曼树、生成编码、压缩和解压缩等步骤实现。结合描述中的信息,这个项目提供了一个实践哈夫曼编码的完整示例,对于学习和理解这一...

Global site tag (gtag.js) - Google Analytics