这篇总结存到草稿箱也有三个月了，嘿嘿...
学到哈夫曼压缩的时候首先就得了解哈夫曼树，我想说，对于数据结构挂科的人来说，额，这是一个沉重的话题。不过我还真感谢老师把我的数据结构挂了，因为我那一学期根本没
听课，考试时什么都不会，而后来为了补考悬梁刺股的，当然没这里强悍，总之是还是下了很大的功夫，因此补考通过，哈夫曼树俺也理解了，为哈夫曼压缩做好了铺垫。哈夫曼树是一种由下往上构建的树形结构，只会在叶子结点上存储，从而每个存储的值都有特定的唯一的编码。具体就不再细细阐述了。
而哈夫曼压缩原理的官方（即百度百科）解释是：通过某种特殊的编码方式将数据信息中存在的重复度、冗余度有效地降低，从而达到数据压缩的目的。
个人理解压缩就是把原本文件一个一个的字节重新按照制定的新的规则来编码。因此哈夫曼压缩的步骤就是：一. 读取文件，创建哈夫曼树——> 二.根据哈夫曼树得到哈夫曼编码——> 三.根据编码再次读取文件进行压缩，生成压缩文件。——> 四.解压缩
一. 读取文件，创建哈夫曼树。
1).定义一个长度为255的int数组，将读取字符对应的ASC码(所以只需要255的大小)做为数组下标进行+1操作，这样有利于保存每个字符出现的频次。
2).将频次表存入Map中，将下标ASC码作为Key,出现的频次作为Value。
3).遍历Map,每次找出最小两个Value,将Key作为叶子结点，其Value的和作为父亲结点的Value构建成一个最小树,父亲结点以"n"+"i"作为Key；返回父亲结点，添加到Map中，并在Map中移除两个叶子结点。 *：关于这点很值得吐槽一下，其实Java中有一个优先队列不需要自己比较，直接可以从中拿到最小两个值，用完后再移除掉，但是自己写的Map比较因为一直用一个文件测试，结果有一天我换了文件就出错了，原来Map最后三个排序时真是很不容易啊，有（小中大），（小大中），（大中小）等各种极端情况都要考虑。
4).不断循环(3)操作,直至Map为空。
try {
System.out.println("读取文件：" + subFile);
// 读取文件的ASC码值，获得出现频次。
while (is.available() > 0)
asc[is.read()]++;
int i = 0;
while (i < asc.length) {
if (asc[i] != 0) {
// System.out.println("得到频次表为：asc[" + i + "]==" + asc[i]);
String key = "" + i;// 频次表存放的asc码值
Integer value = asc[i];// 频次表所对应asc码出现的次数
map.put(key, value);
}
i++;
}
// 关闭输入输出流
is.close();
// System.out.println("输出频次map表：(共有" + map.size() + "条)");
workByEntry(map);// 输出频次表的map
String k1 = null, k2 = null;
Set<Map.Entry<String, Integer>> set = map.entrySet();
Map.Entry<String, Integer> entry = null ;
while (true) {
int vamin1 = 256, vamin2 = 256,num = 1;
// 遍历频次map表，找出两个最小值
for (Iterator<Map.Entry<String, Integer>> it = set.iterator(); it
.hasNext();) {
if (map.size() == 2) {// 构建HFM树的最后两个结点需要单独取出
System.out.println("倒数第二个结点为："+map.get("n"+(pd-1)));
vamin1 = map.get("n" + (pd - 1));
k1 = "n" + (pd - 1);
map.remove("n" + (pd - 1));
System.out.println("倒数第一个结点为："+map.get("n"+(pd)));
vamin2 = map.get("n" + (pd));
k2 = "n" + pd;
map.remove("n" + pd);
break;
} else {
entry= (Map.Entry<String, Integer>) it
.next();
String key = entry.getKey();
Integer value = entry.getValue();
if (value < vamin1&&!(num==map.size()-1)) {//极端情况一：当遇到最后三个权值递减排列时
vamin1 = value;
k1 = key;
} else if(value < vamin2){
vamin2 = value;
k2 = key;
}else if(num==map.size()-1&&vamin2==256){//极端情况二：当遇到最后三个权值排列为中，大，小时
// 遍历频次map表，找出两个最小值
Iterator<Map.Entry<String, Integer>> it1 = set.iterator();
Map.Entry<String, Integer> entry1= (Map.Entry<String, Integer>) it1.next();
k2 = entry1.getKey();
vamin2 = entry1.getValue();
}
num++;
}
}
//将取出的最小值移除
map.remove(k1);
map.remove(k2);
if(vamin2==256||vamin1==256){
System.out.println(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>出现错误！！！");
break;
}
System.out.println("最小值一为：" + vamin1 + "其key为：" + k1);
System.out.println("最小值二为：" + vamin2 + "其key为：" + k2);
//TODO 2.传递过去两个最小值构成最小树，返回父节点value，即传递过去的频次之和。
Integer newValue = creaHFM(k1, k2, vamin1, vamin2);// 2
//将父节点添加进入map进行排序
map.put("n" + (pd), newValue);
if(map.size()<=3){
Set<String> keySet = map.keySet();//获取map的key值的集合，set集合
for(Object obj:keySet){//遍历key
System.out.println("key:"+obj+",Value:"+map.get(obj));//输出键与值
}
}
System.out.println("map的大小： "+map.size());
if (map.size() < 2||map.size()>90) {
break;
}
}
//打印哈夫曼树
System.out.println("生成的哈夫曼树结构如下：“打印格式是node(left,right)”");
PrintTree(nodepraent);
//TODO 3.传递哈夫曼树创建码表
creatMaBiao(nodepraent);
//TODO 4.开始编码
creatCompressionFile();
} catch (FileNotFoundException e1) {
System.out.println("指定的文件不存在！");
} catch (IOException e1) {
System.out.println("IO流异常！");
}
private static int pd = 0;
private static NodeTree nodepraent, nodeleft, noderight;
NodeTree nodepraent1[] = new NodeTree[100000]; //TODO 大小问题
/**
* 2.根据频次表生成HFM树
*/
private Integer creaHFM(String k1, String k2, int vamin1, int vamin2) {
nodepraent = new NodeTree("n" + (++pd));
int i;
//判断左结点是否路径结点
//两节点都不是路径结点
if (!(k1.substring(0, 1)).equals("n")
&& !(k2.substring(0, 1)).equals("n")) {
nodeleft = new NodeTree(k1);
noderight = new NodeTree(k2);
}
//左右结点都是路径结点
else if ((k2.substring(0, 1)).equals("n")
&& (k1.substring(0, 1)).equals("n")) {
String regEx = "[^0-9]";
Pattern p = Pattern.compile(regEx);
Matcher m = p.matcher(k1);
i = Integer.parseInt(m.replaceAll("").trim(), 10);
nodeleft = nodepraent1[i];
i = Integer.parseInt((p.matcher(k2)).replaceAll("").trim(), 10);
noderight = nodepraent1[i];
}//左结点是否路径结点
else if ((k1.substring(0, 1)).equals("n")
&& (!(k2.substring(0, 1)).equals("n"))) {
String regEx = "[^0-9]";
Pattern p = Pattern.compile(regEx);
Matcher m = p.matcher(k1);
i = Integer.parseInt(m.replaceAll("").trim(), 10);
nodeleft = nodepraent1[i];
noderight = new NodeTree(k2);
}
//右结点是否路径结点
else if ((k2.substring(0, 1)).equals("n")
&& (!(k1.substring(0, 1)).equals("n"))) {
String regEx = "[^0-9]";
Pattern p = Pattern.compile(regEx);
Matcher m = p.matcher(k2);
i = Integer.parseInt(m.replaceAll("").trim(), 10);
noderight = nodepraent1[i];
nodeleft = new NodeTree(k1);
}
nodepraent.leftnext = nodeleft;
nodepraent.rightnext = noderight;
nodeleft.setParents(nodepraent);
noderight.setParents(nodepraent);
nodepraent1[pd] = nodepraent;
Integer value = (vamin1 + vamin2);
return value;
}
/**
* 采用递归的方法打印哈夫曼树，按先序方式排序，显示的格式是node(left,right)
*/
public void PrintTree(NodeTree node) {
NodeTree left, right;
if (node != null) {
System.out.println(node.getObj());
left = node.getLeftnext();
right = node.getRightnext();
if (left != null || right != null){
if((!((String) node.getLeftnext().getObj()).matches("[0-9]+")))
left.setObj(left.getObj()+"-0");
if((!((String) node.getRightnext().getObj()).matches("[0-9]+")))
right.setObj(right.getObj()+"-1");
System.out.println("("+(left != null ? left.getObj() : " ")
+","+(right != null ? right.getObj() : " ") + ")");
}
if (left != null){
PrintTree(left);
}
if (right != null){
PrintTree(right);
}
}
}
二.根据哈夫曼树得到哈夫曼编码。
自己规定哈夫曼树向左为0，向右为1。为了便于操作，再一次遍历Map,若是路径结点，便在其Key的最后追加"0/1"。
每次从根节点开始读取，读取到第一个没出现过的叶子结点为止，即可产生哈夫曼编码。将哈夫曼编码存入一个255大小的String数组，下标为出现的ASC码(所以只需要255的大小)，值为01字符串码表。
/**
* 3.根据哈夫曼树创建码表，左为0，右为1
*/
private void creatMaBiao(NodeTree node) {
NodeTree left, right;
StringBuffer mabiao ;//存储二进制码表
if (node != null) {
left = node.getLeftnext();
right = node.getRightnext();
//判断是否是叶子结点，即是否存储值的结点
if(((String) node.getObj()).matches("[0-9]+")){
int a = Integer.parseInt(((String) node.getObj()));
int i;
for(i=0;i<255;i++){
if(val[i]==a)
break;
}
if(i==255){//是第一次出现
val[a] = a;
mabiao = new StringBuffer("");
//TODO 先递归产生码表
mabiao = Mabiao(node,mabiao);
if(n%2==1)
mabiao = mabiao.append("0");
else
mabiao = mabiao.append("1");
n++;
//将String转换为StringBuffer数组中存储并输出
mb[a]=mabiao.toString();
creatMaBiao(nodepraent);//递归调用
}
}
if (left != null){
creatMaBiao(left);
}
if (right != null){
creatMaBiao(right);
}
}
}
/**
* 向根节点递归产生码表
*/
private StringBuffer Mabiao(NodeTree node,StringBuffer mabiao){
String str,s = null;
String[] rl = null;
NodeTree nt;
//得到节点名中的最后一个数字
if(!(node.getParents().getObj().equals(nodepraent.getObj()))){
nt = (NodeTree) node.getParents();
str = nt.getObj().toString();
rl = str.split("[\\D]+");
s = rl[rl.length-1];
Mabiao(nt,mabiao);
mabiao.append(s);
return mabiao;
}else{
return mabiao;
}
}
三.根据编码再次读取文件进行压缩，生成压缩文件。
哈夫曼压缩就是需要再次读取一次文件比较哈夫曼树的码表生成01bit,八位转成一个Byte进行存储，写入文件，从而达到压缩的效果。
但是为了解压缩的方便操作，我们还需把 原始文件类型 及 哈夫曼码表 写入压缩文件，方便异地解压缩。(不在一台机器上，因此内存中没有哈夫曼码表)
/**
* 4.根据码表进行编码，对文件进行压缩
*/
private void creatCompressionFile() {
byte[] b = new byte[100];
byte bt = 0;
int ind=0;
StringBuffer a = new StringBuffer();
File file2 = new File(targetFile1);
try {
//按字节读取流
is = new FileInputStream(file);
//将源文件格式和码表写入流
FileOutputStream fos=new FileOutputStream(file2);
OutputStreamWriter os=new OutputStreamWriter(fos);
BufferedWriter bw=new BufferedWriter(os);
bw.write(fileLastName+"*");
for(int in=0;in<mb.length;in++){
if(mb[in]!=null){
bw.write(in+"*"+mb[in]+"*");
}
}
bw.write("*");//以*号隔离
// 读取文件每个的ASC码。
while (is.available() > 0){
int srcasc = is.read();
a.append(mb[srcasc]);
}
for(int i=1;i<a.length();i++){
if(i%8==0){
String move = a.substring(0, 7);
String leav = a.substring(8, a.length());
a = new StringBuffer();
a.append(leav);
char[] c = move.toCharArray();
bt=0;
//将每八位01转换成byte
for (int j = 0;j < c.length;j ++)
{
if(c[j]=='1'){
double n = Math.pow(2,j);
bt+=n;
}
}
i=1;
}
b[ind++]=bt;
}
//将内容写入压缩
for(int m = 0;m<b.length;m++)
bw.write(b[m]);
System.out.println("文件总大小为： "+a.length()+" 字节");
//关闭输入输出流
is.close();
bw.flush();
bw.close();
os.close();
long end=System.currentTimeMillis();//记录程序复制完成后的时间或者“long end=new Date().getTime();”
long time = end - start;
String time_final1 = String.valueOf(time);
timeBox.setText(time_final1+"ms");
} catch (FileNotFoundException e1) {
System.out.println("指定的文件不存在！");
} catch (IOException e1) {
System.out.println("IO流异常！");
}
}
四.解压缩
把哈夫曼码表转成bit写入文件又耽误了我几天，本来，解压缩就是一读取文件比较的简单过程，也就不阐述了。
哈夫曼压缩压缩效率不是太高，在我测试中，压缩后的文件常常都是比原始文件要大，根本没有达到目的，我思考了一下，若1M的TXT文件全是一个字符应该比出现任意字符的1M的TXT文件压缩率要高，但是和LZW压缩相比，我还真不知道，还得去测试去了解，若等不及了你就自己去测试再告诉我答案吧。
相关推荐
要实现哈夫曼压缩和解压缩，我们可以创建一个MFC应用程序，利用MFC的文件I/O功能读取和写入文件。在程序中，我们需要定义数据结构来表示哈夫曼树节点，实现哈夫曼树的构建和编码生成，以及编码的压缩和解压缩操作。 ...
《哈夫曼压缩》是一种广泛应用于数据压缩领域的高效算法，由大卫·艾尔·哈夫曼在1952年提出。它属于一种基于字符频率的无损压缩方法，特别适用于压缩那些存在大量重复字符的数据。哈夫曼编码是哈夫曼压缩的核心，...
vc++哈夫曼压缩算法 vc++哈夫曼压缩算法
mypage文件可能包含了实现哈夫曼压缩和解压缩算法的C源代码文件，以及相关的测试数据或结果。通过阅读和理解这些代码，你可以深入学习哈夫曼编码的工作原理，以及如何在C语言中实现这一算法。同时，还可以了解到如何...
哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩...
### 哈夫曼压缩详解 #### 一、哈夫曼压缩概述 哈夫曼压缩是一种广泛应用于数据压缩领域的无损压缩技术。无损压缩意味着压缩后的数据在解压后可以完全恢复到原始状态，不丢失任何信息。哈夫曼编码通过构建一个特殊...
在Java中实现哈夫曼压缩和解压涉及到以下几个关键知识点： 1. **哈夫曼树**： 哈夫曼树（Huffman Tree）是一种带权路径长度最短的二叉树，也称为最优二叉树。它通过将频率较低的字符编码为较短的位序列，而频率较...
哈夫曼压缩是一种高效的数据压缩方法，它基于字符出现频率构建一种特殊的二叉树——哈夫曼树。在计算机科学中，尤其是信息处理和文件压缩领域，哈夫曼编码是广泛应用的技术之一。ASC II码是计算机中用8位二进制数...
哈弗曼编码（Huffman Coding）是一种数据压缩算法，由美国计算机科学家大卫·艾尔文·哈弗曼在1952年提出。这个算法基于一种称为“最优二叉树”（也称哈弗曼树）的数据结构，主要用于对频率不同的字符进行编码，从而...
哈夫曼编码是一种高效的数据压缩方法，由大卫·哈夫曼在1952年提出。它是基于一种称为哈夫曼树（也叫最优二叉树）的数据结构。在这个课程设计中，你将深入理解哈夫曼编码的原理，并通过C++编程语言实现文件的压缩与...
在Java中实现哈夫曼压缩涉及到的主要步骤包括统计字节频率、构建哈夫曼树以及生成哈夫曼编码。首先，我们需要创建一个字节类（`NodeData`）来表示每个字节及其对应的权重（频率）。下面我们将详细讲解这些步骤： 1....
哈夫曼实现文件的压缩与解压缩，代码关键部分有注释。
通常通过哈夫曼构建算法实现，该算法将频率最低的两个节点合并为一个新的节点，新节点的频率是其子节点频率之和，重复此过程直到只剩下一个节点，即为哈夫曼树的根节点。 3. **生成哈夫曼编码**：从哈夫曼树中生成...
哈夫曼压缩算法，全称为哈夫曼编码（Huffman Coding），是一种高效的无损数据压缩方法，由美国科学家大卫·艾尔·哈夫曼在1952年提出。它是基于字符频率（权重）构建最优二叉树的思想，通过创建一棵特殊的二叉树——...
在Java编程环境中实现哈夫曼压缩与解压缩程序，我们可以利用面向对象的特性，设计多个类来完成不同部分的功能。 1. **FileChooserDemo.java**：这是一个用户界面类，通常包含用于让用户选择输入和输出文件的控件。...
哈夫曼编码是数据压缩中的经典方法之一，由克利福德·哈夫曼在1952年提出，因此得名。 哈夫曼编码是一种前缀码（也称为无歧义码），它根据符号出现的频率为其分配长度不等的二进制代码。频繁出现的字符将被赋予较短...
哈夫曼编码是一种高效的数据编码方法，主要用于无损数据压缩，尤其在文本文件的压缩中表现出色。这种编码方式基于频率最小的字符用最短的二进制代码表示的原理，能够有效地减少数据存储和传输时的位数，从而达到压缩...
在"哈夫曼压缩.zip"这个压缩包中，我们可以预见到包含了一个与哈夫曼压缩相关的项目。这个项目可能是用Visual Studio（VS）开发环境编写的，这意味着它可能是一个C++、C#或Visual Basic等编程语言的实现。实习性质...
每次选出权值最小且没有双亲的两个节点建立新的哈弗曼树。 无栈非递归遍历Huffman树，求Huffman编码。...要注意的是当文件较小时，不宜使用哈夫曼来进行压缩，此时文件头占比过大，会使压缩结果很差。
在Java中实现哈夫曼压缩通常包括以下几个关键步骤： 1. **构建哈夫曼树**：首先，需要统计输入文本中每个字符出现的频率。然后，根据这些频率创建一个哈夫曼树。哈夫曼树是一种特殊的二叉树，其特点是叶子节点代表...