哈夫曼（有图片展示）

   

 

   这次真的是纠结了好久，足足半个月。

    在这半个月期间，突然感觉自己能自学了，有种入门的微妙感觉。自己只对音频、视频有知觉的历史一去不返了。

    编码的时候，有太多东西自己以前不懂，尤其是关于数据类型，进制之间的转换，内存中存储的二进制，原码-反码-补码，编码问题有ASCII，ANSI，Unicode-16等等。每个问题都是很纠结，更别说如何将他们联系起来。只能是看看书（此时真的知道书其实真的很好看，尤其是能解决你的问题），用代码测试。。。很漫长的测试，测试其实就是推断的验证，有推断必然有错误，有错误就有纠结，有纠结就意味着从头再来，还好这方面是自己最擅长的。。。。。

 

 

*****************************************************************

***此次采取将密码本（哈夫曼编码对照表）和压缩文件单独存储方式***

** 哈夫曼编码是不定长的，考虑此我用的是默认3字节存储编码。可以加更长**

*后来发现解码的时候，哈夫曼真的是存在很大的问题，效率好低！！！于是将编码以0开头和以1开头分别存储到不同的队列，减少解码是遍历的次数。。。。。* 

 

 

************************自己的一些理解*****************************

1：读进读出，用到的是输入输出流，方法自然是read()和write().容易理解

 

2:  联想到"111111111"以1开头的字符串能否同样以write（255）写进磁盘后达到预期的目的----因为内存中最高位是符号位。------于是了解内存中的数据存储方法。

 

3：内存中数据采用原码，反码，补码3种。补码问题可以解决计算机的硬件结构中只有加法器，所以大部分的运算都必须最终转换为加法的问题。所以计算机采用补码。那么255 在内存中是一2个字节存储的“0000000___11111111",调用write（255）后此方法截取8个低位，所以可以实现预期的目的。（高兴啊。。）但  总有中不详的感觉，后来知道write（-1) 也能达到相同的结果。

 

4：此时担心read（）的时候返回的是-1 还是255.“11111111”在计算机表示-1，但是写进文件是以255写进的。后来发现java   read（）方法返回的是0~255，所以write加上read达到一种互补，可以实现预期的目的。

 

5： 此时发现问题是在统计字符频率用到数组，次数组要定义成int类型，防止某字符出现次数超过255次，Byte数组的话次数达到127次后，在加就是-128，在多达到255就会出现最高位溢出，重新变成00000000；对构建哈树有影响。

 

6：剩下的就是编码问题，想实现哈夫曼编码，首先了解下ASCII，ANSI，Unicode-16等等。 这到时不太难，此间和同学碰见纠结的一个问题。同样的一个数字1以ANSII存储是1个字节，验证没错。以ANSI存储分全半角，全角是2字节，半角是1字节。 Unicode-16存储的话按说是2字节，结果是4字节。纠结。。。。

 

7：接着用java的read方法验证的时候解决此问题：read一个只有1的txt文件，结果多出来255，254，0，49.此时终于了解看Unicode编码是存在着这样一个现象：单独“联通”两个字存到txt中打开是乱码。有点相似。。为了区分某文件是什么编码，一边打开时正确解码，Unicode编码在文件头存储了255，254两个字节。

 **********************************************************************************

   主函数：

 

package huffman_3;

import javax.swing.*;
import java.awt.*;

public class MainHuffman extends JFrame {

	// 属性
	private JTextArea jta;
	private JMenuBar jmb;
	private JMenu file;
	private JMenuItem jmi1, jmi2, jmi3;
	public static void main(String[] args) {
		MainHuffman main = new MainHuffman();
        
	}
	
	
	public MainHuffman() {
		// 初始化
		jmi1 = new JMenuItem("压缩");
		jmi2 = new JMenuItem("解压");
		jmi3 = new JMenuItem("退出");
		file = new JMenu("文件");
		jmb = new JMenuBar();
		// 添加组件
		file.add(jmi1);
		file.add(jmi2);
		file.add(jmi3);
		jmb.add(file);
		// 创建监听器对象
		Listener action = new Listener();
		// 菜单项添加监听器
		jmi1.addActionListener(action);
		jmi1.setActionCommand("压缩");
		jmi2.addActionListener(action);
		jmi2.setActionCommand("解压");
		jmi3.addActionListener(action);
		jmi3.setActionCommand("退出");
		this.setJMenuBar(jmb);

		this.setTitle("哈夫曼解压缩");
		this.setSize(new Dimension(300, 130));
		this.setLocationRelativeTo(null);
		this.setDefaultCloseOperation(3);
		this.setVisible(true);

	}

}

 

