这篇总结存到草稿箱也有三个月了，嘿嘿...
学到哈夫曼压缩的时候首先就得了解哈夫曼树，我想说，对于数据结构挂科的人来说，额，这是一个沉重的话题。不过我还真感谢老师把我的数据结构挂了，因为我那一学期根本没
听课，考试时什么都不会，而后来为了补考悬梁刺股的，当然没这里强悍，总之是还是下了很大的功夫，因此补考通过，哈夫曼树俺也理解了，为哈夫曼压缩做好了铺垫。哈夫曼树是一种由下往上构建的树形结构，只会在叶子结点上存储，从而每个存储的值都有特定的唯一的编码。具体就不再细细阐述了。
而哈夫曼压缩原理的官方（即百度百科）解释是：通过某种特殊的编码方式将数据信息中存在的重复度、冗余度有效地降低，从而达到数据压缩的目的。
个人理解压缩就是把原本文件一个一个的字节重新按照制定的新的规则来编码。因此哈夫曼压缩的步骤就是：一. 读取文件，创建哈夫曼树——> 二.根据哈夫曼树得到哈夫曼编码——> 三.根据编码再次读取文件进行压缩，生成压缩文件。——> 四.解压缩
一. 读取文件，创建哈夫曼树。
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压缩相比，我还真不知道，还得去测试去了解，若等不及了你就自己去测试再告诉我答案吧。
相关推荐
vc++哈夫曼压缩算法 vc++哈夫曼压缩算法
哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩...
哈夫曼算法实现图片的压缩，图片有前后对比。
哈夫曼实现文件的压缩与解压缩，代码关键部分有注释。
每次选出权值最小且没有双亲的两个节点建立新的哈弗曼树。 无栈非递归遍历Huffman树，求Huffman编码。...要注意的是当文件较小时，不宜使用哈夫曼来进行压缩，此时文件头占比过大，会使压缩结果很差。
C语言实现的huffman压缩解压缩算法
哈夫曼压缩与解压缩程序（JAVA）
这里采用哈夫曼编码方式来对每个字符重新编码，因为哈夫曼树具有最小带权路径长度的性质，能够生成用于压缩的二进制前缀码。程序使用的 “静态统计模型”，也就是说在编码前统计要编码的信息中所有字符的出现频率，...
代码为将普通数据使用哈夫曼编码的算法压缩。该压缩属于无损压缩
压缩解压缩 源码 VC MFC实现 可供学习研究
使用哈夫曼编码实现对文本文件的压缩和解压缩
通过自定义算法创建哈夫曼树和编码，对文件进行二进制操作实现压缩和解压。
（3） 依次读取原始文件的每个字节，查找其对应的哈弗曼编码，将这些位写入到压缩文件中（注意：要凑够8位二进制才写入到文件中）。 （4） 将原始文件中各字节及出现的次数也写入到压缩文件中。 2、解压 （1） 从...
该代码实现哈夫曼基本算法，并对输入的图片进行压缩，最终输出译码后的图片，代码真实可用，想理解学习哈夫曼压缩的同学可以看看。
利用哈夫曼算法进行文件的压缩和解压缩。 利用命令行对指定的文件进行压缩和解压缩。 能对一般的文本文件有较好的压缩能力，对其它格式文件可以进行压缩但不一定能有压缩效果。对于用此程序压缩的文件可以用此程序...
哈夫曼压缩和解压和解压，数据结构课程设计，c++源码。
哈夫曼解压缩程序Szip 命令行输入 可以实现压缩、解压命令 控制台程序
java实现的哈夫曼压缩算法，有swing界面。
c++ 哈夫曼压缩源代码. 多种文件格式 亲测可用
利用哈夫曼编码对数据进行无损压缩，实现Huffman压缩的编码器和译码器。 1．首先读入待压缩源文件。 2．然后建立并分析字母表，对每种字符的出现频度进行统计，以频度作为建立Huffman树的权值。 3. 频度表建好后，就...