北京工业大学--算法作业3--huffman编码对文本文件进行压缩与解压---Java

### 学生信息 0. 学号： ### 编程语言 Java ### 运行环境 0. jdk1.8以上（1.8版本以下会报错） 0. IDEA 开发工具 ### 运行过程说明 点击进入Main类，启动main方法，根据提示，输入数据文件编号，然后自动运行程序 ### 算法设计 #####分析 1. 实质上是贪心算法求最优解问题。 2. 采用哈夫曼编码的方式压缩文件，将文件中字符按照哈夫曼树进行编码，然后将编码转换为二进制输出到文件中。 #####算法分析 0. 采用Collections.sort排序的时间复杂度为O（nlogn） 0. 总的时间复杂度为O（nlogn） #####伪码描述： 1.输入数据文件的编号； 2.while (文件编号 <1 || 文件编号 > 5){ 2.1 重新输入数据文件的编号； 3.通过FileRead.getFileData方法获取数据文件数据（getFileData方法利用FileReader、BufferedReader读取）； 4.将文件中文件路径、文件数据的哈夫曼树、文件中每一个字符的出现次数等信息封装到FileContent实体bean中； 5、统计文本文件中每个字符的使用频度， 5.1、List<Node> nodes = fileContent.getNodeList(); 5.2、对list排序并输出 SortList sort = new SortList(); sort.sortList(nodes); nodes.forEach(node -> { System.out.println("char:\'"+(char)node.getCharacter()+"\'>>> times: "+node.getWeight()); }); 6.通过哈夫曼实体类HuffmanTree()的构造方法，获取哈夫曼树的权重和节点; //当nodes只含有哈夫曼树的根节点时，退出循环 while (nodes.size() > 1) { //左节点 Node left = nodes.get(0); //右节点 Node right = nodes.get(1); //父节点 Node parent = new Node(left.weight + right.weight, -1); parent.setLeftNode(left); parent.setRightNode(right); //删除左节点 nodes.remove(0); //删除右节点 nodes.remove(0); //添加父节点 nodes.add(parent); sort.sortList(nodes); } if (nodes.size() == 0) { root = null; } else { root = nodes.get(0); } 7、为了写入文件的效率，构造HashMap<Integer, String> map = new HashMap<>();把哈夫曼树的权重和节点存在map中; 7.1 利用哈夫曼树的树转map方法：huffmanTree.treeToMap(); 8、以二进制流形式压缩文件 8.1使用文件写入类FileWrite.writeFile()方法，将每一个字符用对应的哈夫曼编码替换 int value = inputStream.read(); while (value != -1) { String str = map.get(value); for (int i = 0; i < str.length(); i++) { char ch = str.charAt(i); outputStream.write(ch); } value = inputStream.read(); } 9.将压缩文件写到路径中 #### 贪心算法，利用huffman编码对文本文件进行压缩作业--整体目录结构 ``` file-huffman/src/main └─java └─com └─han └─huffman 项目名 ├─bean 实体 └─utils 工具包 └─resource 资源包（包含输入输出数据文件集） ``` ##### 类设计说明 0. Main ：main方法，程序入口 0. FileContent ： 文件信息bean 0. HuffmanTree ： 哈夫曼树 工具类 0. FileRead ： 文件读取类 0. FileWrite ： 文件输出类 0. SortList ： List排序工具类 0. Node ： 哈夫曼树节点bean ##### 数据结构设计 FileContent类 ： 文件信息bean 0. filePath 文件路径 0. huffmanTree 文件数据的哈夫曼树 0. nodeList 文件中每一个字符的出现次数信息 Node类 ： 哈夫曼树节点bean 0. rightNode 树的右节点 0. leftNode 树的左节点 0. weight 字符权重（字符出现次数） 0. character 字符 ##### 数据文件说明 0. 文件内字符需为ASCII码对应字符