哈夫曼（有图片展示）

???

?

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

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

??? 编码的时候，有太多东西自己以前不懂，尤其是关于数据类型，进制之间的转换，内存中存储的二进制，原码-反码-补码，编码问题有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) {// 如果不是0Node 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-8BigInteger 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个字节，数值为0os.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) {// 如果数据不为默认-1os.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--00000000os.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);// 改变sbsb.delete(0, tran.length());i = -1;// i++ =0code = 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);// 改变sbsb.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;   }}

?