哈夫曼压缩：
进行哈夫曼压缩首先要知道什么是哈夫曼树。
哈夫曼树是最优的二叉树，最优指的是带权路径最短的树。
那么如何建立一个哈夫曼树呢？
实现步骤：
1.给定大小无序的数据，首先把数据存储起来，然后再对数据进行排序。
2.创建节点类，节点类中要包含（左、右子节点的引用和数据值）
3.构建哈夫曼树：
每次取两个最小的数据，实例化两个节点，建立一个新节点，其数据值为取出的两个数据值之和，并将新节点作为两个节点的
父节点加到存储容器中，并让容器移除取出的两个节点。重复上述步骤，知道容器中只有一个节点，它就是哈夫曼树的根节点。
哈夫曼压缩思路：
1.读文件，统计每个字符出现的次数。将次数存储在数组中。
2.根据出现的次数对其进行排序（通过优先队列），建立节点将其加入优先队列中。
3.构建哈弗曼树。将队列中的前两个元素移除并得到其出现次数构成新节点，加入队列中。重复以上步骤，直到队列中没有元素。
4.遍历树，得到每个叶子节点的编码。
5.写头文件，对编码进行处理，不足8位在前补0，够8位则写入。
我在压缩时写头文件主要写了各个编码的长度，各个编码。
写文件内容，8位8位的写入，不足8位则补0。
6.解压
首先把编码长度读出，接着读编码。这里需要注意，我在写头文件时并没把该读多少字节写入，但前面我已经把各个编码长度读出来了
所以我还是8位8位的读，当读出字符串长度大于SaveCode[i].length的长度时就把它赋给SaveCode[i].node，这就是它的编码
读内容时是同样的道理，根据读到的字符串与编码进行匹配，匹配成功时读出，不成功就继续读。
下面是哈夫曼压缩代码：
public class HfmMain {
public int bytecount[]=new int [256];//创建存储压缩内容中每个字符出现的次数
static hfmNode root;
static Code[] SaveCode=new Code[256];
public static void main(String []args) throws Exception{
HfmMain hm = new HfmMain();
String filename = "C:\\Users\\aa\\Desktop\\蓝杰 java\\sss.txt";
String name="C:\\Users\\aa\\Desktop\\蓝杰 java\\aaa.txt";
hm.read(filename);
hm.createTree();
hm.printTree(root);
hm.createSaveCode();
hm.getMB(root, "");
hm.printSaveCode();
UtilCode uc=new UtilCode(SaveCode);
uc.writefile(filename);
DeCode dc=new DeCode(SaveCode);
dc.Decode(filename+".hfrq", name);
}
/**
* 创建读文件的方法
* @param filename
* @throws Exception
*/
public void read(String filename) throws Exception{
//实例化输入流对象
InputStream ins = new FileInputStream(filename);
while(ins.available()>0){
int i = ins.read();
bytecount[i]++;
}
}
/**
* 创建哈弗曼树
*/
public void createTree(){
PriorityQueue<hfmNode> hfmqueue = new PriorityQueue<hfmNode>();
for(int i=0;i<bytecount.length;i++){
if(bytecount[i]!=0){
hfmNode node = new hfmNode(i,bytecount[i]);
hfmqueue.add(node); //向优先队列中加入节点
}
}
while(hfmqueue.size()>1){
hfmNode min1 = hfmqueue.poll();
hfmNode min2 = hfmqueue.poll();
hfmNode result = new hfmNode(0,min1.times+min2.times);
result.lchild=min1;
result.rchild=min2;
hfmqueue.add(result);
}
root = hfmqueue.peek();
}
/**
* 给叶子节点加编码的方法
*/
public void getMB(hfmNode node,String s){
if(node.lchild==null&&node.rchild==null){
Code c = new Code();
c.length=s.length();
c.code=s;
SaveCode[node.obj]=c;
}
if(node.lchild!=null){
getMB(node.lchild,s+'0');
}
if(node.rchild!=null){
getMB(node.rchild,s+'1');
}
}
/**
* 输出树
* @param node
*/
public void printTree(hfmNode node){
if(node==null){
return ;
}else{
System.out.println("次数: "+node.times+" 元素: "+node.obj);
printTree(node.lchild);
printTree(node.rchild);
}
}
/**
* 初始化存储编码的数组
*/
public void createSaveCode(){
for(int i=0;i<256;i++){
Code c=new Code();
c.code="";
c.length=0;
SaveCode[i]=c;
}
}
public void printSaveCode(){
for(int i=0;i<256;i++){
System.out.println(i+" :"+SaveCode[i].length+" "+SaveCode[i].code);
}
}
}
/**
* 压缩的方法
* @author lsx
*/
public class UtilCode {
Code SaveCode[];
/**
* 构造函数
* @param bytecount 表示存储字符出现次数的数组
*/
public UtilCode(Code SaveCode[]){
this.SaveCode=SaveCode;
}
/**
* 写文件的方法
* @throws Exception
*/
public void writefile(String filename) throws Exception{
//创建输入流对象
InputStream ins = new FileInputStream(filename);
//创建输出流对象
OutputStream os = new FileOutputStream(filename+".hfrq");
//写头信息
os.write((int)'h');
os.write((int)'f');
os.write((int)'r');
os.write((int)'q');
//写各个字符的编码长度
for(int i=0;i<256;i++){
os.write(SaveCode[i].length);
System.out.println(i+"点的编码长："+SaveCode[i].length);
}
//写编码内容
int i=0;
int count=0; //当前字符串长度
String write="";
String transwrite="";
String waitwrite="";
while((i<256)||count>=8){
if(count>8){
//将前8位写入
waitwrite="";
for(int t=0;t<8;t++){
waitwrite+=write.charAt(t);
}
if(write.length()>8){
transwrite="";
for(int t=8;t<write.length();t++){
transwrite+=write.charAt(t);
}
write="";
write=transwrite;
}else{
write="";
}
count-=8;
os.write(changeString(waitwrite));
System.out.println("写入了头--->"+waitwrite+" "+changeString(waitwrite));
}else{
count+=SaveCode[i].length;
write+=SaveCode[i].code;
i++;
}
}
if(count>0){
waitwrite="";
for(int t=0;t<8;t++){
if(t<write.length()){
waitwrite+=write.charAt(t);
}else{
waitwrite+='0';
}
}
os.write(changeString(waitwrite));
System.out.println("写入了头--->"+waitwrite+" "+changeString(waitwrite));
}
// **********************************************************************************
//写文件内容
count=0;
write="";
transwrite="";
waitwrite="";
int data = ins.read();
while(ins.available()>0||count>=8){
if(count>8){
waitwrite="";
for(int t=0;t<8;t++){
waitwrite+=write.charAt(t);
}
if(write.length()>8){
transwrite="";
for(int t=8;t<write.length();t++){
transwrite+=write.charAt(t);
}
write="";
write=transwrite;
}else{
write="";
}
count-=8;
os.write(changeString(waitwrite));
System.out.println("写入了内容-->"+waitwrite+" "+changeString(waitwrite));
}else{
count+=SaveCode[data].length;
write+=SaveCode[data].code;
data=ins.read();
}
}
count+=SaveCode[data].length;
write+=SaveCode[data].code;
int end = 0;
if(count>0){
waitwrite="";
for(int t=0;t<8;t++){
if(t<write.length()){
waitwrite+=write.charAt(t);
}else{
waitwrite+='0';
end++;
}
}
os.write(changeString(waitwrite));
System.out.println("写入了内容-->"+waitwrite+" "+changeString(waitwrite));
}
os.write(end);
System.out.println("压缩完成");
}
/**
* 将8位的字符串转换成一个整数
*/
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);
}
}
public class DeCode {
Code SaveCode[];
/**
* 构造方法
* @param SaveCode
*/
public DeCode(Code SaveCode[]){
this.SaveCode=SaveCode;
}
/**
* 解压方法
* name要解压的文件名
* filename解压到的文件名
* @throws Exception
*/
public void Decode(String name,String filename) throws Exception{
//创建输入流对象
InputStream ins=new FileInputStream(name);
// BufferedInputStream bis=new BufferedInputStream(ins);
if(ins.read()!='h'){
System.out.println(" Not a .hfrq file ");
}
if(ins.read()!='f'){
System.out.println(" Not a .hfrq file ");
}
if(ins.read()!='r'){
System.out.println(" Not a .hfrq file ");
}
if(ins.read()!='q'){
System.out.println(" Not a .hfrq file ");
}
//读SaveCode中的编码长度
for(int i=0;i<256;i++){
Code c=new Code();
//读编码长度
c.length=ins.read();
System.out.println("SaveCode["+i+"]:"+c.length);
c.code="";
//将编码对象存到数组中
SaveCode[i]=c;
}
System.out.println("各个点都有了值");
int i=0;
String coms="";
//读SaveCode中的编码
while (i<256){
if (coms.length()>=SaveCode[i].length){
//先把这b[i].n位给b[i].node
for (int t=0;t<SaveCode[i].length;t++){
SaveCode[i].code=SaveCode[i].code+coms.charAt(t);
}
System.out.println("b["+i+"]:"+SaveCode[i].length+" "+SaveCode[i].code);
//把coms前这几位去掉
String coms2="";
for (int t=SaveCode[i].length;t<coms.length();t++){
coms2=coms2+coms.charAt(t);
}
coms="";
coms=coms2;
i++;
}else{
coms=coms+changeint(ins.read());
}
}
//创建输出流对象
OutputStream os=new FileOutputStream(filename);
String compString="";
while(ins.available()>1){
if(search(compString)>=0){
int intw=search(compString); //得到了当前字符的acsii码
System.out.println("写入了："+"int:"+intw+" "+changeint(intw)+" ="+compString);
os.write(intw); //将当前字符写入文件
String compString2="";
//删除前n个元素
for(int t=SaveCode[intw].length;t<compString.length();t++){
compString2+=compString.charAt(t);
}
compString="";
compString=compString2;
}else{
compString+=changeint(ins.read());
}
}
int end = ins.read(); //最后一个，表示补0的个数
String compString2="";
for(int t=0;t<compString.length()-end;t++){
compString2+=compString.charAt(t);
}
compString = "";
compString = compString2;
while (compString.length()>0){
int ccint=search(compString);
os.write(ccint);
// System.out.println("写入了："+compString);
compString2="";
for (int t=SaveCode[ccint].length;t<compString.length();t++){
compString2=compString2+compString.charAt(t);
}
compString="";
compString=compString2;
}
ins.close();
os.flush();
os.close();
System.out.println("解码完毕！");
}
/**
* 将1个整数转换成8位字符串
*/
public String changeint(int n){
int n0=n;
String s="";
for(int i=0;i<8;i++){
if((n0%2)==0){
s='0'+s;
}else if((n0%2)==1){
s='1'+s;
}
n0=n0/2;
}
return s;
}
/**
* 找到编码所对应的位置
*/
public int match(String s){
for(int i=0;i<256;i++){
if(SaveCode[i].length==s.length()&&(SaveCode[i].code.equals(s))){
return i;
}
}
return -1;
}
public int search(String s){
int i;
int num=-1;
String ss="";
for(i=0;i<s.length();i++){
ss+=s.charAt(i);
num=match(ss);
if(num>=0){
break;
}
}
if(i<s.length()){
return num;
}else {
return -1;
}
}
}
出现的问题：最后的时候要把输入输出流关闭，否则在解压过程中读取文件内容时最后一位会没有与之匹配的编码，从而导致数组下标越界，而解压
的文件会少写入一位。
要点：理清思路，写文件时要明白自己写了哪些内容，是按什么顺序写入的，读的时候按顺序读出。
分享到：
相关推荐
哈夫曼编码是一种高效的数据压缩方法，由大卫·哈夫曼在1952年提出。它是基于一种称为哈夫曼树（也叫最优二叉树）的数据结构。在这个课程设计中，你将深入理解哈夫曼编码的原理，并通过C++编程语言实现文件的压缩与...
总结，哈弗曼压缩是一种基于频率的编码方法，它通过构建哈弗曼树来实现对数据的有效压缩。在Java中，可以通过分析给定的源码文件了解并实现这一过程，这有助于提高对数据压缩原理和算法的理解。
总结来说，哈夫曼树压缩算法利用了数据的统计特性，通过构建最优二叉树实现高效的数据编码，进而完成数据的压缩。在实际应用中，这种算法广泛应用于文本、图像和音频等数据的压缩，提高了存储和传输的效率。
总结来说，哈夫曼压缩技术是一种基于频率的无损数据压缩方法，特别适合处理包含重复元素的数据。虽然在处理图像压缩时可能效率较低，但与其他算法结合使用时，如EZW，可以提升压缩效果。在实际应用中，哈夫曼编码常...
哈夫曼编码是一种高效的数据压缩编码技术，由美国科学家大卫·哈夫曼在1952年提出。这种编码方式是基于信源符号的概率分布，通过构建最优的二叉树来实现，使得出现频率高的符号拥有较短的编码，而出现频率低的符号...
总结来说，这个小工具通过哈夫曼编码技术实现了文件的压缩和解压缩，利用了数据的频率特性，尤其适用于那些含有大量重复字符的文件。同时，哈夫曼编码的原理和实现也是计算机科学中经典的数据压缩理论，对于理解和...
在哈夫曼压缩与解压软件的实现中，MFC提供了图形用户界面（GUI）的构建基础，包括对话框、控件和文件操作类，使得开发者能够更加专注于算法的实现，而无需过多关注底层的Windows API。 哈夫曼编码的核心步骤包括： ...
总结起来，哈夫曼树和小顶堆在文件压缩中的应用是一项高效的技术，通过优化编码长度，有效减少了文件大小。在实现过程中，理解并掌握这两个数据结构的操作是至关重要的。通过FileCompress.h、Heap.h和HaffmanTree.h...
总结来说，Java哈夫曼编码是利用数据结构和算法理论实现的一种压缩技术，它在处理大量重复字符的数据时表现优秀。通过合理地分配编码长度，哈夫曼编码可以有效地减少存储空间，同时保持数据的可恢复性，因此在文本...
在实际的哈夫曼压缩过程中，我们先遍历输入文件中的每个字符，根据哈夫曼编码表将其转换为二进制序列，然后将所有二进制序列连接起来形成一个大的二进制串。这个二进制串就是压缩后的文件，可以写入到名为"2文件"的...
总结来说，哈夫曼压缩是一种高效的无损数据压缩方法，基于字符频率构建特殊的二叉树并生成前缀编码。它在数据存储、传输和各种文件格式中都有广泛应用，并可以通过各种编程工具和库进行实现和操作。
总结来说，哈夫曼编码是一种基于字符频率的压缩技术，它通过构建哈夫曼树并生成编码来实现数据压缩。在“哈夫曼编码压缩解压文件”的过程中，理解哈夫曼树的构建、编码的生成以及压缩和解压的步骤至关重要。掌握这些...
《哈夫曼编码在压缩软件中的应用与实现》 哈夫曼编码，作为一种高效的数据压缩方法，被广泛应用于各类压缩软件中。它基于频率最小的编码原则，通过构建最优的二叉树结构来实现对数据的高效编码。在这个项目中，我们...
总结，Java哈夫曼压缩和解压涉及对数据编码、构建哈夫曼树、生成编码表、解码等过程，通过高效的数据结构和算法实现高效的数据压缩。了解和掌握哈夫曼编码不仅有助于理解数据压缩原理，也是提升软件开发效率的重要...
总结来说，哈夫曼编码是一种基于字符频率的无损数据压缩方法，通过构建哈夫曼树来生成编码，并据此进行数据的压缩和解压缩。在VC环境下，可以编写C++程序来实现这一过程，从而提高数据存储和传输的效率。
《哈夫曼压缩解压数据结构设计》报告 在数据处理和存储中，文献压缩是一种重要的技术，旨在减少数据的存储需求。哈夫曼编码是一种高效的数据压缩方法，基于字符出现频率进行编码，使得出现频繁的字符具有较短的编码...
哈夫曼树总结习题学时PPT课件.pptx 哈夫曼树是一种特殊的二叉树，它的路径长度最短，是一种非常重要的数据结构。哈夫曼树的构造是通过Huffman算法来实现的，该算法将n个权值构成n棵独立二叉树的森林，然后不断地...
哈夫曼编码是一种高效的数据压缩方法，主要用于无损数据压缩，其原理基于频率最小的字符用最短的编码，频率最高的字符用最长的编码。在本课程设计中，学生将深入理解并应用哈夫曼编码的理论，实现一个能够进行压缩...
总结来说，哈夫曼压缩解压缩是通过构建哈夫曼树，根据字符出现的频率为其分配不同的二进制编码，从而实现文件的高效压缩和解压缩。在具体实现时，需要设计合适的数据结构和算法来支持这一过程，同时保证压缩前后文件...
在Java编程中，哈夫曼编码（Huffman Coding）是一种数据压缩算法，它基于字符出现频率构建最优前缀树（也称为哈夫曼树），从而为每个字符分配一个唯一的二进制编码。这个编码方法使得频繁出现的字符拥有较短的编码，...