# Huffman编码 **Repository Path**: H-study/huffmanCode ## Basic Information - **Project Name**: Huffman编码 - **Description**: No description available - **Primary Language**: Java - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2021-05-13 - **Last Updated**: 2021-05-13 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README ## Huffman编码 #### **一、实验目的** 通过实验掌握从文件中读取数据及将运行结果保存到文件中的方法，了解Huffman编码的算法设计及使用Java实现的方法。 #### **二、实验内容** 对文件Input.txt中的字符使用Huffman编码进行编码，将编码结果保存到文件Output.txt文件中，最后对Output.txt文件中的字符进行译码。程序要先统计文件中字符的种类数，每种字符的个数，然后通过Huffman算法计算出各字符的Huffman编码，使用该编码对文件进行编码，并将结果保存到Output.txt文件中。最后对Output.txt文件中的字符进行译码，将译码结果保存到文件Output1.txt中。 #### **三、实验要求** 1.文件Output.txt大小应比文件Input.txt文件的小。 2.译码结果应和原文件input.txt中的内容一致。 #### **四、相关算法及程序说明** ##### (1)统计文件中字符的频率先读取文件，创建一个256大小的数组b保存字符出现的频率，下标对应该字符的ASCII码，值为该字符出现的频率，通过循环遍历读取文件内容，统计各个字符出现的频率；创建一个HashMap来保存该文件字符及其对应的频率，key值为字符的ASCII码，value值为频率，通过遍历数组b，如果数组元素不等0，则将该元素的下标存到HashMap的key值，对应的value为该元素的值，最后返回该HashMap。 ```java public static HashMap getCharWeight(String inputFile) throws IOException { FileInputStream inputStream = new FileInputStream(inputFile); HashMap hashMap = new HashMap<>(); int[] b = new int[256]; int read; while ((read=inputStream.read())!=-1){ b[read]+=1; } for (int i = 0; i < b.length; i++) { if (b[i]!=0){ hashMap.put(i,b[i]); } } return hashMap; } ``` ##### (2)创建huffman树结点类该节点类的属性包含权重(weight)、ASCII码(asc)、树的左孩子(lchild)和树的右孩子(rchild)，一个全参构造方法。 ```java class Node{ int weight; //权重 int asc; //该的字符ACll码 Node lchild; //左孩子 Node rchild; //右孩子 //构造方法 public Node(int weight, int asc, Node lchild, Node rchild) { this.weight = weight; this.asc = asc; this.lchild = lchild; this.rchild = rchild; } } ``` ##### (3)创建huffman树先创建一个ArrayList来保存叶子结点，将上面已保存的每个字符及其对应的频率添加到ArrayList当中；对列表中的元素根据结点的权重来按小到大进行排序，取出排序后列表中的权重最小和次小的结点，将该两个结点的权重相加的值作为该两个结点的父结点，左孩子为最小权重的结点，右孩子为次小权重的结点，将该父结点加入列表中，并移除最小和次小的结点；重复以上该过程，直到列表中只剩一个结点时，则退出循环；最后，返回该结点，即为huffman树的根结点。 ```java public static Node createTree(HashMap charWeight){ //创建保存叶子结点的列表 ArrayList tree = new ArrayList<>(); charWeight.forEach((k,v)->{ tree.add(new Node(v,k,null,null)); }); //构造Huffman树 while (tree.size()!=1){ //当列表中只剩下一个结点的时候则退出循环 //根据树的权重进行排序 Collections.sort(tree, Comparator.comparingInt(o -> o.weight)); //将排序后的列表中取前面两个最小的树的结点进行合并 //权重为该两个结点的权重和，左孩子为最小权重的结点，右孩子为次小权重的结点 //重新构造一颗树结点，将该结点加到原来的列表当中 //然后，将最小的两个结点从列表中移除 tree.add(new Node(tree.get(0).weight+tree.get(1).weight,-1,tree.get(0),tree.get(1))); tree.remove(tree.get(0)); tree.remove(tree.get(0)); } //返回列表中的第一个结点，即为该Huffman树的根结点 return tree.get(0); } ``` ##### (4)先序遍历huffman树先遍历huffman树的根结点，再遍历树的左孩子，每遍历一个左孩子结点，在code字符串后加“0”，直到左孩子为null时，则返回继续遍历右孩子，每遍历一个右孩子结点，在code字符串后加“1”，右孩子为null时，则huffman树遍历完成。最后，将各个字符ASCII码及其对应的huffman编码存到HashMap当中。(huffmanCode和huffmanCode2为全局HashMap变量,其中huffmanCode的key为huffman编码，value为ASCII码，huffmanCode2的key为ASCII码，value为huffman编码) ```java public static void printHuffmanCode(Node root, String code) { if(root!=null) { if(root.lchild==null&&root.rchild==null) { huffmanCode.put(code,root.asc); huffmanCode2.put(root.asc,code); } printHuffmanCode(root.lchild,code+"0"); printHuffmanCode(root.rchild,code+"1"); } } ``` ##### (5)对文件进行编码先读取文件，通过循环遍历文件中的每一个字符，寻找该字符的ASCII码在huffmanCode2中的key值所对应的huffman编码，将该huffman编码加到编码字符串中，当编码字符串的长度大于等于31的时候，截取该编码字符串的前31位01字符串转为十进制，将转为后的十进制数字写入文件中，再删除编码字符串前31位的01字符串，如果最后一段01字符串不足31位，则将剩下的部分转为十进制。最后，将编码后的字符串写入文件中。 ```java public static void coding(String inputFile, String outputFile) throwsIOException { //编码文件 FileInputStream inputStream = new FileInputStream(inputFile); //保存编码后的文件 DataOutputStream outputStream = new DataOutputStream(new FileOutputStream(outputFile)); int read; //编码后的字符串 StringBuilder codingContent = new StringBuilder(); int n=31;//01字符串转为十进制的位数 int num;//十进制数 while ((read=inputStream.read())!=-1){ String s = *huffmanCode2*.get(read);//获取该ASCII码对应的huffman编码 codingContent.append(s);//将huffman加入到codingContent中 if (codingContent.length()>=n){ num = Integer.*valueOf*(codingContent.substring(0,n),2);// 截取31位01字符串转为十进制 outputStream.writeInt(num);//将十进制数字写入文件 codingContent.delete(0,n);//删除已经转为十进制的01字符串 } } //处理最后一个不足31位的01字符串 num = Integer.*valueOf*(codingContent.substring(0,codingContent.length()),2); outputStream.writeInt(num); *lastNum* = num;//最后一个不足31位的01字符串转为十进制的数字 *lastLen* = codingContent.length();//最后一个不足31位的01字符串的长度 outputStream.close(); } ``` ##### (6)对文件进行解码先读取解码文件，读取文件中的十进制数字，将十进制转为二进制，如果转换后的二进制位数不等于31位，则在该二进制前面添加0，直到二进制位数等于31位为止，对于最后一个二进制数要与前面最后保存的01字符串的长度进行比较，若两者不等则在该二进制前面添加0，直到两者长度相等为止。最后，将转换后的二进制01字符串保存到编码字符串中，通过循环遍历编码字符串中的每一个字符，每次循环将该字符加入临时字符串中，如果huffmanCode的key包含该临时字符串，则将该临时字符串所对应的字符进行解码，将解码后的字符加入到解码后的字符串中，接着删除临时字符串，将它置为空，重复进行上述操作，直到遍历结束。最后，将解码后的字符串写入文件中。 ```java public static void decoding(String inputFile, String outputFile) throws IOException { DataInputStream dis = new DataInputStream(new FileInputStream(inputFile)); int a;//文件读取的十进制数字 int l;//十进制数字转为二进制后的长度与31位的差值 StringBuilder coding = new StringBuilder();//编码字符串 StringBuilder s;// 保存二进制的字符串 while (dis.available()>0){ a = dis.readInt(); s = new StringBuilder(Integer.*toBinaryString*(a));//将读取的十进制数转为二进制 //若十进制数字转为二进制后的长度不等于31，则在该二进制数前面补充l个0 if (a==*lastNum*){//处理最后一个二进制数 l = *lastLen*-s.length(); for (int i = 0; i < l; i++) { s.insert(0,"0"); } }else if ((l=31-s.length())!=0){ for (int i = 0; i < l; i++) { s.insert(0,"0"); } } coding.append(s);//将二进制字符串加入到编码字符串中 } //临时字符串 StringBuilder str = new StringBuilder(); //解码后的字符串 StringBuilder decodingContent = new StringBuilder(); for (int i=0;i