监听器：

package huffman_3;

import java.awt.*;
import java.awt.event.ActionEvent;
import java.io.FileNotFoundException;
import java.util.ArrayList;

import javax.swing.*;

public class Listener implements java.awt.event.ActionListener {
	public void actionPerformed(ActionEvent arg0) {
		if (arg0.getActionCommand().equals("压缩")) {
			// 压缩
			JFileChooser jfc = new JFileChooser();
			jfc.setDialogTitle("解压文件");
			jfc.setVisible(true);
			// 定义一个返回的值
			int returnVal = jfc.showOpenDialog(null);// 使用默认属性
			if (returnVal == JFileChooser.APPROVE_OPTION) {
				String path = jfc.getSelectedFile().getAbsolutePath();
				Huffman_Com h_c = new Huffman_Com();// 创建压缩对象
				Code[] txtCode = h_c.read(path);// 读文件 得到编码
				h_c.write(txtCode, path);
			}

		} else if (arg0.getActionCommand().equals("解压")) {
			// 解压缩
			JFileChooser jfc = new JFileChooser();
			jfc.setDialogTitle("解压文件");
			jfc.setVisible(true);
			// 定义一个返回的值
			int returnVal = jfc.showSaveDialog(null);// 使用默认属性
			if (returnVal == JFileChooser.APPROVE_OPTION) {
				String path = jfc.getSelectedFile().getAbsolutePath();
				// 创建解压对象
				Huffman_Decom h_d = new Huffman_Decom();
				h_d.readCode(path);
				h_d.readDec(path);
				h_d.writeLast(path);
			}
		} else if (arg0.getActionCommand().equals("退出")) {
			System.exit(0);
		}

	}
}

 

 压缩文件：

package huffman_3;

import huffman_2.HuffmanCode;

import java.io.*;
import java.math.BigInteger;
import java.util.ArrayList;

/*
 *问题1：得到哈夫曼编码简单，再次读取文件时要得到编码，上次是遍历存放编码的队列（占用内存小），遍历效率很低
 *解决1： 改用数组存取编码，虽然占内存但是查取很快，效率高
 *问题2：哈夫曼编码超过了8位，存储到磁盘密码本的时候错误
 *解决2：只能是将8位甚至更高位的哈夫曼编码拆成两个字节（如果编码更多加入25位就要用4个字节存储），以自己的方法读进磁盘的密码本
 *其中统计频率的时候采用的数组定义成int类型，应为某字符出现的次数超过256次（否则此时read和write不再管用）
 */

public class Huffman_Com {
	/*
	 * 步骤：
	 * ----1第一次读取文件，数组统计字符频率--创建各个节点--得到哈夫曼树--（得到哈夫曼编码——同时创建Code类对象）--存到Code[]数组
	 * ----2遍历Code[] 数组，创建Byte[5] write到磁盘密码本中
	 * ----3第二次读取文件，根据Code[]得到编码，write磁盘压缩文件中
	 */
	// 定义根节点
	Node root;

	int[] data = new int[256];// 统计字符频率

	Code[] txtCode = new Code[256];// 存放数据，哈夫曼编码及长度

	ArrayList<Node> arr_node = new ArrayList<Node>();// 存放哈夫曼节点队列

	// 构造函数
	public Huffman_Com() {
		// 初始化统计数组
		for (int i = 0; i < 256; i++) {
			data[i] = 0;
			txtCode[i] = new Code();
		}
	}

