哈夫曼编码压缩
压缩过程思路:
1、 统计文件中每个字节出现的次数,每一个字节由8bit组成,一个字节从0~255,分别统计每种字节的次数。
1、实现思路:创建一个长度为256的数组,数组的下标与byte的值对应,数组中的每一个数据元素表示一种字节出现的次数。
2、 根据每个字节出现的次数建一个哈夫曼树
1. 遍历前面建立的数组,判断数组元素的值是否为0
2. 如果数组元素的值不为0,则为该元素建立一个结点,并将该结点添加到结点队列中
3. 结点含有数据域(存储数组的下标值),频率值域(对应于下标的元素值,即某字节在文件中出现的次数),左子结点,右子结点
// 将文件中出现次数不为0 的字节存入结点中,并将结点添加到队列中,TreeNode是自定义的结点类 public void addNode2List() { for (int i = 0; i < frequent.length; i++) { if (frequent[i] != 0) { TreeNode node = new TreeNode(i, frequent[i]); nodeList.add(node); } } }
4. 生成一棵哈夫曼树(哈弗曼编码的思想)
1. 遍历结点队列,从中找到频率值最小和次小的两个结点
2. 新建一个结点,其左右子结点是刚才找到的两个结点
3. 将这个新结点添加到队列中
4. 将之前找到的两个结点从结点队列中移除
5. 跳到第1步,直至队列中只有一个结点,该结点即为哈弗曼树的根结点
// 将队列中的结点转化成哈夫曼树 public void changeTree() { int len = nodeList.size();// 取得初始队列的长度 for (int j = 0; j < len - 1; j++) { TreeNode minnode1 = nodeList.get(0);// 取得队列中的第一个结点 TreeNode minnode2 = nodeList.get(1);// 取得队列中的第二个结点 // 循环比较,找到最小两个结点 for (int i = 1; i < nodeList.size(); i++) { TreeNode node = nodeList.get(i);// 取得队列中的第i个结点 // 比较两个节点中frequent值的大小 if (minnode1.getFrequent() > node.getFrequent()) {// 如果minnode1结点的次数值大于node的 minnode2 = minnode1;// 将最小的结点赋给次小的节点 minnode1 = node;// 将新找到的最小结点赋给原来最小的结点 } else if (minnode2.getFrequent() > node.getFrequent()) {// 如果minnode2结点的次数值大于node的 minnode2 = node;// 将新找到的最小结点赋给原来最小的结点 } } int sum = minnode1.getFrequent() + minnode2.getFrequent(); TreeNode parent = new TreeNode(0, sum);// 新建一个父节点,其子节点为上面找到的最小和次小结点,其data值为0,表示它不是叶结点 parent.setLeft(minnode1); parent.setRight(minnode2); // 将新的父节点添加到原来的队列中 nodeList.add(parent); // 把最小和次小的两个结点队列中移除 nodeList.remove(minnode1); nodeList.remove(minnode2); } }
3、 根据上一步生成的哈夫曼树,对每个字节重新编码
1. 根据哈夫曼数,进行新编码
2. 每一个字节都用字符串表示,字符串中只含有字符’0’和’1’。
3. 具体编码实现:
// 根据哈夫曼树进行编码 public void encode(TreeNode root, String s) { // 如果遍历到该节点为叶结点 if (root.getLeft() == null && root.getRight() == null) { int key = root.getData();// 获得叶结点的data map.put(key, s);// 将data和它的新编码添加到map中 System.out.println((cnt++) + "<---->" + s); return; } // 如果该结点的左子节点不为空 if (root.getLeft() != null) { String s1 = s + "0"; encode(root.getLeft(), s1);//递归调用本方法 } // 如果该结点的右子节点不为空 if (root.getRight() != null) { String s2 = s + "1"; encode(root.getRight(), s2);//递归调用本方法 } }
4、 将源文件中的字节按照新编码转换成字符串
1. 遍历文件中的字节,并按照新编码转换成一个长字符串
2. 如果长字符串的长度不是8的倍数,则在长字符串末尾补'0'
// 将文件中的字节,按照新的编码存储到一个长字符串中 public void changeToString(String fileName) { try { FileInputStream fis = new FileInputStream(fileName); BufferedInputStream bis = new BufferedInputStream(fis); while (bis.available() > 0) { int i = bis.read(); longstr.append(getNewCode(i));// 新编码添加到长字符串结尾 } bis.close(); fis.close(); number = longstr.length() % 8;// 长字符串对8取余数的结果 // 给长字符串补'0' for (int i = 0; i < 8 - number; i++) { longstr.append('0'); } } catch (Exception e) { e.printStackTrace(); } }
5、 从上面的长字符串中,依次读取8个字符,将这8个字符转换成一个十进制数,并将其输出到文件中
1. 依次从长字符串中读取8个字符,将其转化成一个相应的十进制数
2. 将这个十进制数输出到文件中保存
压缩文件的结构:文件头和数据部分
1、 文件头包含的信息:
1. 用4个byte保存压缩文件的新编码数,即数组中元素值不为0的元素个数
2. 用1个byte保存字符串末尾补0的个数
3. 保存新编码规则
1、写入一个源码值,占1byte
2、写入新编码的长度,1byte
3、写入对应于源码值的新编码,新编码中的一个字符('0'或'1')用1byte节表示(不等 长存储,最坏情况下一个新码由255个'0'或'1'表示)
例子:原字节的值为20的新编码可能是0101010101
2、 文件数据部分
1. 压缩文件中数据部分的每一个字节都是由原来的8个字符转化而成的十进制数。
解压缩过程
就是将用上面的方法压缩的文件解压成源来可读的文件。
从压缩文件中读取数据的顺序及其含义
1、读取文件头信息
a) 读取4个byte,这4个字节表示压缩编码中新编码的个数
b) 读取1个byte:数据部分补'0'个数
c) 根据读取到的新编码的个数,循环进行d、e、f步骤的读取
d) 读取1个byte:源码值
e) 读取1个byte:该新编码的长度值
f) 读取对应于源码值的新编码,读取的字节数由d)步骤读取的字节所表示的新编码的长度值决定。将源码值与其对应的字符串编码添加到Map中
2、读取编码数据信息
a) 将读取到的每一个字节都转换成对应的8位字符,将其添加到长字符串中
b) 按照读取到的编码规则,即保存在Map中的编码规则信息,将长字符串中的字符码转换成源字节码,并将源字节码输出到解压缩文件中
<!--EndFragment-->
<!--EndFragment-->
分享到:
相关推荐
文件包含可执行程序和源代码,可以直接下载运行。C++ QT 实现文件压缩,有两种压缩算法,一是哈夫曼编码,还要一个是游程编码
利用哈夫曼编码思想,设计对一个文本文件(.txt)中的字符进行哈夫曼编码,生成编码压缩文件(.txt),并且还可将压缩后的文件进行解码还原为原始文本文件(.txt)。 实现的功能: (1)压缩:实现对文件的压缩,生成...
对比二进制编码和哈夫曼编码后的文件字节大小,并计算压缩率 通过编写利用哈夫曼算法实现的文件编码解码小工具,可加深对哈夫曼算法的理解,以及编码的熟练度。本人的小工具仅针对英文大小字母及 ' '\n' ' ' 字符...
哈夫曼编码实现文本文件的压缩,可作为数据压缩作业的参考
实验目的:理解哈弗曼信源编码算法,并能应用于文件压缩中。 实验内容:写出程序,利用哈弗曼编码实现对文件的压缩,并能解压文件。 实验步骤: 1、压缩 (1) 统计原始文件中各字节出现的概率(次数); (2) 采用...
上回传的那个可能忘了上传源码,非常抱歉,这里就将源码上传,源码里有错误的话,请指正。
哈夫曼编码进行文本压缩
数据结构课程设计用哈夫曼编码实现文件压缩: 一、实验题目: 用哈夫曼编码实现文件压缩 二、实验目的: 1、了解文件的概念。 2、掌握线性链表的插入、删除等算法。 3、掌握Huffman树的概念及构造方法。 4、掌握...
使用哈夫曼编码实现对文本文件的压缩和解压缩
114243 用哈夫曼编码实现文件压缩 doc
含哈夫曼编码和解码代码,利用哈夫曼编码来压缩和解压文件的小工具。
哈夫曼编码-文件压缩,数据结构作业,C语言 用哈夫曼树对ASCII文件进行压缩,编码后得到实际压缩的文件,同时还有解码功能,界面的效果 文件夹中含程序的多个版本,分别是代表程序编写是的不同阶段 程序使用C编写,...
用Java实现,哈夫曼编码实现文件压缩,有详细注释
利用无失真信源编码方法中的哈夫曼编码进行程序设计实践,实现对文件的压缩与解压操作。
通过哈夫曼编码实现文件的压缩与解压.pdf
压缩文件即读文件,统计文件中的字符个数,对文件进行哈夫曼编码和译码,并将编码译码后的字符存储在文件中。 完成功能的详细说明: 1.统计文本文件中各字符的频率(涉及读文件,统计字符个数); 2.对文件中的...
使用哈夫曼编码统计字符的频率作为权值来实现压缩技术 ,包括哈夫曼树的创建,构造哈夫曼编码,使用哈夫曼编码压缩文件,和解压文件
利用哈夫曼编码原理对磁盘文件进行压缩与解压
采用哈夫曼编码对文件进行压缩解压。先将文件各字节读出,统计频率。进行哈夫曼编码,将编码重新写入文件。 编码命令:c <input file> 解码命令:d <input file> 对于编码的output file和解码的input file可以...