1.按照字符分析要压缩的文件得出结果（有哪些字符，每个字符出现的次数）。2.根据字符出现的次数构建哈夫曼树（得出字符的哈夫曼编码）。3.根据字符的哈夫曼编码进行转换、压缩，然后创建压缩文件。4.读取压缩文件，读出哈夫曼编码和字符的对照表。解压缩。数据结构的设计：1.保存字符次数和字符的数据结构struct _symbol{char character;//字符unsigned int number;//字符出现的次数char huffecode[20];//编码}2.用一个结构体保存所有字符的信息struct _filestate{char symbol_count;//字符种类struct _symbol symbol_array[128];//字符信息};3.哈夫曼树节点struct node{struct _symbol symbol;struct node *left;struct node *right;};4.哈夫曼编码struct code{char character;char codebit[100];}; 源代码实现：
#include "header.h"
#include <string.h>
//单个字符的结构体
struct
_symbol{
char character;//字符
unsigned int number;//字符的次数
char huffcode[20]; //编码
};
//总结构体
struct _filestate{
char symbol_count;//多少种字符
struct _symbol symbol_array[128]; //结构体数组保存各种字符
};
//文件字符总结构体
struct _filestate filestate;
//树节点
struct _node{
struct _node *parent;
struct _symbol symbol;
struct _node *left;
struct _node *right;
int idx; //在filestate中的索引
};
typedef struct _node node;
//创建节点
node *creatnode(struct _symbol symbol,int idx)
{
node *temp=malloc(sizeof(node));
temp->symbol=symbol;
temp->left=NULL;
temp->right=NULL;
temp->idx=idx;
temp->parent=NULL;
return temp;
}
//构建一棵哈弗曼树
node *createhaffman(struct _filestate *pfilestate)
{
//创建一维数组，里面保存指针
node **array=malloc(pfilestate->symbol_count*sizeof(node *));
node *temp=NULL;
int i;
for(i=0;i<pfilestate->symbol_count;i++)
{
array[i]=creatnode(pfilestate->symbol_array[i],i);
}
int j;
int minidx,secminidx;
for(i=0;i<pfilestate->symbol_count-1;i++)
{
j=0;
//找出第一个非空节点
while(array[j]==NULL)
{
j++;
}
minidx=j;
//拿第一个非空节点和后面的对比
for(j=0;j<pfilestate->symbol_count;j++)
{
if(array[j]&&array[j]->symbol.number<array[minidx]->symbol.number)
{
minidx=j;
}
}
j=0;
while(array[j]==NULL
j==minidx)
{
j++;
}
secminidx=j;
for(j=0;j<pfilestate->symbol_count;j++)
{
if(array[j]&&j!=minidx&&array[j]->symbol.number<array[secminidx]->symbol.number)
{
secminidx=j;
}
}
struct _symbol symbol={0,array[minidx]->symbol.number+array[secminidx]->symbol.number};
temp=creatnode(symbol,-1);
temp->left=array[minidx];
temp->right=array[secminidx];
temp->parent=NULL;
array[minidx]->parent=temp;
array[secminidx]->parent=temp;
array[minidx]=temp;
array[secminidx]=NULL;
}
free(array);
array=NULL;
return temp;
}
//判断是否叶子节点
int isleaf(node *cur)
{
if(cur->left==NULL&&cur->right==NULL)
return 1;
else
{
return 0;
}
}
//取得哈夫曼编码
void huffmancode(node *leaf,char code[20])
{
char a[20]={0};
node *temp=leaf;
int i=0;
while(temp->parent)
{
if(temp->parent->left==temp)
{
a[i]=2;
}
else
{
a[i]=1;
}
temp=temp->parent;
i++;
}
int length=i;
char tmp=0;
for(i=0;i<length/2;i++)
{
tmp=a[i];
a[i]=a[length-i-1];
a[length-i-1]=tmp;
}
strcpy(code,a);
}
//取得叶子的哈夫曼码并填充到文件结构体里
void fillhuffmancode(node *root,struct _filestate *pfilestate)
{
int idx;
if(root)
{
if(isleaf(root))
{
idx=root->idx;
huffmancode(root,pfilestate->symbol_array[idx].huffcode);
}
else
{
fillhuffmancode(root->left,pfilestate);
fillhuffmancode(root->right,pfilestate);
}
}
}
//根据频率创建树且获取编码
void createandcoding(struct _filestate *pfilestate)
{
node *root=createhaffman(pfilestate);
fillhuffmancode(root,pfilestate);
//haffmancode(root,0,&dictionary);
int i,j;
for(i=0;i<pfilestate->symbol_count;i++)
{
printf("%c ",pfilestate->symbol_array[i].character);
for(j=0;j<20;j++)
printf("%d",pfilestate->symbol_array[i].huffcode[j]);
puts("\n");
}
}
//创建结构体
void calccount(struct _filestate *pfilestate,char ch)
{
int i;
int flagexist=0;
for(i=0;i<pfilestate->symbol_count;i++)
{
if(ch==pfilestate->symbol_array[i].character)
{
pfilestate->symbol_array[i].number++;
flagexist=1;
break;
}
}
if(!flagexist)
{
pfilestate->symbol_array[pfilestate->symbol_count].character=ch;
pfilestate->symbol_count++;
}
}
//查字典，获得编码
void lookupdict(char character,struct _filestate *pfilestate,char bitcode[])
{
int i=0;
for(i=0;i<pfilestate->symbol_count;i++)
{
if(character==pfilestate->symbol_array[i].character)
{
strcpy(bitcode,pfilestate->symbol_array[i].huffcode);
break;
}
}
}
//写文件头
void writeheader(int fd,struct _filestate *pfilestate)
{
write(fd,pfilestate,sizeof(struct _filestate));
}
//读文件头
void readheader(int fd,struct _filestate *pfilestate)
{
read(fd,pfilestate,sizeof(struct _filestate));
}
//写编码
void writecode(int fd_r,int fd_w,struct _filestate *pfilestate)
{
int flgend=0;
//临时变量，用来保存取出来哈夫曼编码
char bitcode[20];
//临时变量
char temp;
char buffer;
//写字节的索引
int buf_idx=0;
//读到文件尾
int bitcode_idx=0;
//从源文件读一个字符
read(fd_r,&temp,1);
//从字典里查出字符的哈夫曼编码
lookupdict(temp,pfilestate,bitcode);
//一直读字符，直到文件的末尾
while(!flgend)
{
//用来写的字符，需要根据哈夫曼编码构建
buffer=0;
//现在指向buffer的第0位
buf_idx=0;
while(buf_idx<8)
{
if(bitcode[bitcode_idx]==2)
{
//把对应的位清零
buffer&=~(1<<buf_idx);
bitcode_idx++;
buf_idx++;
}
else if(bitcode[bitcode_idx]==1)
{
//给对应的位置1
buffer|=(1<<buf_idx);
bitcode_idx++;
buf_idx++;
}
else//如果编码数组里的编码读完了
{
//再取一个字符
if((read(fd_r,&temp,1))==1)
{
//根据字符取得哈夫曼码
lookupdict(temp,pfilestate,bitcode);
bitcode_idx=0;
}
else
{
flgend=1;
break;
}
}
}
write(fd_w,&buffer,1);
}
}
//写到文件中
void writetofile(char *filename,struct _filestate *pfilestate)
{
int fd1=open(filename,O_RDONLY);
if(fd1<0)
{
perror("open");
exit(EXIT_FAILURE);
}
char *newfilename=strcat(filename,".aar");
int fd2=open(newfilename,O_CREAT|O_TRUNC|O_WRONLY,0666);
if(fd2<0)
{
perror("open");
exit(EXIT_FAILURE);
}
//将字典结构体先写到文件里面，方便解压时读取
writeheader(fd2,pfilestate);
//写编码
writecode(fd1,fd2,pfilestate);
close(fd1);
close(fd2);
}
//分析文件，得到各字符的次数
void analyse(char *filename)
{
int fd=open(filename,O_RDONLY);
if(fd<0)
{
return;
}
char temp;
while((read(fd,&temp,1))==1)
{
calccount(&filestate,temp);
}
close(fd);
int i;
for(i=0;i<filestate.symbol_count;i++)
{
printf("char is %c ascii %d, number is %d\n",\
filestate.symbol_array[i].character,\
filestate.symbol_array[i].character,\
filestate.symbol_array[i].number);
}
}
//压缩
void compress(char *filename)
{
analyse(filename);
createandcoding(&filestate);
writetofile(filename,&filestate);
}
//写解压缩文件
void writedecompressfile(int fd, char *filename,node *root)
{
char *newfilename=strcat(filename,".un");
node *tmpnode=root;
int fd_w=open(newfilename,O_CREAT|O_WRONLY|O_TRUNC,0600);
if(fd_w<0)
{
perror("open");
return;
}
char temp;
int bit_idx;
while(read(fd,&temp,1)==1)
{
bit_idx=0;
while(bit_idx<8)
{
if(temp&(1<<bit_idx))
{
tmpnode=tmpnode->right;
}
else
{
tmpnode=tmpnode->left;
}
if(isleaf(tmpnode))
{
write(fd_w,&(tmpnode->symbol.character),1);
tmpnode=root;
}
bit_idx++;
}
}
close(fd_w);
}
//解压
void decompress(char *filename)
{
int fd=open(filename,O_RDWR);
if(fd<0)
{
perror("open");
return;
}
memset(&filestate,0,sizeof(filestate));
//读文件头
readheader(fd,&filestate);
//创建哈弗曼树
node *root=NULL;
root=createhaffman(&filestate);
writedecompressfile(fd,filename,root);
close(fd);
}
int main(int argc,char const *argv[])
{
char *filename=(char *)argv[2];
if(argc<3)
{
puts("用法：tar -y[-j] filename");
exit(EXIT_FAILURE);
}
if(strcmp(argv[1],"-y")==0)
{
compress(filename);
}
else if(strcmp(argv[1],"-j")==0)
{
decompress(filename);
}
else
{
puts("参数错误！");
exit(EXIT_FAILURE);
}
}
这样的压缩可以做到压缩50%的效果。

哈夫曼编码的主要用途：哈夫曼编码主要用于数据压缩，通常可以节省20%-90%的空间，具体的压缩率依赖于数据的特性。下面举个简单的例子说明对于字符不同编码方式所使用的空间大小。从图中可以看出：1、定长编码6个字符使用的二进制位数为 （45*3+13*3+12*3+16*3+9*3+5*3）= 300 个二进制位来编码文件。2、变长编码中6个字符使用的二进制位数为 （45*1+13*3+12*3+16*3+9*4+5*4） = 224 个二进制位来编码文件。3、变长编码与定长编码相比节约了(300-224)/300 = 25%的空间。哈夫曼编码原理概述哈夫曼编码是有贪心算法来构造的最优前缀码。哈夫曼编码是通过二叉树的形式构造表示的，其中构造出的二叉树一定是一颗满二叉树。下面简述哈夫曼编码的构造过程：1、由给定的m个权值{w(1),w(2),w(3),...,w(m)}，构造m课由空二叉树扩充得到的扩充二叉树{T(1),T(2),....T(m)}。每个T(i)(1<= i <= m)只有一个外部节点（也是根节点），它的权值置为m(i)。概括一下就是把原先的节点封装成二叉树结点的形式。2、在已经构造的所有扩充二叉树中，选取根结点的权值最小和次最小的两棵，将他们作为左右子树，构造成一棵新的扩充二叉树，它的根结点（新建立的内部结点）的权值置为其左、右子树根结点权值之和。3、重复执行步骤（2），每次都使扩充二叉树的个数减少一，当只剩下一棵扩充二叉树时，它便是所要构造的哈夫曼树。下面是哈夫曼编码的具体操作步骤：从图中可以看出，每次选择两个最小的结点，生成新的二叉树之后，新二叉树的根结点重新加入到原结点序列中。哈夫曼编码代码实现过程在算法导论中，哈夫曼编码使用优先队列管理结点序列，如果优先队列使用最小堆来维护，这样哈夫曼编码算法时间复杂度为O(n*lgn)；在这里我使用链表的形式存储结点序列，采用时间复杂度为O(n^2)的方式来实现，考虑到哈夫曼编码生成的二叉树为满二叉树，而满二叉树中总的结点个数等于叶子结点加上内部结点的和，叶子结点又等于内部结点加上一。所以我们可以根据已知的结点序列数，计算出总的需要使用的链表的空间大小 = 结点数*2 + 1 。首先是定义的二叉树结点的结构，具体get,set方法我就不罗列出了public class Haff {
private int node; // 结点的值
private int parent; // 父结点的值
private int llink; // 左孩子结点的值
private int rlink; // 右孩子结点的值
private int mark; // 标记结点下标，解码时候方便
}下面是用Java写的哈夫曼编码二叉树的生成过程： public void generatorTree(List<Haff> list){
int length = (list.size()+1)/2;
for (int i = 0; i < length-1; i++) {
// x,y为最小两个数组的下标,min1,min2为Integer类型最大值,方便比较的大小
int min1 = MAXINT, min2 = MAXINT, x = ELEINDEX, y = ELEINDEX;
// 找出指定链表长度内最小的两个数
for (int j = 0; j < length + i; j++) {
if (list.get(j).getParent() == -1 && min1 > list.get(j).getNode()) {
y = x;
min2 = min1;
min1 = list.get(j).getNode();
x = j;
} else if (list.get(j).getParent() == -1 && min2 > list.get(j).getNode()) {
min2 = list.get(j).getNode();
y = j;
}
}
list.get(x).setParent(length + i);
list.get(y).setParent(length + i);
list.get(length + i).setNode(min1 + min2);
list.get(length + i).setLlink(x);
list.get(length + i).setRlink(y);
}
}
从代码中我们可以看出，每次循环需要找到已知链表长度中两个最小的结点，然后生成新的结点加入到链表中。
下面是根据已经生成的哈夫曼树生成哈夫曼编码的过程（采用递归的方式实现）：
利用递归的方法,生成HaffMan编码
public void generatorCode(List<Haff> list,int index,StringBuilder strb,Map<Integer,String> map){
if(list.get(index).getRlink() == -1
list.get(index).getLlink() == -1){
map.put(list.get(index).getMark(), strb.toString());
return;
}
strb.append("0");
generatorCode(list,list.get(index).getLlink(),strb,map);
strb.deleteCharAt(strb.length()-1);
strb.append("1");
generatorCode(list,list.get(index).getRlink(),strb,map);
strb.deleteCharAt(strb.length()-1);
}也可以使用栈从而采用非递归的方式实现。
模拟哈夫曼编码实现文件压缩过程首先读取文件中的字符（这里主要是ASCII码中所表示的字符，Unicode中的字符集没有考虑到），统计数据中单个字符的出现次数，并生成哈夫曼树，遍历哈弗曼树生成哈夫曼编码，将哈夫曼编码存放在map中，再次扫描文件，转换原字符为对应的哈夫曼编码，并且模拟哈夫曼编码的还原过程，读取哈夫曼编码文件，还原为原来的文件。下面是代码，关键部分都做了注释：package algo;
public class Haff {
private int node;
private int parent;
private int llink;
private int rlink;
private int mark;
public Haff(){
this.node = 0;
this.parent = -1;
this.llink = -1;
this.rlink = -1;
this.mark = -1;
}
public int getMark() {
return mark;
}
public void setMark(int mark) {
this.mark = mark;
}
public int getNode() {
return node;
}
public void setNode(int node) {
this.node = node;
}
public int getParent() {
return parent;
}
public void setParent(int parent) {
this.parent = parent;
}
public int getLlink() {
return llink;
}
public void setLlink(int llink) {
this.llink = llink;
}
public int getRlink() {
return rlink;
}
public void setRlink(int rlink) {
this.rlink = rlink;
}
}
package algo;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class HaffTree {
private final static int[] array = new int[256];
private final static int MAXINT = Integer.MAX_VALUE;
private final static int ELEINDEX = -1;
static {
Arrays.fill(array, 0);
}
// 初始化列表
public List<Haff> initTree(File file){
int length = 0;
int size = array.length;
List<Haff> list = new ArrayList<Haff>(size);
// 打开文件读取流,统计文件中的各个字母出现的次数
try(FileInputStream in = new FileInputStream(file)){
int c;
while((c = in.read()) != -1){
array[c]++;
}
}catch(IOException ex){
System.err.println(ex);
}
// 因为HaffMan树是满二叉树， 初始化list，链表的长度为叶子节点加内部节点。内部节点等于叶子节点减一
for (int i = 0; i < size; i++) {
Haff haff = new Haff();
if (array[i] != 0) {
haff.setNode(array[i]);
haff.setMark(i);
list.add(haff);
length++;
}
}
for(int i = 0; i < length-1; i++){
list.add(new Haff());
}
return list;
}
// HaffMan树
public Map<Integer,String> generatorTree(List<Haff> list){
int length = (list.size()+1)/2;
for (int i = 0; i < length-1; i++) {
// x,y为最小两个数组的下标,min1,min2为Integer类型最大值,方便比较的大小
int min1 = MAXINT, min2 = MAXINT, x = ELEINDEX, y = ELEINDEX;
// 找出指定链表长度内最小的两个数
for (int j = 0; j < length + i; j++) {
if (list.get(j).getParent() == -1 && min1 > list.get(j).getNode()) {
y = x;
min2 = min1;
min1 = list.get(j).getNode();
x = j;
} else if (list.get(j).getParent() == -1 && min2 > list.get(j).getNode()) {
min2 = list.get(j).getNode();
y = j;
}
}
list.get(x).setParent(length + i);
list.get(y).setParent(length + i);
list.get(length + i).setNode(min1 + min2);
list.get(length + i).setLlink(x);
list.get(length + i).setRlink(y);
}
StringBuilder strb = new StringBuilder();
Map<Integer,String> map = new HashMap<Integer,String>();
// 根据HaffMan树,生成HaffMan编码
generatorCode(list,list.size()-1,strb,map);
return map;
}
// 利用递归的方法,生成HaffMan编码
public void generatorCode(List<Haff> list,int index,StringBuilder strb,Map<Integer,String> map){
if(list.get(index).getRlink() == -1
list.get(index).getLlink() == -1){
map.put(list.get(index).getMark(), strb.toString());
return;
}
strb.append("0");
generatorCode(list,list.get(index).getLlink(),strb,map);
strb.deleteCharAt(strb.length()-1);
strb.append("1");
generatorCode(list,list.get(index).getRlink(),strb,map);
strb.deleteCharAt(strb.length()-1);
}
// 根据HaffMan编码生成新的文件
public void getNewFile(File inFile,File outFile,Map<Integer,String> map){
try(FileInputStream in = new FileInputStream(inFile);
FileOutputStream out = new FileOutputStream(outFile)){
int c;
while((c = in.read()) != -1){
if(map.containsKey(c)){
out.write(map.get(c).getBytes());
}
}
}catch(IOException ex){
System.err.println(ex);
}
}
// 还原HaffMan编码
public void enGeneratorCode(File file,File inFile,List<Haff> list){
// 打开要读取和写入的文件
try(FileInputStream in = new FileInputStream(inFile);
FileOutputStream out = new FileOutputStream(file)){
int temp = 0,index = list.size()-1,node = 0;
// 从根节点根据读入的字符遍历
while((node = in.read()) != -1){
temp = getNextNode(list, index, node);
if(list.get(temp).getLlink() == -1){
out.write((char)list.get(temp).getMark());
index = list.size()-1;
}else{
index = temp;
}
}
}catch(IOException ex){
System.err.println(ex);
}
}
public int getNextNode(List<Haff> list,int index,int node){
if(node == 48){
return list.get(index).getLlink();
}else{
return list.get(index).getRlink();
}
}
}package algo;
import java.io.File;
import java.util.List;
import java.util.Map;
public class readFile {
public static void main(String[] args){
HaffTree haffTree = new HaffTree();
File inFile = new File("E:/user.txt");
File outFile = new File("E:/userCode.txt");
File file = new File("E:/default.txt");
// 获得HaffMan编码
List<Haff> list = haffTree.initTree(inFile);
Map<Integer,String> map = haffTree.generatorTree(list);
// 根据HaffMan编码输出新的文件
haffTree.getNewFile(inFile, outFile,map);
// 还原HaffMan编码
haffTree.enGeneratorCode(file, outFile, list);
}
}