	// 再次读取文件======密码本和压缩文件
	public void write(Code[] txtCode, String path) {
		File code_file = new File(path + "Code");// 创建密码本
		File huffman_file = new File(path + "CodeWLH");// 压缩文件
		try {
			code_file.createNewFile();
			huffman_file.createNewFile();
			// 写进密码本
			writeInPasswordFile(txtCode, path + "Code");
			// 写进压缩文件
			readInCompression(path, path + "CodeWLH", txtCode);
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	// 第一次读取文件得到Code数组--存放编码的信息
	public Code[] read(String path) {
		InputStream is = null;
		int t = 0;// 定义返回的值
		try {
			is = new FileInputStream(path);
			while ((t = is.read()) != -1) {
				data[t]++;
			}
			is.close();// 关闭流
		} catch (Exception e) {
			e.printStackTrace();
		}
		// 遍历数组 封住成节点
		for (int i = 0; i < 256; i++) {
			if (data[i] != 0) {// 如果不是0
				Node newNode = new Node(i, data[i]);
				arr_node.add(newNode);
			}
		}
		arr_node = upOrder();// 排序
		root = creatHuffman(arr_node);// 创建哈树
		txtCode = getHuffmanCode(root, "");// 哈码存放到数组
		return txtCode;
	}

	// 写进压缩文件
	public void readInCompression(String inPath, String outPath, Code[] txtCode)
			throws Exception {
		InputStream is = new FileInputStream(inPath);// 输入流
		OutputStream os = new FileOutputStream(outPath);// 输出流
		String huffmanCode = "";
		int t = 0;
		Boolean state = true;
		while ((t = is.read()) != -1) {
			huffmanCode += txtCode[t].Huffmancode;
			while (huffmanCode.length() >= 8) {
				StringBuilder sb = new StringBuilder(huffmanCode);// 字符串生成器
				String subStr = huffmanCode.substring(0, 8);// 截取0-8
				BigInteger bt = new BigInteger(subStr, 2);
				int n = Integer.parseInt(bt.toString());
				os.write(n);
				huffmanCode = sb.delete(0, 8).toString();// 删除0-8位
			}
			if (is.available() == 0) {
				System.out.println("马上写进去了。。。最后剩下小于8位的是：    " + huffmanCode);
				if (huffmanCode.length() != 0) {// 写进去2个字节
					// 把最后的编码写进去
					BigInteger bt = new BigInteger(huffmanCode, 2);
					int n = Integer.parseInt(bt.toString());
					os.write(huffmanCode.length());// 将最后的不足8个的编码写进文件前 先记录编码长度
					// 写进文件然后才能写编码
					os.write(n);
				} else {// 为了保证解码时的严密性和简单性--即使编码正好被8整除 也写进去1个字节，数值为0
					os.write(0);
				}
			}
		}
		os.close();
		is.close();// 关闭流 os先 is后
	}

	// 写进密码本--编码采用3个字节存储---24位长---
	public void writeInPasswordFile(Code[] txtCode, String path) {
		OutputStream os = null;
		try {
			os = new FileOutputStream(path);
			// 遍历Code[] 数组
			for (int i = 0; i < 256; i++) {
				if (txtCode[i].data != -1) {// 如果数据不为默认-1
					os.write(txtCode[i].data);// --1--
					os.write(txtCode[i].length);// --2--
					writeCode(txtCode[i].Huffmancode, os);// --3--
					System.out
							.println("压缩的密码本中的编码：  " + txtCode[i].Huffmancode);
				}
			}
		} catch (Exception e) {
			// TODO 自动生成 catch 块
			e.printStackTrace();
		}// 输出流对象
		finally {
			try {
				os.close();
			} catch (IOException e) {
				// TODO 自动生成 catch 块
				e.printStackTrace();
			}// 关闭输出流
		}
	}

	// 将不定长的String编码写进文件（编码的length<24） 默认是24位，3字节
	public static void writeCode(String code, OutputStream os) throws Exception {
		int length = code.length();// 输入编码的长度
		if (length > 0 && length <= 8) {
			BigInteger bt = new BigInteger(code, 2);// 声明是2进制的字符串
			int n = Integer.parseInt(bt.toString());
			os.write(0);
			os.write(0);// 前两个字节是00000000--00000000
			os.write(n);
		} else if (length > 8 && length <= 16) {
			// 将字符串截成两个字节
			String newStr_1 = code.substring(0, length - 8);
			String newStr_2 = code.substring(length - 8, length);
			// 字符转换成int写进文件
			BigInteger bt_1 = new BigInteger(newStr_1, 2);
			int n_1 = Integer.parseInt(bt_1.toString());
			BigInteger bt_2 = new BigInteger(newStr_2, 2);
			int n_2 = Integer.parseInt(bt_2.toString());
			os.write(0);
			os.write(n_1);
			os.write(n_2);
		} else if (length > 16 && length <= 24) {
			String newStr_1 = code.substring(0, length - 16);
			String newStr_2 = code.substring(length - 16, length - 8);
			String newStr_3 = code.substring(length - 8, length);
			// 分别转换成int写进文件
			BigInteger bt_1 = new BigInteger(newStr_1, 2);
			int n_1 = Integer.parseInt(bt_1.toString());
			BigInteger bt_2 = new BigInteger(newStr_2, 2);
			int n_2 = Integer.parseInt(bt_2.toString());
			BigInteger bt_3 = new BigInteger(newStr_3, 2);
			int n_3 = Integer.parseInt(bt_3.toString());
			os.write(n_1);
			os.write(n_2);
			os.write(n_3);
		} else {
			System.out.println("编码长度超过了默认的24位，版本升级！！！");
		}
		// os.close();// 关闭输出流

	}

	// 得到哈夫曼编码
	public Code[] getHuffmanCode(Node root, String s) {
		// 终止的条件
		if (root.leftnode == null && root.rightnode == null) {
			Code nodeCode = new Code();// 创建Code对象
			nodeCode.data = root.data;// 数据大小
			nodeCode.length = s.length();// 编码长度
			nodeCode.Huffmancode = s;// 编码
			// 存到数组
			txtCode[root.data] = nodeCode;
			return txtCode;
		}
		if (root.leftnode != null) {
			getHuffmanCode(root.leftnode, s + '0');
		}
		if (root.rightnode != null) {
			getHuffmanCode(root.rightnode, s + '1');
		}
		return txtCode;
	}

	// 创建哈树
	public Node creatHuffman(ArrayList<Node> arr_node) {
		// 递归调用的终止条件
		if (arr_node.size() == 1) {
			root = arr_node.get(0);
			// return； 是不行的 如果文件只有一种字符
			return root;
		}
		// 取出前两个元素
		Node node_0 = arr_node.get(0);
		Node node_1 = arr_node.get(1);
		// 创建新的节点
		Byte nodeData = 0;
		int time0 = node_0.times;
		int time1 = node_1.times;
		Node newNode = new Node(nodeData, time0 + time1);
		// 设置左右的节点
		newNode.leftnode = node_0;
		newNode.rightnode = node_1;
		// 刷新arr_node 将newNode 插入到指定位置
		if (newNode.times > arr_node.get(arr_node.size() - 1).times) {
			arr_node.add(newNode);
		} else {
			for (int i = 0; i < arr_node.size(); i++) {
				if (newNode.times <= arr_node.get(i).times) {
					arr_node.add(i, newNode);
					break;
				}
			}
		}
		arr_node.remove(0);
		arr_node.remove(0);
		// 递归调用
		this.creatHuffman(arr_node);
		return root;
	}

	// 将arr_node 队列按数序排序
	public ArrayList<Node> upOrder() {
		// 创建一个新的队列
		ArrayList<Node> list = new ArrayList<Node>();
		// 遍历
		for (int i = 0; i < arr_node.size(); i++) {
			if (list.size() == 0) {
				list.add(arr_node.get(0));
			} else {
				for (int t = 0; t < list.size(); t++) {
					// 先判断该数据是不是比最后一个数据大
					if (arr_node.get(i).times >= list.get(list.size() - 1).times) {
						// 直接加到末尾
						list.add(arr_node.get(i));
						System.out.println(list.size());
						break;
					}// 找到大于新插入的数据的list中数据位置插入此数据
					else if (arr_node.get(i).times < list.get(t).times) {
						list.add(t, arr_node.get(i));
						System.out.println(list.size());
						break;
					}
				}
			}
		}
		arr_node = list;
		return arr_node;
	}

}

 解压文件：

 

package huffman_3;

import java.io.*;
import java.util.ArrayList;

/*  实现解压缩
 *1 读取密码本---以5个字节为一个循环---得到Code对象，添加到队列---为了解压时方便：以开头首位数字1或者0分别存储两个队列
 *2 读取压缩的文件---每次读取一个数字，遍历队列得到对应的int数值，存到队列arr_integer
 *3 遍历arr_integer 读进新的文件。实现解压！！！！
 */

public class Huffman_Decom {

	// 存放Code类的队列
	ArrayList<Code> arr_0_Code = new ArrayList<Code>();
	ArrayList<Code> arr_1_Code = new ArrayList<Code>();
	// 存放原始文件数据Int类型的队列
	ArrayList<Integer> arr_int = new ArrayList<Integer>();
	public void readCode(String path) {
		InputStream is = null;
		path = path.substring(0, path.length() - 3);
		try {
			is = new FileInputStream(path);
			while (is.available() > 0) {
				Code newCode = new Code();
				newCode.data = is.read();// 第一个字节存放的是数值
				newCode.length = is.read();// 第二个字节存放哈夫曼编码长度
				if (newCode.length <= 8 && newCode.length > 0) {// 3-5个字节存放编码
					is.read();
					is.read();
					int t_3 = is.read();// 每组的最后一个字节
					// 得到指定长度的二进制字符串
					newCode.Huffmancode = Dec_To_Binaary(t_3, newCode.length);
				} else if (newCode.length > 8 && newCode.length <= 16) {
					is.read();
					int t_2 = is.read();// 第二个字节
					newCode.Huffmancode = Dec_To_Binaary(t_2,
							newCode.length - 8);
					int t_3 = is.read();// 第三个字节
					newCode.Huffmancode += Dec_To_Binaary(t_3, 8);
				} else if (newCode.length > 16 && newCode.length <= 24) {
					// 此处可以添加 根据编码成都改变
				} else {
					System.out.println("出错了。。。。。");
				}
				// 取得编码的首个字符 判断添加到那个队列
				char first = newCode.Huffmancode.charAt(0);
				if (first == '1') {
					arr_1_Code.add(newCode);
				} else {
					arr_0_Code.add(newCode);
				}
			}
			is.close();// 关闭输如流
		} catch (Exception e) {
			e.printStackTrace();
		}

	}

	// 读取压缩的文件
	public void readDec(String path) {
		InputStream is = null;
		try {
			is = new FileInputStream(path);
			int num = 0;
			int total = is.available();
			String code = "";
			while (num < total - 2) {
				num++;
				int t = is.read();
				code += Dec_To_Binaary(t, 8);
				StringBuilder sb = new StringBuilder(code);// 转换成字符串生成器 便于删除
				for (int i = 0; i < sb.length(); i++) {
					String tran = code.substring(0, i + 1);
					if (tran.substring(0, 1).equals("0")) {
						for (int m = 0; m < arr_0_Code.size(); m++) {
							if (tran.equals(arr_0_Code.get(m).Huffmancode)) {
								arr_int.add(arr_0_Code.get(m).data);
								// 改变sb
								sb.delete(0, tran.length());
								i = -1;// i++ =0
								code = sb.toString();
								break;
							}
						}
					} else {
						for (int n = 0; n < arr_1_Code.size(); n++) {
							if (tran.equals(arr_1_Code.get(n).Huffmancode)) {
								arr_int.add(arr_1_Code.get(n).data);
								sb.delete(0, tran.length());
								i = -1;
								code = sb.toString();
								break;
							}

						}
					}
				}
			}
			// 处理最后的两个字节 得到最后一个字符
			int t = is.read();// 读取倒数第二个字节
			if (t != 0) {// 等于0 表示编码正好被8整除，无需读取最后2字节
				int last = is.read();// 读取最后一个字节
				code += Dec_To_Binaary(last, t);
				StringBuilder sb = new StringBuilder(code);// 转换成字符串生成器 便于删除
				// 再次遍历
				for (int i = 0; i < code.length(); i++) {
					String tran = code.substring(0, i + 1);
					if (tran.substring(0, 1).equals("0")) {
						for (int m = 0; m < arr_0_Code.size(); m++) {
							if (tran.equals(arr_0_Code.get(m).Huffmancode)) {
								arr_int.add(arr_0_Code.get(m).data);
								// 改变sb
								sb.delete(0, tran.length());
								i = -1;
								code = sb.toString();
								break;
							}
						}
					} else {
						for (int n = 0; n < arr_1_Code.size(); n++) {
							if (tran.equals(arr_1_Code.get(n).Huffmancode)) {
								arr_int.add(arr_1_Code.get(n).data);
								sb.delete(0, tran.length());
								i = -1;
								code = sb.toString();
								break;
							}
						}
					}
				}
			}
			is.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	// 最后一读
	public void writeLast(String path) {
		path = path.substring(0, path.length() - 7);
		File file = new File(path);
		OutputStream os = null;
		try {
			file.createNewFile();
			os = new FileOutputStream(file);
			for (int i = 0; i < arr_int.size(); i++) {
				os.write(arr_int.get(i));
			}
			os.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	/*
	 * 将int类型数值转换成指定位数的2进制 t 是输入的整数 length 表示想要转换的长度 例如2转换成0010，00010等等
	 */
	public String Dec_To_Binaary(int t, int length) {
		// 定义中转字符串
		String tran;
		// 定义补0的字符串
		String repair;
		// 字符常量
		String s = "00000000";
		tran = Integer.toBinaryString(t);
		repair = s.substring(0, length - tran.length());
		return (repair + tran);
	}

}

 

哈夫曼编码类：

package huffman_3;

public class Code {

   int  data;
   int  length;
   String Huffmancode;
   
   //构造函数
   public Code(){
	   this.data=-1;
	   this.Huffmancode="";
	   this.length=0;
   }
}

 

节点类：

 

package huffman_3;
//节点类 存放节点数据+times+左节点，右节点
public class Node {
   int data=0;
   int times=0;//定义成int  考虑出现的次数完全肯能超过128次
  
   Node  leftnode;
   Node  rightnode;
   
   public  Node(int i,int times){
	  this.data= i;
	  this.times=times;
	  //节点默认为空
	  leftnode=null;
	  rightnode=null;
   }
}

 

评论

1 楼 finallygo 2013-04-12  

255 在内存中应该是4个字节的(int 类型),其实只要低8位是1就行了,前面的24位会自动省略