- 浏览: 205450 次
- 性别:
- 来自: 长沙
最新评论
-
螺旋懒虫:
原本是想自己画点阵的,一来画的不标准,也不好解析(用excel ...
超级详细解析——字模 -
螺旋懒虫:
这个程序解决了我怎么加载点阵字库文件的问题,和怎么去拿到汉字对 ...
超级详细解析——字模 -
慕容墨风:
你好,我用你的测试程序发现数字提取不了
超级详细解析——字模 -
文之若素:
求代码,我最近在学这个,公司需要,呜呜呜,159374403 ...
初学EXTJS做的系统界面 -
csrhlu:
为什么我压缩之后文件还变大了呢? 而且解压eclipse下边会 ...
自己动手写压缩软件,超详细解释(哈夫曼实现)
说到文件压缩大家很容易想到的就是 rar,zip 等我们常见的压缩格式。然而,还有一种就是大家在学习数据结构最常见到的哈夫曼树的数据结构,以前还不知道他又什么用,其实他最大的用途就是用来做压缩,也是一些 rar,zip 压缩的祖先,称为哈弗曼压缩(什么你不知道谁是哈弗曼,也不知道哈弗曼压缩,不急等下介绍)。
随着网络与多媒体技术的兴起,人们需要存储和传输的数据越来越多,数据量越来越大,以前带宽有限的传输网络和容量有限的存储介质难以满足用户的需求。
特别是声音、图像和视频等媒体在人们的日常生活和工作中的地位日益突出,这个问题越发显得严重和迫切。如今,数据压缩技术早已是多媒体领域中的关键技术之一。
一、什么是哈弗曼压缩
Huffman( 哈夫曼 ) 算法在上世纪五十年代初提出来了,它是一种无损压缩方法,在压缩过程中不会丢失信息熵,而且可以证明 Huffman 算法在无损压缩算法中是最优的。 Huffman 原理简单,实现起来也不困难,在现在的主流压缩软件得到了广泛的应用。对应用程序、重要资料等绝对不允许信息丢失的压缩场合, Huffman 算法是非常好的选择。
二、怎么实现哈弗曼压缩
哈夫曼压缩是个无损的压缩算法,一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号(例如,文本文件中的字符)用一个特定长度的位序列替代。因此,在文件中出现频率高的符号,使用短的位序列,而那些很少出现的符号,则用较长的位序列。
故我们得了解几个概念:
1 、二叉树 : 在计算机科学中,二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作 “ 左子树 ” ( left subtree )和 “ 右子树 ” ( right subtree )。
2 、哈夫曼编码 (Huffman Coding) :是一种编码方式,哈夫曼编码是可变字长编码 (VLC) 的一种。 uffman 于 1952 年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字,有时称之为最佳编码,一般就叫作 Huffman 编码。
三、哈夫曼编码生成步骤:
① 扫描要压缩的文件,对字符出现的频率进行计算。
② 把字符按出现的频率进行排序,组成一个队列。
③ 把出现频率最低(权值)的两个字符作为叶子节点,它们的权值之和为根节点组成一棵树。
④ 把上面叶子节点的两个字符从队列中移除,并把它们组成的根节点加入到队列。
⑤ 把队列重新进行排序。重复步骤 ③④⑤ 直到队列中只有一个节点为止。
⑥ 把这棵树上的根节点定义为 0 (可自行定义 0 或 1 )左边为 0 ,右边为 1 。这样就可以得到每个叶子节点的哈夫曼编码了。
既如 (a) 、 (b) 、 (c) 、 (d) 几个图,就可以将离散型的数据转化为树型的了。
如果假设树的左边用0 表示右边用 1 表示,则每一个数可以用一个 01 串表示出来。
则可以得到对应的编码如下:
1-->110
2-->111
3-->10
4-->0
每一个01 串,既为每一个数字的哈弗曼编码。
为什么能压缩:
压缩的时候当我们遇到了文本中的1 、 2 、 3 、 4 几个字符的时候,我们不用原来的存储,而是转化为用它们的 01 串来存储不久是能减小了空间占用了吗。(什么 01 串不是比原来的字符还多了吗?怎么减少?)大家应该知道的,计算机中我们存储一个 int 型数据的时候一般式占用了 2^32-1 个 01 位,因为计算机中所有的数据都是最后转化为二进制位去存储的。所以,想想我们的编码不就是只含有 0 和 1 嘛,因此我们就直接将编码按照计算机的存储规则用位的方法写入进去就能实现压缩了。
比如:
1这个数字,用整数写进计算机硬盘去存储,占用了 2^32-1 个二进制位
而如果用它的哈弗曼编码去存储,只有110 三个二进制位。
效果显而易见。
开始写程序:
开始些程序之前,必须想好自己的文件存储格式,和存储规则是什么
为了简便,我自定义存储的基本信息,格式如下:
SaveCode[i].n int型 // 每一个字节的编码长度 i:0~256
B yte[] byte数组型 // 每一个字节的编码 SaveCode[i].node 中 String 的 01 串转化而来。
Byte[] byte数组型 // 对文件中每一个 byte 的重新编码的哈夫曼编码写入。
有了定义好的格式我们的读写就非常的方便了,
创建步骤:
①读入文件中的所有字节:
// 创建文件输入流 java.io.FileInputStream fis = new java.io.FileInputStream(path); //读入所有的文件字节 while(fis.available()>0){ int i=fis.read(); byteCount[i]++; }
②构建哈夫曼树:
/** * 使用优先队列构建哈弗曼树 */ public void createTree(){ //优先队列 PriorityQueue<hfmNode> nodeQueue = new PriorityQueue<hfmNode>(); //把所有的节点都加入到 队列里面去 for (int i=0;i<256;i++){ if(byteCount[i]!=0){ hfmNode node = new hfmNode(i,byteCount[i]); nodeQueue.add(node);//加入节点 } } //构建哈弗曼树 while(nodeQueue.size()>1) { hfmNode min1 = nodeQueue.poll();//获取队列头 hfmNode min2 = nodeQueue.poll(); hfmNode result = new hfmNode(0,min1.times+min2.times); result.lChild=min1; result.rChild=min2; nodeQueue.add(result);//加入合并节点 } root=nodeQueue.peek(); //得到根节点 }
这里我采用了优先队列的方法,因为优先队列比较符合哈夫曼的构造方法,形式上也非常的相似。
③取得每一个叶子节点的哈夫曼编码:
/** * 获得叶子节点的哈弗曼编码 * @param root 根节点 * @param s */ public void getMB(hfmNode root,String s){ if ((root.lChild==null)&&(root.rChild==null)){ Code hc=new Code(); hc.node=s; hc.n=s.length(); System.out.println("节点"+root.data+"编码"+hc.node); SaveCode[root.data]=hc;//保存字节 root.data 的编码 HC } if (root.lChild!=null){//左0 右 1 getMB(root.lChild,s+'0'); } if (root.rChild!=null){ getMB(root.rChild,s+'1'); } }
如此一来我们的哈夫曼树就建好了。
下面就是按照我们之前定义的文件存储格式直接写进文件就可以了。
压缩文件的写入:
① 写出0~256 每一个字节对应编码的长度
//写出每一个编码的长度 for (int i=0;i<256;i++){ fos.write(SaveCode[i].n); }
② 写出每一个字节所对应的编码
这一步较为复杂,因为JAVA 中没有自己定义的二进制为写入,我们就不得不将每 8 个 01 String 转化为一个 byte 再将 byte 写入。但是,问题又来了不是所有的 01String 都是 8 的整数倍,所以就又得在不是 8 整数倍的 String 后面补上 0
/////写入每一个字节所对应的 String编码 int count=0;//记录中转的字符个数 int i=0;//第i个字节 String writes =""; String tranString="";//中转字符串 String waiteString;//保存所转化的所有字符串 while((i<256)||(count>=8)){ //如果缓冲区的等待写入字符大于8 if (count>=8){ waiteString="";//清空要转化的的码 for (int t=0;t<8;t++){ waiteString=waiteString+writes.charAt(t); } //将writes前八位删掉 if (writes.length()>8){ tranString=""; for (int t=8;t<writes.length();t++){ tranString=tranString+writes.charAt(t); } writes=""; writes=tranString; }else{ writes=""; } count=count-8;//写出一个8位的字节 int intw=changeString(waiteString);//得到String转化为int //写入文件 fos.write(intw); }else{ //得到地i个字节的编码信息,等待写入 count=count+SaveCode[i].n; writes=writes+SaveCode[i].node; i++; } } //把所有编码没有足够8的整数倍的String补0使得足够8的整数倍,再写入 if (count>0){ waiteString="";//清空要转化的的码 for (int t=0;t<8;t++){ if (t<writes.length()){ waiteString=waiteString+writes.charAt(t); }else{ waiteString=waiteString+'0'; } } fos.write(changeString(waiteString));//写入 System.out.println("写入了->"+waiteString); } /** * 将一个八位的字符串转成一个整数 * @param s * @return */ public int changeString(String s){ return ((int)s.charAt(0)-48)*128+((int)s.charAt(1)-48)*64+((int)s.charAt(2)-48)*32 +((int)s.charAt(3)-48)*16+((int)s.charAt(4)-48)*8+((int)s.charAt(5)-48)*4 +((int)s.charAt(6)-48)*2+((int)s.charAt(7)-48); }
③ 将源文件中的所有byte 转化为 01 哈夫曼编码,写入压缩文件
这一步也比较复杂,原理同上一步,在SaveCode 中查找一个 byte 所对应的哈夫曼编码,不够 8 的整数倍的就不足,再写入。
值得注意的事,最后一定要写一个byte 表示,补了多少个 0 方便解压缩时的删除 0
//再次读入文件的信息,对应每一个字节写入编码 count=0; writes =""; tranString=""; int idata=fis.read(); //文件没有读完的时候 while ((fis.available()>0)||(count>=8)){ //如果缓冲区的等待写入字符大于8 if (count>=8){ waiteString="";//清空要转化的的码 for (int t=0;t<8;t++){ waiteString=waiteString+writes.charAt(t); } //将writes前八位删掉 if (writes.length()>8){ tranString=""; for (int t=8;t<writes.length();t++){ tranString=tranString+writes.charAt(t); } writes=""; writes=tranString; }else{ writes=""; } count=count-8;//写出一个8位的字节 int intw=changeString(waiteString); fos.write(intw);//写到文件中区 }else{ //读入idata字节,对应编码写出信息 count=count+SaveCode[idata].n; writes=writes+SaveCode[idata].node; idata=fis.read(); } } count=count+SaveCode[idata].n; writes=writes+SaveCode[idata].node; //把count剩下的写入 int endsint=0; if (count>0){ waiteString="";//清空要转化的的码 for (int t=0;t<8;t++){ if (t<writes.length()){ waiteString=waiteString+writes.charAt(t); }else{ waiteString=waiteString+'0'; endsint++; } } fos.write(changeString(waiteString));//写入所补的0
如此一来,整个的压缩过程就完毕了。
解压缩过程:
与压缩过程刚好是反着来进行的,知道的存储的方式我们就反着来读取看看。
① 读入所有字节所对应的编码长度:
//读入文件中的每一个编码的长度 for (int i=0;i<256;i++){ Code hC=new Code(); hC.n=fis.read(); hC.node=""; SaveCode[i]=hC; }
② 读入每一个字节所对应的编码
int i=0; int count=0; String coms=""; //读SaveCode中0~256字节的的数据 while (i<256){ //当缓存区的编码长度比编码[i]的长度长的时候 if (coms.length()>=SaveCode[i].n){ for (int t=0;t<SaveCode[i].n;t++){//SaveCode[i].node取得该编码 SaveCode[i].node=SaveCode[i].node+coms.charAt(t); } //把coms前这几位去掉 String coms2=""; for (int t=SaveCode[i].n;t<coms.length();t++){ coms2=coms2+coms.charAt(t); } coms=""; coms=coms2;//累计的下一个编码,继续的使用 i++; }else{ //如果已经没有写出的话,再度入一个byte转化为01 String coms=coms+IntToString(fis.read()); } }
③ 读入文件的哈夫曼编码
得注意的事,前面我们又补0 的位,所以在我们读取的时候,记得把之前所补得东西,给删除掉就 OK 了。
String rsrg;//存转换成的Sting String compString="";//存要比较的字符串 //读入文件,写出文件 while(fis.available()>1){ if (search(compString)>=0){ int cint=search(compString); fos.write(cint); //删掉前n个数据 String compString2=""; for (int t=SaveCode[cint].n;t<compString.length();t++){ compString2=compString2+compString.charAt(t); } compString=""; compString=compString2; }else{//继续读入 compString=compString+IntToString(fis.read()); } } //处理最后一个字节 int cint=fis.read(); String compString2=""; for (int t=0;t<compString.length()-cint;t++){ compString2=compString2+compString.charAt(t); } compString=compString2; //删掉前n个数据 while (compString.length()>0){ int ccint=search(compString); fos.write(ccint); compString2=""; for (int t=SaveCode[ccint].n;t<compString.length();t++){ compString2=compString2+compString.charAt(t); } compString=""; compString=compString2; }
评论
以前只是知道哈弗曼编码是用来解压缩的,但是没有真正的动手编写过,一是因为觉得这个东西很复杂,不知道如何下手,总觉得这个东西是牛人做的事情。 二:整个程
"1这个数字,用整数写进计算机硬盘去存储,占用了 2^32-1 个二进制位"
这里好像不对,整数在计算机中以4个字节进行存放,4*8=32 其实就是32个字节,而 2^32-1 是这32位二进制能表示的整数的个数或者是如果是无符号的也可以理解为最大的整数。
确实花了比较久的时间,谢谢你指出错误,我满上改正,相互学习,有助提高~
12楼的同学,其实不是32个字节, 是32个位,也就是4个字节
以前只是知道哈弗曼编码是用来解压缩的,但是没有真正的动手编写过,一是因为觉得这个东西很复杂,不知道如何下手,总觉得这个东西是牛人做的事情。 二:整个程
"1这个数字,用整数写进计算机硬盘去存储,占用了 2^32-1 个二进制位"
这里好像不对,整数在计算机中以4个字节进行存放,4*8=32 其实就是32个字节,而 2^32-1 是这32位二进制能表示的整数的个数或者是如果是无符号的也可以理解为最大的整数。
确实花了比较久的时间,谢谢你指出错误,我满上改正,相互学习,有助提高~
以前只是知道哈弗曼编码是用来解压缩的,但是没有真正的动手编写过,一是因为觉得这个东西很复杂,不知道如何下手,总觉得这个东西是牛人做的事情。 二:整个程序思路理不清出,所以不敢编,今天看了你的程序还有收获很大,3Q
"1这个数字,用整数写进计算机硬盘去存储,占用了 2^32-1 个二进制位"
这里好像不对,整数在计算机中以4个字节进行存放,4*8=32 其实就是32个字节,而 2^32-1 是这32位二进制能表示的整数的个数或者是如果是无符号的也可以理解为最大的整数。
PDF本身就是一个压缩的格式,我的哈弗曼算法只是实现了比较简单的功能,只针对于学习,没有考虑过对以压缩文件再次压缩,存在许多的BUG请不要见怪啊~
谢谢提醒~ 正在学习中,以后我会注意修改~
发表评论
-
《动感地下城》,让宅男变猛男
2011-10-03 11:11 1603动感地下城 写在之前: 好久都没有发表文章了, ... -
RGP游戏的非主流应用——虚拟地图
2011-06-30 01:02 6121RGP游戏的非主流应用——虚拟地图 写在之前: 本 ... -
一个项目完整制作过程的分享
2011-05-22 14:23 8220St书店管理系统 写在文章之前: 本项 ... -
一个项目完整制作过程的分享
2011-05-22 14:18 0St书店管理系统 写在文章之前: 本项 ... -
eclipse下的1245个图标
2011-05-19 17:23 2160eclipse下的1245个图标 大家随便拿写 ... -
超级详细解析——字模
2011-05-17 21:09 6742超级详细解析——字模 一、简介 汉字库: 即 ... -
JavaSE 的MV模式(国际化)
2011-05-14 12:13 2780JavaSE 的 MV 模式 ... -
分享一个绿色版本的 JAR TO EXE工具(附上一个视频教程)
2011-03-15 14:05 1567如题,使用灰常简单 附上一个视频教程: -
偶然玩分形 java测试
2011-03-09 13:54 2607分形世界 我从拉丁文形容词fractus(分裂的)造出了fr ... -
Oracle, SQL Server, My SQL数据分页查询语句汇总
2011-03-05 23:16 2029之前一直在学习SQL Server,然而其的分 ... -
小议MVC模式开发
2011-02-27 22:08 1289做web项目是所经常提到的mvc模式。 MVC是三个 ... -
菜鸟 利用VE、截图 快速打造仿QQ绚丽界面
2011-02-12 02:52 2957自绘菜鸟 利用VE、截图 快速打造仿QQ绚丽界面 ... -
JAVA的几个重要概念小总结
2011-01-17 12:20 1411JAVA的几个重要概念小总结 方法声明: 写一个方 ... -
几个文字编码小总结
2011-01-17 12:03 1206ASCII 我们入门学习是最 ... -
超详细解释常用网络命令
2011-01-15 12:10 1585常用网络命令 PING请求 Ping www.google ... -
达通杯 赛后感想
2010-12-23 13:09 3593比赛结束两三天了今天才抽出了时间写写心得。 其实想想自己 ... -
自己动手实现高压缩比压缩软件 超详细解释(LZW算法)
2010-12-07 17:27 5009Lzw 针对大量的子串多次重复出现的压缩 之前 ... -
JAVA BMP解码 超详细解释
2010-11-21 23:02 13418首先,对于BMP 格式的图片大家都不感觉到陌生吧。 ... -
Java 挂链 Hash表 手动实现
2010-11-19 13:08 2189前些天一直在纠结的 ... -
五子棋 图片版
2010-11-16 12:45 5532近来发现自绘的东西怎么都比不了自己PS加载图片所作的界面好看。 ...
相关推荐
通过阅读和理解这些源码,可以深入学习哈夫曼编码算法的实现细节,并了解如何将其应用于实际的压缩软件开发中。 总结来说,哈夫曼树压缩算法利用了数据的统计特性,通过构建最优二叉树实现高效的数据编码,进而完成...
"哈夫曼编码实现图像压缩" 哈夫曼编码是一种常用的压缩编码算法,采用变长码编码,属于无损压缩算法的一种。这便使编码之后的字符串的平均期望长度降低,从而达到无损压缩数据的目的。在无损压缩的编码范畴中,...
《哈夫曼编码在压缩软件中的应用与实现》 哈夫曼编码,作为一种高效的数据压缩方法,被广泛应用于各类压缩软件中。它基于频率最小的编码原则,通过构建最优的二叉树结构来实现对数据的高效编码。在这个项目中,我们...
在“利用哈夫曼原理的压缩解压缩软件”中,哈夫曼编码被应用于文件的压缩与解压缩过程。 MFC(Microsoft Foundation Classes)是微软开发的一种C++库,用于构建Windows应用程序。它提供了丰富的类结构,使得开发者...
哈夫曼编码是一种高效的数据编码方法,主要用于无损数据压缩,它通过构建最优的二叉树来实现数据的高效表示。在本项目中,"用哈夫曼实现的无损压缩和解压" 包含了两个部分:Compress 和 Decompress。Compress 文件夹...
在提供的文件列表中,`main.c`可能是实现哈夫曼编码算法的C语言源代码,而`H.txt`和`A.txt`是待压缩的文本文件。`H.zip`可能是压缩后的结果,包含压缩后的文本和哈夫曼树信息。`2.cbp`和`2.layout`可能与开发环境或...
利用哈夫曼编码思想,设计对一个文本文件(.txt)中的字符进行哈夫曼编码,生成编码压缩文件(.txt),并且还可将压缩后的文件进行解码还原为原始文本文件(.txt)。 实现的功能: (1)压缩:实现对文件的压缩,生成...
《哈夫曼实现文件压缩的实验报告》详细解读 该实验报告主要介绍了如何利用哈夫曼编码实现文件的压缩和解压缩。哈夫曼编码是一种数据压缩方法,它基于字符出现频率,通过构建哈夫曼树来生成最优的二进制编码,从而...
在"哈夫曼实现压缩解压缩——源代码"中,我们可以期待看到一个用C语言在Linux环境下实现的哈夫曼编码和解码过程。 哈夫曼编码的过程主要包括以下步骤: 1. **构建哈夫曼树**:首先,统计所有字符的出现频率,创建...
在这个项目中,我们看到的是一个用C++实现的哈夫曼算法,用于图像压缩。这个程序包括了编码和解码两个过程,可以从`in.bmp`输入图像,通过`Compressor.cpp`中的算法进行压缩,将结果保存到`encode.dat`文件中,然后...
本文将详细介绍如何使用哈夫曼树进行文件压缩,并结合QT5.12框架实现可视化界面。 一、哈夫曼编码原理 1. 频率统计:首先,对文件中的每个字符进行频率统计,计算出每个字符出现的次数。 2. 哈夫曼树构造:通过...
在“基于哈夫曼编码的文本文件压缩与解压缩.zip”这个压缩包中,很可能包含了用于演示或教学目的的哈夫曼编码实现代码、压缩和解压缩的示例文本以及相应的结果文件。学习和理解这个压缩包的内容,可以帮助我们更好地...
下面将详细介绍哈夫曼编码的原理、构建过程以及在Java中的实现。 1. **哈夫曼编码原理**: 哈夫曼编码是建立在频率统计基础上的,通过对输入文本中各个字符出现频率的统计,构造一棵特殊的二叉树——哈夫曼树。在...
在C++中实现哈夫曼树压缩与解压涉及到几个主要步骤,包括构建哈夫曼树、生成哈夫曼编码、编码数据以及解码数据。 1. **哈夫曼树的构建** - 首先,统计输入文本中每个字符出现的频率,形成一个频率列表。 - 接着,...
标题中提到的"114243 用哈夫曼编码实现文件压缩 doc"是一份实验报告,描述了如何使用哈夫曼编码来实现文件的压缩。哈夫曼编码是一种数据编码方法,常用于无损数据压缩,它通过为出现频率较高的字符分配较短的编码,...
在C++中实现哈夫曼压缩软件,我们需要理解以下几个核心概念和技术: 1. **哈夫曼树**:哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树。构建哈夫曼树的过程是通过合并频度最低的两个节点来逐渐构建整个...
实验内容:写出程序,利用哈弗曼编码实现对文件的压缩,并能解压文件。 实验步骤: 1、压缩 (1) 统计原始文件中各字节出现的概率(次数); (2) 采用哈弗曼算法对各字节进行编码,建立哈弗曼对照表; a) 构造...
本报告详细介绍了以哈夫曼编码实现软件压缩的课程设计,报告共25页,涵盖了从理论基础到软件实现的各个方面。报告首先对数据结构的基本概念进行阐述,为后续的排序算法比较和哈夫曼编码实现打下理论基础。排序算法在...
基于哈夫曼树的压缩软件 C++ 知识点一:哈夫曼编码原理 哈夫曼编码是一种_variable-length prefix code_,它的主要思想是将频繁出现的字符编码短,较少出现的字符编码长,以此来减少所占用的空间。哈夫曼编码的主要...