此文主要分析的是哈夫曼压缩的重点包括统计字符频率,建哈夫曼树,生成码表。哈夫曼压缩是最常用的一种静态无痕压缩。
以前也学习过哈夫曼的算法结构,但是没有自己去写代码实现,这次再学习了一遍,更加深刻理解哈夫曼压缩的原理,如何真正实现文件的压缩节省内存资源。下面梳理下我的代码和分析逻辑。
第一步是打开文件,读取文件流,统计文字频率。
方法是读取文件内容,根据每个字符有唯一的字节,存储在长度为256的数组中。可将字符和频率绑定为一个节点类Node,所有节点类的对象存储在队列中。
/*
* 统计频率
*/
private static Mylist<Node> countFre(String path) throws IOException {
// 创建一个文件输入流对象
java.io.FileInputStream fis = new java.io.FileInputStream(path);
java.io.BufferedInputStream bis = new java.io.BufferedInputStream(fis);
int[] byteArray = new int[256];
while (bis.available() > 0) {
int i = bis.read();
// 统计字符的频率
byteArray[i]++;
}
// 关闭文件输入流
fis.close();
Mylist<Node> l = new Mylist<Node>();
// 遍历数组,打印并保存
for (int i = 0; i < byteArray.length; i++) {
if (byteArray[i] != 0) {
char c = (char) i;
int count = byteArray[i];
// System.out.println("字符:"+c+" "+"频率:"+count);
// 添加到队列
l.add(new Node(c, count));
}
}
return l;
}
第二步是排序。
根据字符所对应的频率由小到大进行排序,可用选择排序算法。
/*
* 排序
*/
private static void sort(Mylist<Node> list) {
for (int i = 0; i < list.size() - 1; i++) {
int min = i;
for (int j = i + 1; j < list.size(); j++) {
// 如果j返回的节点中的频率大于i
if (list.get(j).getFrequency() < list.get(min).getFrequency())
min = j;
}
// 交换
if (i != min) {
Node n = list.get(min);
list.set(list.get(i), min);
list.set(n, i);
}
}
}
第三步是构建哈夫曼二叉树。
依次取出排好序的节点,每次取出前两个生成一个父节点,再将父节点添加到队列中,这里我将生成父节点的过程写在另一个函数creatHFM里,方便理解逻辑。
/*
* 构建哈夫曼二叉树
*/
private static Node creat(Mylist<Node> list){
while (list.size() > 1) {
Node l = list.remove(0);
Node r = list.remove(0);
Node n = creatHFM(l, r);
// 把新的节点添加到队列中
list.add(n);
// 排序
sort(list);
}
//根节点
Node root = list.get(0);
return root;
}
private static Node creatHFM(Node left, Node right) {
int fc = left.getFrequency() + right.getFrequency();
Node root = new Node(' ', fc);
root.setLeft(left);
root.setRight(right);
return root;
}
第四步是给每个字符编码,生成码表。
用递归遍历的方法生成每一个字符的编码,左0右1,并绑定字符保存,即新建一个类,依次保存到队列中。
/*
* 计算编码
*/
private static void creatCode(Node root, String str) {
// 若不是叶节点,递归遍历
if (root.getLeft() != null) {
creatCode(root.getLeft(), str + "0");
creatCode(root.getRight(), str + "1");
} else {// 否则输出,编码,并保存
count += root.getFrequency() * str.length();
System.out.println(root.getC() + " = " + str);
// 保存每一个字符及其编码,存入队列
Character chact = new Character(root.getC(), str);
codelist.add(chact);
}
}
在以上代码中所有的方法的参数输入由上一个方法的返回决定,更加方便梳理逻辑,查错。
构造方法及主函数,其中主函数中测试文件中的内容为string
public HFMtree(String path) throws IOException {
// 统计每个字符的频率
list = countFre(path);
// 根据每个字符的频率排序
sort(list);
// 构建哈夫曼二叉树,返回根节点
Node root = creat(list);
// 生成每一个字符的编码及带权路径。并保存编码
creatCode(root, "");
}
/*
* 主函数
*/
public static void main(String[] args) throws IOException {
// 文件路径
String str = "F:/text.txt";
// 文件的内容
// String string = "jfsjflvyavllcyqlcjhqvYV";
HFMtree hfm=new HFMtree(str);
System.out.print("带权路径=" + count);
}
测试结果
- 大小: 2.5 KB
分享到:
相关推荐
vc++哈夫曼压缩算法 vc++哈夫曼压缩算法
哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩...
哈夫曼压缩和解压和解压,数据结构课程设计,c++源码。
哈夫曼压缩与解压缩程序(JAVA)
哈夫曼算法实现图片的压缩,图片有前后对比。
通过自定义算法创建哈夫曼树和编码,对文件进行二进制操作实现压缩和解压。
C语言实现的huffman压缩解压缩算法
哈夫曼压缩与解压算法(可以直接运行),压缩成二进制文件,而且生成了txt文件可以查看哈夫曼编码。C++代码
哈夫曼实现文件的压缩与解压缩,代码关键部分有注释。
每次选出权值最小且没有双亲的两个节点建立新的哈弗曼树。 无栈非递归遍历Huffman树,求Huffman编码。...要注意的是当文件较小时,不宜使用哈夫曼来进行压缩,此时文件头占比过大,会使压缩结果很差。
c++ 哈夫曼压缩源代码. 多种文件格式 亲测可用
java实现的哈夫曼压缩算法,有swing界面。
利用哈夫曼编码对数据进行无损压缩,实现Huffman压缩的编码器和译码器。 1.首先读入待压缩源文件。 2.然后建立并分析字母表,对每种字符的出现频度进行统计,以频度作为建立Huffman树的权值。 3. 频度表建好后,就...
利用哈夫曼算法进行文件的压缩和解压缩。 利用命令行对指定的文件进行压缩和解压缩。 能对一般的文本文件有较好的压缩能力,对其它格式文件可以进行压缩但不一定能有压缩效果。对于用此程序压缩的文件可以用此程序...
压缩解压缩 源码 VC MFC实现 可供学习研究
这里采用哈夫曼编码方式来对每个字符重新编码,因为哈夫曼树具有最小带权路径长度的性质,能够生成用于压缩的二进制前缀码。程序使用的 “静态统计模型”,也就是说在编码前统计要编码的信息中所有字符的出现频率,...
哈夫曼压缩算法的c++实现,你可以学习到你想学的 这也是一个经典的算法设计题
这是一个典型的哈夫曼压缩程序,能压缩各种格式,适合初学者学习。
哈夫曼压缩算法,使用c#编写,先统计输入字串的权重,权重越大越靠近根节点