- 浏览: 202422 次
- 性别:
- 来自: 长沙
-
最新评论
-
螺旋懒虫：
原本是想自己画点阵的，一来画的不标准，也不好解析（用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请不要见怪啊~
刚写了一个C++的 今晚的题目 呵呵谢谢提醒~
正在学习中，以后我会注意修改~
我这有C++版本的……是数据结构课程设计的题目……呵呵发表评论
-
《动感地下城》，让宅男变猛男
2011-10-03 11:11 1555动感地下城 写在之前： 好久都没有发表文章了， ... -
RGP游戏的非主流应用——虚拟地图
2011-06-30 01:02 6048RGP游戏的非主流应用——虚拟地图 写在之前： 本 ... -
一个项目完整制作过程的分享
2011-05-22 14:23 8193St书店管理系统 写在文章之前： 本项 ... -
一个项目完整制作过程的分享
2011-05-22 14:18 0St书店管理系统 写在文章之前： 本项 ... -
eclipse下的1245个图标
2011-05-19 17:23 2099eclipse下的1245个图标 大家随便拿写 ... -
超级详细解析——字模
2011-05-17 21:09 6571超级详细解析——字模 一、简介 汉字库： 即 ... -
JavaSE 的MV模式（国际化）
2011-05-14 12:13 2716JavaSE 的 MV 模式 ... -
分享一个绿色版本的 JAR TO EXE工具（附上一个视频教程）
2011-03-15 14:05 1535如题，使用灰常简单 附上一个视频教程： -
偶然玩分形 java测试
2011-03-09 13:54 2545分形世界 我从拉丁文形容词fractus（分裂的）造出了fr ... -
Oracle, SQL Server, My SQL数据分页查询语句汇总
2011-03-05 23:16 1984之前一直在学习SQL Server，然而其的分 ... -
小议MVC模式开发
2011-02-27 22:08 1231做web项目是所经常提到的mvc模式。 MVC是三个 ... -
菜鸟 利用VE、截图 快速打造仿QQ绚丽界面
2011-02-12 02:52 2923自绘菜鸟 利用VE、截图 快速打造仿QQ绚丽界面 ... -
JAVA的几个重要概念小总结
2011-01-17 12:20 1377JAVA的几个重要概念小总结 方法声明： 写一个方 ... -
几个文字编码小总结
2011-01-17 12:03 1174ASCII 我们入门学习是最 ... -
超详细解释常用网络命令
2011-01-15 12:10 1555常用网络命令 PING请求 Ping www.google ... -
达通杯 赛后感想
2010-12-23 13:09 3556比赛结束两三天了今天才抽出了时间写写心得。 其实想想自己 ... -
自己动手实现高压缩比压缩软件 超详细解释（LZW算法）
2010-12-07 17:27 4942Lzw 针对大量的子串多次重复出现的压缩 之前 ... -
JAVA BMP解码 超详细解释
2010-11-21 23:02 13272首先，对于BMP 格式的图片大家都不感觉到陌生吧。 ... -
Java 挂链 Hash表 手动实现
2010-11-19 13:08 2151前些天一直在纠结的 ... -
五子棋 图片版
2010-11-16 12:45 5492近来发现自绘的东西怎么都比不了自己PS加载图片所作的界面好看。 ...
相关推荐
哈夫曼编码实现文本文件的压缩，可作为数据压缩作业的参考
利用哈夫曼编码思想，设计对一个文本文件（.txt）中的字符进行哈夫曼编码，生成编码压缩文件（.txt），并且还可将压缩后的文件进行解码还原为原始文本文件（.txt）。 实现的功能： (1)压缩：实现对文件的压缩，生成...
实验内容：写出程序，利用哈弗曼编码实现对文件的压缩，并能解压文件。 实验步骤： 1、压缩 （1） 统计原始文件中各字节出现的概率（次数）； （2） 采用哈弗曼算法对各字节进行编码，建立哈弗曼对照表； a) 构造...
利用哈夫曼算法实现压缩解压缩，Linux c
用哈夫曼实现的无损压缩和解压 压缩包中Compress的是压缩有关的所有代码，Decompress是与解压有关的所有代码，编译时需加上 -std=c++11参数
使用哈夫曼编码实现对文本文件的压缩和解压缩
利用mfc写的一个压缩软件，利用哈夫曼的原理，可以对文件进行压缩和解压缩（软件支持txt和doc，可以自行更改）。运用了移位运算，有进度条和动态文字。
这是我做的一个基于哈夫曼树思想的压缩算法程序源码，希望大家指正
数据结构课程设计用哈夫曼编码实现文件压缩： 一、实验题目： 用哈夫曼编码实现文件压缩 二、实验目的： 1、了解文件的概念。 2、掌握线性链表的插入、删除等算法。 3、掌握Huffman树的概念及构造方法。 4、掌握...
该代码实现哈夫曼基本算法，并对输入的图片进行压缩，最终输出译码后的图片，代码真实可用，想理解学习哈夫曼压缩的同学可以看看。
用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAME IS MY FAVORITE”。 字符 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N ...
报告中不仅有完整的哈夫曼树实现文件的压缩和解压缩功能，还有算法的结构流程图和主函数的简单结构图，程序中有中文注释，可读性比较强，文末还附有本人的心得体会
这是学校数据结构与算法设计课程的PJ，旨在实现类似zip软件的压缩与解压功能。我在几乎有空就在写代码的情况下两周完成了这个项目。 目前网上能够搜索到的资料对于单个文件和文本文件的压缩与解压较多，而对文件夹与...
哈夫曼编码进行文本压缩
114243 用哈夫曼编码实现文件压缩 doc
根绝哈夫曼编码写的数据压缩解压软件
哈夫曼编码压缩解压缩软件，加强对哈夫曼编码方式的理解
利用无失真信源编码方法中的哈夫曼编码进行程序设计实践，实现对文件的压缩与解压操作。
草稿版代码 内容超详细 可压缩任何文件类型 亲测可用 100%还原