精华内容
下载资源
问答
  • 数据结构文件压缩

    2012-11-27 12:57:06
    数据结构课程设计霍夫曼文件压缩解压。 文档加源代码 还有关键路径的小福利代码 欢迎下载
  • 利用哈夫曼编码对数据进行无损压缩,实现Huffman压缩的编码器和译码器。 1.首先读入待压缩源文件。 2.然后建立并分析字母表,对每种字符的出现频度进行统计,以频度作为建立Huffman树的权值。 3. 频度表建好后,就...
  • 主要介绍了C++数据结构之文件压缩(哈夫曼树)实例详解的相关资料,利用哈夫曼编码的方式对文件进行压缩,并且对压缩文件可以解压,需要的朋友可以参考下
  • 高校数据结构的课件。比较概括的叙述了有关链表,树,堆栈的基本概念,对初学者很有帮助。
  • 文件压缩与解压代码 #include<stdio.h> #include<stdlib.h> #include<string.h> #define maxsize 100 /* 编码函数中,被编译的字符串的最大长度 */ #define max 100 /* 最大字符的个数 */ ...

    文件压缩与解压代码

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define maxsize 100  /* 编码函数中,被编译的字符串的最大长度 */
    #define max 100  /* 最大字符的个数 */
    
    typedef struct  /* 定义一个HUFFNODE结点 */
    {
      char data;    /* 数据域 */
      int weight;   /* 权值域 */
      int parent;   /* 双亲域 */
      int left;     /* 左孩子域 */
      int right;    /* 右孩子域 */
    }huffnode;
    
    typedef struct  /* 定义一个HUFFCODE结点 */
    {
       char cd[max];  /* 数组cd存放哈夫曼编码 */
       int start;
    }huffcode;
    
    huffnode ht[max];
    huffcode hcd[2*max];
    
    huffnode ht2[max];
    huffcode hcd2[2*max];
    
    void input(); 
    
    void init()    /* 初始化带权结点 */
    {
      ht[0].weight=27;
      ht[1].data=' '; ht[1].weight=186;
      ht[2].data='A'; ht[2].weight=64;
      ht[3].data='B'; ht[3].weight=23;
      ht[4].data='C'; ht[4].weight=22;
      ht[5].data='D'; ht[5].weight=32;
      ht[6].data='E'; ht[6].weight=103;
      ht[7].data='F'; ht[7].weight=21;
      ht[8].data='G'; ht[8].weight=15;
      ht[9].data='H'; ht[9].weight=47;
      ht[10].data='I'; ht[10].weight=57;
      ht[11].data='J'; ht[11].weight=1;
      ht[12].data='K'; ht[12].weight=5;
      ht[13].data='L'; ht[13].weight=32;
      ht[14].data='M'; ht[14].weight=20;
      ht[15].data='N'; ht[15].weight=20;
      ht[16].data='O'; ht[16].weight=56;
      ht[17].data='P'; ht[17].weight=19;
      ht[18].data='Q'; ht[18].weight=2;
      ht[19].data='R'; ht[19].weight=50;
      ht[20].data='S'; ht[20].weight=51;
      ht[21].data='T'; ht[21].weight=55;
      ht[22].data='U'; ht[22].weight=30;
      ht[23].data='V'; ht[23].weight=10;
      ht[24].data='W'; ht[24].weight=11;
      ht[25].data='X'; ht[25].weight=2;
      ht[26].data='Y'; ht[26].weight=21;
      ht[27].data='Z'; ht[27].weight=2;
    
    }
    
    void hfmtree(huffnode ht[])  /* 创建一棵哈夫曼树 */
    {
      int i,k,x1,x2,n,m1,m2;  /* m1为最小权值,x1为其在ht中的下标;m2为第二小权值,x2为其下标 */
      n=ht[0].weight;
      for(i=1;i<=2*n-1;i++)
         ht[i].parent=ht[i].left=ht[i].right=0;  /* 对ht的parent,left,right域进行初始化 */
      for(i=n+1;i<=2*n-1;i++){
        
    	 m1=m2=10000;  /* m1,m2初值无限大 */
         x1=x2=0;      /* x1, x2初值为0 */
         for(k=1;k<=i-1;k++)  /* k为可以进行比较的结点的下标 */
           if(ht[k].parent==0)     /* 当前结点的父结点不存在时 */
    	 if(ht[k].weight<m1)   /* 当前结点的权值比最小权值还小时 */
    	 {
    	   m2=m1;
    	   x2=x1;
    	   m1=ht[k].weight;
    	   x1=k;
    	 }
           else if(ht[k].weight<m2)    /* 当前结点的权值比最小权值大但比第二最小权值小时 */
    	    {
    	      m2=ht[k].weight;
    	      x2=k;
    	    }
         ht[x1].parent=i;
         ht[x2].parent=i;
         ht[i].weight=ht[x1].weight+ht[x2].weight;
         ht[i].left=x1;
         ht[i].right=x2;
      }
    }
    
    void output(huffnode ht[],huffcode hcd[])  /* 输出哈夫曼编码 */
    {
      huffcode d;
      int i,n,c,f,k,x;
      n=ht[0].weight;
      for(i=1;i<=n;i++)
      {
        d.start=n+1; /* d.start为栈顶 */
        c=i;   /* c存放当前结点 */
        f=ht[i].parent;   /* f存放当前结点的父结点 */
        while(f!=0)
        {
          if(ht[f].left==c)  /* 若当前结点在其父结点的左边时 */
    	     d.cd[--d.start]='0';
          else
    	     d.cd[--d.start]='1'; /* 当前结点在其父结点的右边时 */
             c=f;   /*  当前结点的父结点赋予c */
             f=ht[f].parent;  /* c的父结点赋予f */
        }
        hcd[i]=d;  /* 将当前结点的哈夫曼编码赋予hcd[i]数组 */
      }
      for(i=1;i<=n;i++)  /* 输出各个结点的哈夫曼编码 */
      {
        printf("%c: ",ht[i].data);
        x=hcd[i].start;
        for(k=x;k<=n;k++)  /* 通过栈输出哈夫曼编码 */
          printf("%c",hcd[i].cd[k]);
        printf("\n");
      }
      
     
    }
    void coding1(huffcode hcd[],huffnode ht[]) /* 编码函数,给定一个字符串,输出其对应的哈夫曼编码 */
    {	
      int i,j,n,m,k,x;
      char in[maxsize],out[2*maxsize]; /* in存放需编译的字符串,out存放编译后的代码 */
      m=0; /* m为out数组的下标 */
      printf("请输入字符串:\n");
      getchar();
      gets(in);
      
      n=strlen(in);
      for(i=0;i<n;i++)
      {
        for(j=1;j<=ht[0].weight;j++)  /* ht[0].weight存放的是带权结点的个数 */
          if(in[i]==ht[j].data)  /* 若输入字符和一个带权结点相同 */
    	{
              x=hcd[j].start;
    	  for(k=x;k<=ht[0].weight;k++){
    	   out[m]=hcd[j].cd[k];
    	   //printf("%c",out[m]);
    	   m++;
    	   
         }   
    	}
      }
      printf("哈夫曼编码为:\n");
      for(i=0;i<m;i++)
       printf("%c",out[i]);
       printf("\n");
       getchar();
    }
    
    void coding2(huffcode hcd[],huffnode ht[]) /* 编码函数,给定一个字符串,输出其对应的哈夫曼编码 */
    {	
      int i,j,n,m,k,x;
      char in[maxsize],out[2*maxsize]; /* in存放需编译的字符串,out存放编译后的代码 */
      m=0; /* m为out数组的下标 */
      printf("请输入字符串:\n");
      //getchar();
      gets(in);
      
      n=strlen(in);
      for(i=0;i<n;i++)
      {
        for(j=1;j<=ht[0].weight;j++)  /* ht[0].weight存放的是带权结点的个数 */
          if(in[i]==ht[j].data)  /* 若输入字符和一个带权结点相同 */
    	{
              x=hcd[j].start;
    	  for(k=x;k<=ht[0].weight;k++){
    	   out[m]=hcd[j].cd[k];
    	   //printf("%c",out[m]);
    	   m++;
    	   
         }   
    	}
      }
      printf("哈夫曼编码为:\n");
      for(i=0;i<m;i++)
       printf("%c",out[i]);
       printf("\n");
       getchar();
    }
    
    void decoding(huffcode hcd[],huffnode ht[]) /* 译码函数,输入一个代码流,输出其对应的字符 */
    {
      int i,j,n,k,x,m,w;
      char in[maxsize*2],out[maxsize];  /* in数组存放代码流,out数组存放对应字母 */
      printf("输入一段哈夫曼编码:\n");
      scanf("%s",in);
      n=strlen(in);
      i=0; m=0;   /* i为in数组的下标,m为out数组的下标 */
      while(i<n)
      {
        for(j=1;j<=ht[0].weight;j++)  /* ht[0].weight为带权结点的个数 */
          {
            x=hcd[j].start;
            for(k=x,w=i;k<=ht[0].weight;k++,w++)   /* k为hcd[j].cd[]的下标 */
              if(in[w]!=hcd[j].cd[k])
                 break;
    	if(k>ht[0].weight)
              {
                 out[m++]=ht[j].data;
    	     break;
              }
          }
        i=w;
      }
      printf("对应的内容为:\n");
      for(i=0;i<m;i++)       /* 输出结果 */
        printf("%c",out[i]);
      printf("\n");
      getchar();
      
    }
    
    void disp(huffnode ht[])  /* 先续遍历创建的哈夫编码 */
    {
      int top,i,j,stack[maxsize];
      top=0;
      printf("the tree is:");
      for(i=1;i<=ht[0].weight*2-1;i++)  /* 寻找父结点为0的结点 */
        if(ht[i].parent==0)
          break;
      do
      {
        if(i!=0)  /* i为根结点 */
          {
    	printf("%d ",ht[i].weight);
    	stack[top++]=i;  /* 根结点进栈 */
    	while(ht[i].left!=0)
    	  {
    	    i=ht[i].left; /* 子树的根结点赋予i */
    	    printf("%d ",ht[i].weight);
    	    stack[top++]=i;
    	  }
          }
        j=stack[--top]; 
        i=ht[j].right;
      }while(top>=0||i!=0);
      getchar();
      getchar();
    }
    
    
    void Automatic(huffnode ht2[],huffcode hcd2[]){
    	system("cls");
    	char num[max];
    	int  count[300];
    	memset(count,0,sizeof(count));
    	printf("*************************\n");
    	printf("您正在选用自动统计频率模式\n");
    	printf("请输入文档内容:\n");
    	scanf("%s",num);
    	int n=strlen(num);
    	int cnt=0;
    	//进行统计每个字符频率 
    	for(int i=0;i<n;i++)
    	  count[(int)num[i]]++;
    	for(int j=0;j<256;j++){
    		if(count[j]!=0){
    			cnt++;
    			ht2[cnt].weight=count[j];
    			ht2[cnt].data=(char)j;
    		}
    		
    	}
        ht2[0].weight=cnt;	 	
        hfmtree(ht2);
        printf("文档中各个字符的哈夫曼编码:\n");
        output(ht2,hcd2);	
    	do{
    	printf("**********************\n");
    	printf("文档中出现的字符:\n");
    	for(int i=1;i<=ht2[0].weight;i++)
    	printf("%c ",ht2[i].data);
    	printf("\n");
        printf("1. 文档内容对应的哈夫曼编码\n") ;
        printf("2. 查询文档中的内容\n");
        printf("0. 退出\n");
        printf("请输入您要进行的操作(0~2):\n");
    	int n1;
    	scanf("%d",&n1);
    	if(n1==1)
    	coding1(hcd2,ht2);
    	else if(n1==2)
    	decoding(hcd2,ht2);
    	else
    	break;
    }while(1);
    
    }
    
    
    void welcome(){                                          //首菜单 
    	system("cls");
    	printf("***************************\n");
    	printf("欢迎使用文件压缩与解压系统\n");
    	printf("\n");
    	printf("1.系统默认权值\n");
    	printf("2.手动输入指定权值\n");
    	printf("3.自动统计频率\n");
    	printf("0.退出系统\n");
    	printf("\n");
    	printf("***************************\n");
    	printf("\n");
    }
    
    int precompiled()
    {                                     //选用默认频率
    	int select;
        do
        {
        	system("cls");
            init();    //初始化带权结点 
            hfmtree(ht);  //创建哈夫曼树 
            output(ht,hcd);  //哈夫曼编码 
    	    printf("*************************\n");
    	    printf("您正在选用系统默认权值\n");
    	    printf("\n");
            printf("1. 编码\n");
            printf("2. 解码\n");
            printf("3. 先序遍历哈夫曼树\n");
            printf("0. 退出\n");
            printf("\n");
            printf("*************************\n");
            printf("请输入您要进行的操作(0~3):\n ");
            scanf("%d",&select);
            switch(select)
            {
            	case 1: coding1(hcd,ht);
            	        break;
            	case 2: decoding(hcd,ht);
            	        getchar(); 
            	        break;
            	case 3: disp(ht);
            	        break; 
            	case 0: return 0;
            	default: printf("请输入正确的选择(0~3)!");
    		}
        }while(1);
        getchar();
    	return 0;
    }
    
    int Manual(){
    	int select;
    	system("cls");
        input();    
        hfmtree(ht);  //创建哈夫曼树 
        output(ht,hcd);  //哈夫曼编码
        do
        {
         
    	    printf("******************************\n");
    	    printf("您正在选用手动输入字符及其权值\n");
    	    printf("\n");
            printf("1. 编码\n");
            printf("2. 解码\n");
            printf("3. 先序遍历哈夫曼树\n");
            printf("0. 退出\n");
            printf("\n");
            printf("*************************\n");
            printf("请输入您要进行的操作(0~3):\n ");
            scanf("%d",&select);
            getchar();
            switch(select)
            {
            	case 1: coding2(hcd,ht);
            	        break;
            	case 2: decoding(hcd,ht);
            	        getchar(); 
            	        break;
            	case 3: disp(ht);
            	        break; 
            	case 0: return 0;
            	default: printf("请输入正确的选择(0~3)!\n");
    		}
        }while(1);
        getchar();
    	return 0;
    	
    }
    
    void input()  /* 输入函数,(与huffnode *init()函数有相同的功能) */
    {
      int i,n;
      printf("请输入字符的数量:\n");
      scanf("%d",&n);         /* 输入字符数 */
      ht[0].weight=n;
      for(i=1;i<=n;i++)  {
        getchar();
        printf("请输入第 %d 个的字符和权值: ",i);
        scanf("%c%d",&ht[i].data,&ht[i].weight); /* 输入字符和权值 */
      }
    
    }
    
    int main()
    {
    	int select;
    	while(1){
    		welcome();
    		printf("请输入您要进行的操作(0~3):\n");
    		scanf("%d",&select);
    		getchar();
    		switch(select)
    		{
    			case 1 : precompiled();  //选用默认
    			         break;
    			case 2 : Manual();  //手动输入 
    			         break;
    			case 3 : Automatic(ht2,hcd2);  //自动统计
    			         break;
    			case 0 : printf("感谢您使用本系统!!!");
    			         exit(1);
    			default : printf("请输入正确的操作序号(1~3)!");
    		}
    		getchar();
    	}
    	return 0;
    
    }
    
    
    展开全文
  • package com.ws.数据结构.树.赫夫曼.赫夫曼编码.文件压缩; import java.io.*; import java.util.*; public class HuffmanCode { public static void main(String[] args) { String str="i like lik

    一、文件压缩
    具体要求:给你一个图片文件,要求对其进行无损压缩, 看看压缩效果如何。
    思路:读取文件-> 得到赫夫曼编码表 -> 完成压缩

    package com.ws.数据结构..赫夫曼.赫夫曼编码.文件压缩;
    
    import java.io.*;
    import java.util.*;
    
    public class HuffmanCode {
        public static void main(String[] args) {
            String str="i like like like java do you like a java";
            System.out.println(str);
            byte[] contenBytes=str.getBytes();//②得到字符串i like like like java do you like a java对应的byte[]数组
            System.out.println("压缩前个数="+contenBytes.length);//40
            byte[] huffmanBytes=huffmanZip(contenBytes);
            System.out.println("压缩后"+Arrays.toString(huffmanBytes));
            System.out.println("压缩后个数="+huffmanBytes.length);
            /*
            List<Node> nodes=getNodes(contenBytes);
            System.out.println("List集合nodes="+nodes);
            //测试创建的哈夫曼树
            System.out.println("赫夫曼树");
            Node root=goujianHuffmanTree(nodes);
            qianprintf(root);
            //测试哈夫曼编码
            Map<Byte,String> hafumanbianma=getbianma(root);
            System.out.println("生成的哈夫曼编码表"+hafumanbianma);
            //测试赫夫曼编码字节数组
            byte[] huffmanBytes=zip(contenBytes,hafumanbianma);
            System.out.println("哈夫曼编码过后的数组:"+Arrays.toString(huffmanBytes));
            System.out.println("压缩后个数:"+huffmanBytes.length);
            System.out.println("减少个数:"+(contenBytes.length-huffmanBytes.length));
    
             */
    
            //解压
            System.out.println("解压");
            byte[] zipjei=codezipjie(huffmanbianma,huffmanBytes);
            System.out.println(new String(zipjei));
            System.out.println("文件压缩");
            String inFile="C://Users//asus//Desktop//新建文件夹//1.jpg";
            String outFile="C://Users//asus//Desktop//新建文件夹//out.zip";
            zipFile(inFile,outFile);
            System.out.println("压缩文件ok");
        }
    
        /**
         * ③将构建赫夫曼树的节点Node放到List
         * @param bytes
         * @return  加入节点后的List
         */
        private static List<Node> getNodes(byte[] bytes){
            //1.创建一个ArrayList
            ArrayList<Node> nides=new ArrayList<>();
    
            //2.遍历bytes 统计每一个byte出现的次数  map[key(数据),value次数()]
            Map<Byte,Integer> shucishu=new HashMap<>();
            for (byte b:bytes){
                Integer count=shucishu.get(b);//拿出存储的集合的数据
                if (count==null){//Map还没有这个数据,第一次
                    shucishu.put(b,1);//放进去
                }else {
                    shucishu.put(b,count+1);//次数加一
                }
            }
    
            //把每个键值对转换成Node对象,加入到Nodes集合
            for (Map.Entry<Byte,Integer> entry:shucishu.entrySet()){
                nides.add(new Node(entry.getKey(),entry.getValue()));
            }
            return nides;
        }
    
        /**
         * ④通过List构建哈杜曼树
         * @param nodes
         * @return
         */
        private static Node goujianHuffmanTree(List<Node> nodes){
            while (nodes.size()>1){
                //排序,从小到大
                Collections.sort(nodes);
                //取出第一颗二叉树
                Node zuo=nodes.get(0);
                //取出第二课二叉树
                Node you=nodes.get(1);
                //创建一颗新的二叉树,只有权值(出现的次数),没有具体的数
                Node gen=new Node(null,zuo.weight+you.weight);
                gen.zuo=zuo;
                gen.you=you;
    
                //将处理过的数删除
                nodes.remove(zuo);
                nodes.remove(you);
                //将新的数加入
                nodes.add(gen);
            }
            return nodes.get(0);
        }
    
    //    生成赫夫曼树对应的赫夫曼编码
    //    思路:
    //   ①将赫夫曼编码放到Map中  32->01 ...
        static Map<Byte,String> huffmanbianma=new HashMap<>();
    //   ②生成赫夫曼编码表时需要保存路径StringgBuilder 存储叶子节点路径
        static StringBuilder lujing=new StringBuilder();
    
        //调用方便,重载
        private static Map<Byte,String> getbianma(Node root){
            if (root==null){
                return null;
            }
            //处理左子树
            getbianma(root.zuo,"0",lujing);
            //处理右子树
            getbianma(root.you,"1",lujing);
            return huffmanbianma;
        }
        /**
         * 将传入的node节点的额所有叶子节点的赫夫曼编码得到,放入到huffmanbianma
         * @param node  传入节点
         * @param lujing   路径:左子节点0  右子节点1
         * @param pinjei   用于拼接
         */
        private static void getbianma(Node node,String lujing,StringBuilder pinjei){
            StringBuilder stringBuilder2=new StringBuilder(pinjei);
            //将传入的lujing加入到stringBuilder2
            stringBuilder2.append(lujing);
            if (node!=null){
                //判断当前节点是叶子节点还是非叶子节点
                if (node.data==null){
                    //非叶子节点
                    //递归处理
                    //向左
                    getbianma(node.zuo,"0",stringBuilder2);
                    //向右
                    getbianma(node.you,"1",stringBuilder2);
                }else {
                    //叶子节点
                    //找到了路径
                    huffmanbianma.put(node.data,stringBuilder2.toString());
                }
            }
        }
    
        //字符串对应的byte[]数组,通过生成的赫夫曼编码表,返回一个赫夫曼编码,压缩后的byte[]
    
        /**
         * @param bytes  原始的字符串对应的byte[]
         * @param huffmanbianma  生成的哈夫曼编码
         * @return  赫夫曼编码处理过的字节数组  01编码  8个一组  补码变反码(-1)取反变原码
         */
        private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanbianma){
            //1.使用赫夫曼编码表将原数组转成赫夫曼编码对应的字符串
            StringBuilder stringBuilder=new StringBuilder();
            //遍历byte
            for (byte b:bytes){
                stringBuilder.append(huffmanbianma.get(b));//提取字节数组
            }
            //将数组转换成byte[]
            //统计返回的byte[] 长度
            int len;
            if (stringBuilder.length()%8==0){
                len=stringBuilder.length()/8;
            }else {
                len=stringBuilder.length()/8+1;
            }
            //创建压缩存储的byte数组
            byte[] by=new byte[len];
            int index=0;//记录第几个byte
            for (int i=0;i<stringBuilder.length();i+=8){
                //每8位对应一个byte  所以步长+8
                String strByte;
                if (i+8>stringBuilder.length()){
                    //不够8位
                    strByte=stringBuilder.substring(i);
                }else {
                    strByte=stringBuilder.substring(i,i+8);
                }
                //将strByte转换成byte 放到压缩存储的byte数组
                by[index]=(byte)Integer.parseInt(strByte,2);
                index++;
            }
            return by;
        }
    
        //前序遍历方法
        private static void qianprintf(Node root){
            if (root!=null){
                root.qianprintf();
            }else {
                System.out.println("赫夫曼树为空");
            }
        }
    
        //封装
    
        /**
         * @param bytes  原始字符串对应的字节数组
         * @return  经过赫夫曼编码处理过的数组  压缩后
         */
        private static byte[] huffmanZip(byte[] bytes){
            List<Node> nodes=getNodes(bytes);
            //创建哈夫曼树
            Node root=goujianHuffmanTree(nodes);
            //哈夫曼编码
            Map<Byte,String> hafumanbianma=getbianma(root);
            //赫夫曼编码字节数组
            byte[] huffmanBytes=zip(bytes,hafumanbianma);
            //返回压缩后的字节数组
            return huffmanBytes;
        }
    
        //数据解压
        /*思路:
                1.将生成的赫夫曼编码数组转换成赫夫曼编码对应的二进制字符串
                2.将赫夫曼编码对应的二进制字符串对照赫夫曼编码表转换成原字符串
         */
    
        /**
         * 1.将数组(编码后的数组)转换成二进制字符串
         * @param flag 标识是否需要补高位  最后一个字节不用补高位
         * @param b  传入的数
         * @return  b对应的二进制字符串  补码返回
         */
        private static String bytestoBitString(boolean flag,byte b){
            //使用变量保存b   转成int
            int temp=b;
            //如果是整数存在补高位
            if (flag){
                temp |=256;
            }
    
            String str=Integer.toBinaryString(temp);//返回的是int的补码
            if (flag){
                return str.substring(str.length()-8);//取后面8位
            }else {
                return str;
            }
    
        }
    
        /**
         * 2.将赫夫曼编码对应的二进制字符串对照赫夫曼编码表转换成原字符串
         * @param huffmanbianma  哈夫曼编码表
         * @param huffmanbytes  编码处理过的字节数组数组
         * @return  原来的字符串对应的数组
         */
        private static byte[] codezipjie(Map<Byte,String> huffmanbianma,byte[] huffmanbytes){
            //得到哈夫曼二进制字符串
            StringBuilder stringBuilder=new StringBuilder();
            //将byte数组转成二进制的字符串
            for (int i=0;i<huffmanbytes.length;i++){
                byte b=huffmanbytes[i];//取出
                //判断是不是最后一个字节
                boolean flag=(i==huffmanbytes.length-1);
                stringBuilder.append(bytestoBitString(!flag,b));
            }
            //System.out.println("赫夫曼解码后字节数组转对应的二进制字符串"+stringBuilder.toString());
            //把字符串按照指定的赫夫曼编码进行解码
            //赫夫曼编码表反转  反向查询 键值反转
            Map<String,Byte> map=new HashMap<>();
            for (Map.Entry<Byte,String> entry:huffmanbianma.entrySet()){
                map.put(entry.getValue(),entry.getKey());
            }
            //System.out.println(map);
            //创建集合存放byte
            List<Byte> list=new ArrayList<>();
            for (int i=0;i<stringBuilder.length();){//i是索引 扫描二进制对应的字符串
                int count=1;//后移一个字符的编码计数器
                boolean flage=true;
                Byte b=null;
    
                while (flage){
                    //取出一个 1  0
                    String key=stringBuilder.substring(i,i+count);//后移  匹配一个字符的编码
                    b=map.get(key);
                    if (b==null){
                        //没有匹配到
                        count++;
                    }else {
                        //匹配到
                        flage=false;
                    }
                }
                list.add(b);
                i+=count;//i移动到count位置
            }
            //循环结束后list及存放了所有的字符
            //将list放入到byte数组
            byte b[]=new byte[list.size()];
            for (int i=0;i<b.length;i++){
                b[i]=list.get(i);
            }
            return b;
        }
    
    
        /**
         * 文件压缩
         * @param inFile  输入路径
         * @param outFile  输出路径
         */
        public static void zipFile(String inFile,String outFile){
            //创建文件输出流
            FileOutputStream out=null;
            ObjectOutputStream os=null;
            //创建文件输入流
            FileInputStream in=null;
            try {
                in=new FileInputStream(inFile);
                //创建一个和源文件大小一样的byte数组 读取数据
                byte[] b=new byte[in.available()];
                //读取文件
                in.read(b);
                //获取文件对应的赫夫曼编码
                byte[] huffmanBytes=huffmanZip(b);
                //创建一个文件的输出流,存放压缩文件
                out=new FileOutputStream(outFile);
                //创建一个和文件输出流关联的对象输出流接收
                os=new ObjectOutputStream(out);
                //把哈夫曼编码后的字节数组以对象的方式输出,有助于恢复(解压)
                os.writeObject(huffmanBytes);
                //把哈夫曼编码表写入压缩文件
                os.writeObject(huffmanbianma);
    
            } catch (Exception e) {
                System.out.println(e.getMessage());
            }finally {
                try {
                    in.close();
                    os.close();
                    out.close();
                } catch (IOException e) {
                    System.out.println(e.getMessage());
                }
            }
        }
    
    }
    
    //①创建Node,带数据和权值
    class Node implements Comparable<Node>{
        Byte data;//存放数据本身,  ‘a’=>97
        int weight;//权值,表示字符出现的次数
        Node zuo;
        Node you;
    
        public Node(Byte data, int weight) {
            this.data = data;
            this.weight = weight;
        }
    
    
    
        @Override
        public int compareTo(Node o) {
            return this.weight-o.weight;//从小到大排序
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", weight=" + weight +
                    '}';
        }
    
        /**
         * 前序遍历
         */
        public void qianprintf(){
            System.out.println(this);
            if (this.zuo!=null){
                this.zuo.qianprintf();
            }
            if (this.you!=null){
                this.you.qianprintf();
            }
        }
    }
    i like like like java do you like a java
    压缩前个数=40
    压缩后[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
    压缩后个数=17
    解压
    i like like like java do you like a java
    文件压缩
    压缩文件ok
    

    二、文件解压

    package com.ws.数据结构..赫夫曼.赫夫曼编码.文件解压;
    
    import java.io.*;
    import java.util.*;
    
    public class HuffmanCode {
        public static void main(String[] args) {
            String str="i like like like java do you like a java";
            System.out.println(str);
            byte[] contenBytes=str.getBytes();//②得到字符串i like like like java do you like a java对应的byte[]数组
            System.out.println("压缩前个数="+contenBytes.length);//40
            byte[] huffmanBytes=huffmanZip(contenBytes);
            System.out.println("压缩后"+Arrays.toString(huffmanBytes));
            System.out.println("压缩后个数="+huffmanBytes.length);
            /*
            List<Node> nodes=getNodes(contenBytes);
            System.out.println("List集合nodes="+nodes);
            //测试创建的哈夫曼树
            System.out.println("赫夫曼树");
            Node root=goujianHuffmanTree(nodes);
            qianprintf(root);
            //测试哈夫曼编码
            Map<Byte,String> hafumanbianma=getbianma(root);
            System.out.println("生成的哈夫曼编码表"+hafumanbianma);
            //测试赫夫曼编码字节数组
            byte[] huffmanBytes=zip(contenBytes,hafumanbianma);
            System.out.println("哈夫曼编码过后的数组:"+Arrays.toString(huffmanBytes));
            System.out.println("压缩后个数:"+huffmanBytes.length);
            System.out.println("减少个数:"+(contenBytes.length-huffmanBytes.length));
    
             */
    
            //解压
            System.out.println("解压");
            byte[] zipjei=codezipjie(huffmanbianma,huffmanBytes);
            System.out.println(new String(zipjei));
            System.out.println("文件压缩");
            String inFile="C://Users//asus//Desktop//新建文件夹//1.jpg";
            String outFile="C://Users//asus//Desktop//新建文件夹//out.zip";
            zipFile(inFile,outFile);
            System.out.println("压缩文件ok");
            System.out.println("文件解压");
            String jiesrc="C://Users//asus//Desktop//新建文件夹//1//2.jpg";
            jieZipFile(outFile,jiesrc);
            System.out.println("解压成功");
        }
    
        /**
         * ③将构建赫夫曼树的节点Node放到List
         * @param bytes
         * @return  加入节点后的List
         */
        private static List<Node> getNodes(byte[] bytes){
            //1.创建一个ArrayList
            ArrayList<Node> nides=new ArrayList<>();
    
            //2.遍历bytes 统计每一个byte出现的次数  map[key(数据),value次数()]
            Map<Byte,Integer> shucishu=new HashMap<>();
            for (byte b:bytes){
                Integer count=shucishu.get(b);//拿出存储的集合的数据
                if (count==null){//Map还没有这个数据,第一次
                    shucishu.put(b,1);//放进去
                }else {
                    shucishu.put(b,count+1);//次数加一
                }
            }
    
            //把每个键值对转换成Node对象,加入到Nodes集合
            for (Map.Entry<Byte,Integer> entry:shucishu.entrySet()){
                nides.add(new Node(entry.getKey(),entry.getValue()));
            }
            return nides;
        }
    
        /**
         * ④通过List构建哈杜曼树
         * @param nodes
         * @return
         */
        private static Node goujianHuffmanTree(List<Node> nodes){
            while (nodes.size()>1){
                //排序,从小到大
                Collections.sort(nodes);
                //取出第一颗二叉树
                Node zuo=nodes.get(0);
                //取出第二课二叉树
                Node you=nodes.get(1);
                //创建一颗新的二叉树,只有权值(出现的次数),没有具体的数
                Node gen=new Node(null,zuo.weight+you.weight);
                gen.zuo=zuo;
                gen.you=you;
    
                //将处理过的数删除
                nodes.remove(zuo);
                nodes.remove(you);
                //将新的数加入
                nodes.add(gen);
            }
            return nodes.get(0);
        }
    
    //    生成赫夫曼树对应的赫夫曼编码
    //    思路:
    //   ①将赫夫曼编码放到Map中  32->01 ...
        static Map<Byte,String> huffmanbianma=new HashMap<>();
    //   ②生成赫夫曼编码表时需要保存路径StringgBuilder 存储叶子节点路径
        static StringBuilder lujing=new StringBuilder();
    
        //调用方便,重载
        private static Map<Byte,String> getbianma(Node root){
            if (root==null){
                return null;
            }
            //处理左子树
            getbianma(root.zuo,"0",lujing);
            //处理右子树
            getbianma(root.you,"1",lujing);
            return huffmanbianma;
        }
        /**
         * 将传入的node节点的额所有叶子节点的赫夫曼编码得到,放入到huffmanbianma
         * @param node  传入节点
         * @param lujing   路径:左子节点0  右子节点1
         * @param pinjei   用于拼接
         */
        private static void getbianma(Node node,String lujing,StringBuilder pinjei){
            StringBuilder stringBuilder2=new StringBuilder(pinjei);
            //将传入的lujing加入到stringBuilder2
            stringBuilder2.append(lujing);
            if (node!=null){
                //判断当前节点是叶子节点还是非叶子节点
                if (node.data==null){
                    //非叶子节点
                    //递归处理
                    //向左
                    getbianma(node.zuo,"0",stringBuilder2);
                    //向右
                    getbianma(node.you,"1",stringBuilder2);
                }else {
                    //叶子节点
                    //找到了路径
                    huffmanbianma.put(node.data,stringBuilder2.toString());
                }
            }
        }
    
        //字符串对应的byte[]数组,通过生成的赫夫曼编码表,返回一个赫夫曼编码,压缩后的byte[]
    
        /**
         * @param bytes  原始的字符串对应的byte[]
         * @param huffmanbianma  生成的哈夫曼编码
         * @return  赫夫曼编码处理过的字节数组  01编码  8个一组  补码变反码(-1)取反变原码
         */
        private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanbianma){
            //1.使用赫夫曼编码表将原数组转成赫夫曼编码对应的字符串
            StringBuilder stringBuilder=new StringBuilder();
            //遍历byte
            for (byte b:bytes){
                stringBuilder.append(huffmanbianma.get(b));//提取字节数组
            }
            //将数组转换成byte[]
            //统计返回的byte[] 长度
            int len;
            if (stringBuilder.length()%8==0){
                len=stringBuilder.length()/8;
            }else {
                len=stringBuilder.length()/8+1;
            }
            //创建压缩存储的byte数组
            byte[] by=new byte[len];
            int index=0;//记录第几个byte
            for (int i=0;i<stringBuilder.length();i+=8){
                //每8位对应一个byte  所以步长+8
                String strByte;
                if (i+8>stringBuilder.length()){
                    //不够8位
                    strByte=stringBuilder.substring(i);
                }else {
                    strByte=stringBuilder.substring(i,i+8);
                }
                //将strByte转换成byte 放到压缩存储的byte数组
                by[index]=(byte)Integer.parseInt(strByte,2);
                index++;
            }
            return by;
        }
    
        //前序遍历方法
        private static void qianprintf(Node root){
            if (root!=null){
                root.qianprintf();
            }else {
                System.out.println("赫夫曼树为空");
            }
        }
    
        //封装
    
        /**
         * @param bytes  原始字符串对应的字节数组
         * @return  经过赫夫曼编码处理过的数组  压缩后
         */
        private static byte[] huffmanZip(byte[] bytes){
            List<Node> nodes=getNodes(bytes);
            //创建哈夫曼树
            Node root=goujianHuffmanTree(nodes);
            //哈夫曼编码
            Map<Byte,String> hafumanbianma=getbianma(root);
            //赫夫曼编码字节数组
            byte[] huffmanBytes=zip(bytes,hafumanbianma);
            //返回压缩后的字节数组
            return huffmanBytes;
        }
    
        //数据解压
        /*思路:
                1.将生成的赫夫曼编码数组转换成赫夫曼编码对应的二进制字符串
                2.将赫夫曼编码对应的二进制字符串对照赫夫曼编码表转换成原字符串
         */
    
        /**
         * 1.将数组(编码后的数组)转换成二进制字符串
         * @param flag 标识是否需要补高位  最后一个字节不用补高位
         * @param b  传入的数
         * @return  b对应的二进制字符串  补码返回
         */
        private static String bytestoBitString(boolean flag,byte b){
            //使用变量保存b   转成int
            int temp=b;
            //如果是整数存在补高位
            if (flag){
                temp |=256;
            }
    
            String str=Integer.toBinaryString(temp);//返回的是int的补码
            if (flag){
                return str.substring(str.length()-8);//取后面8位
            }else {
                return str;
            }
    
        }
    
        /**
         * 2.将赫夫曼编码对应的二进制字符串对照赫夫曼编码表转换成原字符串
         * @param huffmanbianma  哈夫曼编码表
         * @param huffmanbytes  编码处理过的字节数组数组
         * @return  原来的字符串对应的数组
         */
        private static byte[] codezipjie(Map<Byte,String> huffmanbianma,byte[] huffmanbytes){
            //得到哈夫曼二进制字符串
            StringBuilder stringBuilder=new StringBuilder();
            //将byte数组转成二进制的字符串
            for (int i=0;i<huffmanbytes.length;i++){
                byte b=huffmanbytes[i];//取出
                //判断是不是最后一个字节
                boolean flag=(i==huffmanbytes.length-1);
                stringBuilder.append(bytestoBitString(!flag,b));
            }
            //System.out.println("赫夫曼解码后字节数组转对应的二进制字符串"+stringBuilder.toString());
            //把字符串按照指定的赫夫曼编码进行解码
            //赫夫曼编码表反转  反向查询 键值反转
            Map<String,Byte> map=new HashMap<>();
            for (Map.Entry<Byte,String> entry:huffmanbianma.entrySet()){
                map.put(entry.getValue(),entry.getKey());
            }
            //System.out.println(map);
            //创建集合存放byte
            List<Byte> list=new ArrayList<>();
            for (int i=0;i<stringBuilder.length();){//i是索引 扫描二进制对应的字符串
                int count=1;//后移一个字符的编码计数器
                boolean flage=true;
                Byte b=null;
    
                while (flage){
                    //取出一个 1  0
                    String key=stringBuilder.substring(i,i+count);//后移  匹配一个字符的编码
                    b=map.get(key);
                    if (b==null){
                        //没有匹配到
                        count++;
                    }else {
                        //匹配到
                        flage=false;
                    }
                }
                list.add(b);
                i+=count;//i移动到count位置
            }
            //循环结束后list及存放了所有的字符
            //将list放入到byte数组
            byte b[]=new byte[list.size()];
            for (int i=0;i<b.length;i++){
                b[i]=list.get(i);
            }
            return b;
        }
    
    
        /**
         * 文件压缩
         * @param inFile  输入路径
         * @param outFile  输出路径
         */
        public static void zipFile(String inFile,String outFile){
            //创建文件输出流
            FileOutputStream out=null;
            ObjectOutputStream os=null;
            //创建文件输入流
            FileInputStream in=null;
            try {
                in=new FileInputStream(inFile);
                //创建一个和源文件大小一样的byte数组 读取数据
                byte[] b=new byte[in.available()];
                //读取文件
                in.read(b);
                //获取文件对应的赫夫曼编码
                byte[] huffmanBytes=huffmanZip(b);
                //创建一个文件的输出流,存放压缩文件
                out=new FileOutputStream(outFile);
                //创建一个和文件输出流关联的对象输出流接收
                os=new ObjectOutputStream(out);
                //把哈夫曼编码后的字节数组以对象的方式输出,有助于恢复(解压)
                os.writeObject(huffmanBytes);
                //把哈夫曼编码表写入压缩文件
                os.writeObject(huffmanbianma);
    
            } catch (Exception e) {
                System.out.println(e.getMessage());
            }finally {
                try {
                    in.close();
                    os.close();
                    out.close();
                } catch (IOException e) {
                    System.out.println(e.getMessage());
                }
            }
        }
    
        /**
         * 文件解压
         * @param zipFile  压缩文件
         * @param outFile  解压到哪里
         */
        public static void jieZipFile(String zipFile,String outFile){
            //定义文件的输入流
            InputStream in=null;
            //定义对象输入流
            ObjectInputStream ois=null;
            //定义文件输出流
            OutputStream out=null;
    
            try {
                //创建文件输入流
                in =new FileInputStream(zipFile);
                //创建一个和压缩文件流关联的对象输入流
                ois=new ObjectInputStream(in);
                //读取byte数组  就是压缩后的哈夫曼字节数组
                byte[] huffmanBytes=(byte[]) ois.readObject();
                //读取保存的赫夫曼编码表
                Map<Byte,String> bianman=(Map<Byte, String>) ois.readObject();
                //解码
                byte[] jieyahouBytes=codezipjie(bianman,huffmanBytes);
                //将解码后的数组写入到目标文件
                //创建文件输入流
                out=new FileOutputStream(outFile);
                //写出数据
                out.write(jieyahouBytes);
    
            } catch (Exception e) {
                System.out.println(e.getMessage());
            }finally {
                try {
                    out.close();
                    in.close();
                    ois.close();
    
                } catch (Exception e2) {
                    System.out.println(e2.getMessage());
                }
            }
        }
    
    
    }
    
    //①创建Node,带数据和权值
    class Node implements Comparable<Node>{
        Byte data;//存放数据本身,  ‘a’=>97
        int weight;//权值,表示字符出现的次数
        Node zuo;
        Node you;
    
        public Node(Byte data, int weight) {
            this.data = data;
            this.weight = weight;
        }
    
    
    
        @Override
        public int compareTo(Node o) {
            return this.weight-o.weight;//从小到大排序
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", weight=" + weight +
                    '}';
        }
    
        /**
         * 前序遍历
         */
        public void qianprintf(){
            System.out.println(this);
            if (this.zuo!=null){
                this.zuo.qianprintf();
            }
            if (this.you!=null){
                this.you.qianprintf();
            }
        }
    }
    是可以的,但是有点bug  就是图片压缩的时候有点奇怪,还有就是存在数组越界的问题,以后有时间再改进
    
    展开全文
  • 数据结构文件压缩项目

    千次阅读 2016-10-29 23:57:31
    文件压缩的算法思路是基于哈夫曼树的,将字符串文件转换成二进制位存储 heap.h #pragma once #include #include using namespace std; // 小堆 template struct Less { bool operator() (const T& l, const ...

    项目名称:文件压缩

    开发环境:vs2010

    运用到的数据结构:

    1、heap堆

    2、huffmantree哈夫曼树

    3、Huffmancode哈夫曼编码

    4、面向对象C++编程语言

    思路:

    1、利用小堆建立哈弗曼树

    2、利用哈弗曼树产生哈夫曼编码

    3、利用哈夫曼编码对文件进行压缩,产生压缩文件**.compress文件,以及**.config配置文件方便解码

    4、利用配置文件获取到文件中每个字符出现的次数

    5、利用配置文件用小堆再次建立哈弗曼树

    6、利用配置文件建立的哈弗曼树进行解码生成解压后的文件**.uncompress

    建立大小堆博文连接在下面

    http://blog.csdn.net/shangguan_1234/article/details/52791719

    堆结构的二叉树存储是
    最大堆:每个父节点的都大于孩子节点。
    最小堆:每个父节点的都小于孩子节点。

    这里举小堆的例子

    将每个子孩子与父节点的值进行比较,如果比父节点小则父节点下移,较小的子孩子上移


    #pragma once    
    #include <vector>    
    #include<assert.h>    
    using namespace std;
    // 小堆    
    template<class T>
    struct Less
    {
    	bool operator() (const T& l, const T& r)
    	{
    		return l < r;
    	}
    };
    //大堆
    template<class T>
    struct Greater
    {
    	bool operator() (const T& l, const T& r)
    	{
    		return l > r;
    	}
    };
    
    template<class T, class Compare = Less<T>>
    class Heap
    {
    public:
    	Heap()
    	{}
    
    	Heap(const T* a, size_t size)
    	{
    		for (size_t i = 0; i < size; ++i)
    		{
    			_infosays.push_back(a[i]);
    		}
    
    		// 建堆    
    		for (int i = (_infosays.size() - 2) / 2; i >= 0; --i)
    		{
    			AdjustDown(i);
    		}
    	}
    
    	void Push(const T& x)
    	{
    		_infosays.push_back(x);
    		AdjustUp(_infosays.size() - 1);
    	}
    
    	void Pop()
    	{
    		assert(_infosays.size() > 0);
    		swap(_infosays[0], _infosays[_infosays.size() - 1]);
    		_infosays.pop_back();
    
    		AdjustDown(0);
    	}
    
    	const T& Top()
    	{
    		//assert(_infosays.size() > 0);
    		if (!Empty())
    		{
    			return _infosays[0];
    		}
    		
    	}
    
    	bool Empty()
    	{
    		return _infosays.empty();
    	}
    
    	int Size()
    	{
    		return _infosays.size();
    	}
    
    	void AdjustDown(int root)
    	{
    		size_t child = root * 2 + 1;
    
    		Compare com;
    		while (child < _infosays.size())
    		{
    			if (child + 1<_infosays.size() &&
    				com(_infosays[child + 1], _infosays[child]))
    			{
    				++child;
    			}
    
    
    			if (com(_infosays[child], _infosays[root]))
    			{
    				swap(_infosays[child], _infosays[root]);
    				root = child;
    				child = 2 * root + 1;
    			}
    			else
    			{
    				break;
    			}
    		}
    	}
    
    	void AdjustUp(int child)
    	{
    		int parent = (child - 1) / 2;
    
    
    		while (child > 0)
    		{
    			if (Compare()(_infosays[child], _infosays[parent]))
    			{
    				swap(_infosays[parent], _infosays[child]);
    				child = parent;
    				parent = (child - 1) / 2;
    			}
    			else
    			{
    				break;
    			}
    		}
    	}
    
    	void Print()
    	{
    		for (size_t i = 0; i < _infosays.size(); ++i)
    		{
    			cout << _infosays[i] << " ";
    		}
    		cout << endl;
    	}
    
    public:
    	vector<T> _infosays;
    };
    

    利用堆建立哈夫曼树

    Huffm an树,又称为最优二叉树,是加权路径长度最短的二叉树。
    【贪心算法】是指在问题求解时,总是做出当前看起来最好的选择。也就是说贪心算法做出的不是整体最优的的选择,而是某种意义上的
    局部最优解。贪心算法不是对所有的问题都能得到整体最优解。

    使用贪心算法构建Huffman树


    #pragma  once 
    #include "Heap.h"    
    #include<assert.h>    
    using namespace std;
    template<class T>
    struct HuffmanTreeNode
    {
    	HuffmanTreeNode<T>* _left;
    	HuffmanTreeNode<T>* _right;
    	HuffmanTreeNode<T>* _parent;
    	T _weight;
    	HuffmanTreeNode(const T& x)
    		:_weight(x)
    		, _left(NULL)
    		, _right(NULL)
    		, _parent(NULL)
    	{}
    };
    
    template<class T>
    class HuffmanTree
    {
    	typedef HuffmanTreeNode<T> Node;
    
    public:
    
    	HuffmanTree()
    		:_root(NULL)
    	{}
    
    	~HuffmanTree()
    	{
    		Destory(_root);
    	}
    
    	template <class T>
    	struct NodeCompare
    	{
    		bool operator()(Node *l, Node *r)
    		{
    			return l->_weight < r->_weight;
    		}
    	};
    	void CreatTree(const T* a, size_t size, const T& invalid)
    	{
    		assert(a);
    		Heap<Node*, NodeCompare<T>> minHeap;
    		for (size_t i = 0; i < size; ++i)
    		{
    			if (a[i] != invalid)
    			{
    				Node* node = new Node(a[i]);
    				minHeap.Push(node);
    			}
    		}
    
    		while (minHeap.Size() > 1)
    		{
    			Node* left = minHeap.Top();
    			minHeap.Pop();
    			Node* right = minHeap.Top();
    			minHeap.Pop();
    
    			Node* parent = new Node(left->_weight + right->_weight);
    			parent->_left = left;
    			parent->_right = right;
    			left->_parent = parent;
    			right->_parent = parent;
    
    			minHeap.Push(parent);
    		}
    
    		_root = minHeap.Top();
    	}
    
    
    	Node* GetRootNode()
    	{
    		return _root;
    	}
    
    
    	//void Destory(Node* root)
    	//{
    	//	if (root)
    	//	{
    	//		Destory(root->_left);
    	//		Destory(root->_right);
    	//		delete root;
    	//		root = NULL;
    	//	}
    	//}
    	void Destory(Node* root)
    	{
    		if (root==NULL)
    		{
    			return ;
    		}
    		if(root->_left==NULL&&root->_right==NULL)
    		{
    			delete root;
    			root=NULL;
    		}
    		else
    		{
    			Destory(root->_left);
    			Destory(root->_right);
    		}
    	}
    private:
    	HuffmanTreeNode<T>* _root;
    };

    利用哈弗曼树产生哈夫曼编码


    代码实现

    void _GenerateHuffmanCode(HuffmanTreeNode<CharInfo>* root)//创建哈夫曼编码
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    
    		_GenerateHuffmanCode(root->_left);
    		_GenerateHuffmanCode(root->_right);
    
    		if (root->_left == NULL && root->_right == NULL)
    		{
    			HuffmanTreeNode<CharInfo>* cur = root;
    			HuffmanTreeNode<CharInfo>* parent = cur->_parent;
    			string& code = _infos[cur->_weight._ch]._code;
    
    			while (parent)
    			{
    				if (parent->_left == cur)//往左走+0
    				{
    					code += '0';
    				}
    				else if (parent->_right == cur)//往右走+1
    				{
    					code += '1';
    				}
    				cur = parent;
    				parent = cur->_parent;
    			}
    			//寻找编码从叶子节点开始。
    			reverse(code.begin(), code.end());
    		}
    	}
    
    	//递归实现哈夫曼编码
    	void _GenerateHuffmanCode_R(HuffmanTreeNode<CharInfo>* root,string code)//创建哈夫曼编码
    	{
    		if(root==NULL)
    			return;
    		_GenerateHuffmanCode_R(root->_left,code+'0');
    		_GenerateHuffmanCode_R(root->_right,code+'1');
    		if(root->_left==NULL&&root->_right==NULL)
    		{
    			_infos[root->_weight._ch]._code=code;
    		}
    	}
    利用哈夫曼编码对文件进行压缩,产生压缩文件**.compress文件,以及**.config配置文件方便解码


    bool Compress(const char* filename)
    	{
    		//1.打开文件,统计文件字符出现的次数    
    		Longtype Charcount = 0;
    		assert(filename);
    		FILE* fOut = fopen(filename, "rb");//之前用“r”,结果出了一点问题
    		//"rb"为以二进制方式读取文件,这里的b就是binary。"wb"为以二进制方式写入文件  
    		assert(fOut);					//以二进制和文本打开方式区别在于:以文本打开方式会将\r\n
    		//转换为\n,二进制这不会有这样的转换
    		//char ch = fgetc(fOut);
    		int ch = fgetc(fOut);
    			while (ch != EOF)
    		{
    		_infos[(unsigned char)ch]._count++;
    		ch = fgetc(fOut);
    		Charcount++;
    		}
    		//2.生成对应的huffman编码    
    		GenerateHuffmanCode();
    		//3.文件压缩    
    		string compressFile = filename;
    		compressFile += ".compress";
    		FILE* fwCompress = fopen(compressFile.c_str(), "wb");//以二进制写入
    		assert(fwCompress);
    		fseek(fOut, 0, SEEK_SET);
    		ch = fgetc(fOut);
    		char inch = 0;
    		int pos = 0;
    		while (!feof(fOut))
    		{
    			string& code = _infos[(unsigned char)ch]._code;
    			for (size_t i = 0; i < code.size(); ++i)
    			{
    				inch = inch << 1;
    				if (code[i] == '1')
    				{
    					inch |= 1;
    				}
    				if (++pos == 8)//对于形成的长串字符编码的切割,每8个bit为一个字节,便于读取  
    				{
    					fputc(inch, fwCompress);
    					inch = 0;
    					pos = 0;
    				}
    			}
    			ch = fgetc(fOut);
    		}
    
    		if (pos)//考虑到可能会有切割完,剩余的字符码不够填充8个bit位的情况  
    		{
    			inch = inch << (8 - pos);
    			fputc(inch, fwCompress);
    		}
    		//4.配置文件,方便后续的解压缩;  
    		string configFile = filename;
    		configFile += ".config";
    		FILE *fconfig = fopen(configFile.c_str(), "wb");
    		assert(fconfig);
    		string infoStr;
    		//char CountStr[128];
    		char CountStr[128];
    		_itoa(Charcount >> 32, CountStr, 10);
    		fputs(CountStr, fconfig);
    		fputc('\n', fconfig);
    		_itoa(Charcount & 0xffffffff, CountStr, 10);
    		//_itoa(Charcount & -1, CountStr, 10);
    		fputs(CountStr, fconfig);
    		fputc('\n', fconfig);
    
    		CharInfo invalid;
    		for (int i = 0; i < 256; i++)
    		{
    			if (_infos[i] != invalid)
    			{
    				/*	fputc(_infos[i]._ch, fconfig);
    				fputc(',', fconfig);
    				fputc(_infos[i]._count + '0', fconfig);
    				fputc('\n', fconfig);*/
    				infoStr=_infos[i]._ch;
    				infoStr+=',';
    				_itoa(_infos[i]._count, CountStr, 10);
    			    infoStr+=CountStr;
    				infoStr+='\n';
    				fputs(infoStr.c_str(),fconfig);
    			}
    		}
    
    		fclose(fOut);
    		fclose(fwCompress);
    		fclose(fconfig);
    
    		return true;
    	}

    利用配置文件获取到文件中每个字符出现的次数

    string configfile = filename;
    		configfile += ".config";
    		FILE* outConfig = fopen(configfile.c_str(), "rb");
    		assert(outConfig);
    		char ch=0;
    		/*char ch;*/
    		Longtype Charcount = 0;
    		string line = ReadLine(outConfig);
    		Charcount = atoi(line.c_str());
    		Charcount <<= 32;
    		line.clear();
    		line = ReadLine(outConfig);
    		Charcount += atoi(line.c_str());
    		line.clear();
    
    		while (feof(outConfig))
    			//feof()遇到文件结束,函数值为非零值,否则为0。当把数据以二进制的形式进行存放时,可能会有-1值的出现,
    			//所以此时无法利用-1值(EOF)做为eof()函数判断二进制文件结束的标志。  
    		{
    			line = ReadLine(outConfig);
    			if (!line.empty())
    			{
    				ch = line[0];
    				_infos[(unsigned char)ch]._count += atoi(line.substr(2).c_str());
    				//_infos[(unsigned char)ch]._count += atoi(line.c_str());
    				line.clear();
    			}
    			else
    			{
    				line = '\n';
    			}
    		}


    利用配置文件用小堆再次建立哈弗曼树

    利用配置文件建立的哈弗曼树进行解码生成解压后的文件**.uncompress

    HuffmanTree<CharInfo> ht;
    		CharInfo invalid(0);
    		ht.CreatTree(_infos, 256, invalid);//重新建树
    		HuffmanTreeNode<CharInfo>* root = ht.GetRootNode();
    		string  UnCompressFile = filename;
    		UnCompressFile += ".uncompress";
    		FILE* fIn = fopen(UnCompressFile.c_str(), "wb");
    		string CompressFile = filename;
    		CompressFile += ".compress";
    		FILE* fOut = fopen(CompressFile.c_str(), "rb");
    		int pos = 8;
    		HuffmanTreeNode<CharInfo>* cur = root;
    		ch=fgetc(fOut);
    		while ((unsigned char)ch != EOF)
    		//while(1)
    		{
    			--pos;
    			if ((unsigned char)ch &(1 << pos))
    			{
    				cur = cur->_right;
    			}
    			else
    			{
    				cur = cur->_left;
    			}
    			if (cur->_left == NULL && cur->_right == NULL)
    			{
    				fputc(cur->_weight._ch, fIn);
    				cur = root;
    				Charcount--;
    				
    			}
    			if (pos == 0)
    			{
    				ch = fgetc(fOut);
    				pos = 8;
    			}
    			if (Charcount==0)
    			{
    				break;
    			}}
    
    
    解压缩

    //文件的解压缩 
    	bool UnCompresss(const char* filename)
    	{
    		string configfile = filename;
    		configfile += ".config";
    		FILE* outConfig = fopen(configfile.c_str(), "rb");
    		assert(outConfig);
    		char ch=0;
    		/*char ch;*/
    		Longtype Charcount = 0;
    		string line = ReadLine(outConfig);
    		Charcount = atoi(line.c_str());
    		Charcount <<= 32;
    		line.clear();
    		line = ReadLine(outConfig);
    		Charcount += atoi(line.c_str());
    		line.clear();
    
    		while (feof(outConfig))
    			//feof()遇到文件结束,函数值为非零值,否则为0。当把数据以二进制的形式进行存放时,可能会有-1值的出现,
    			//所以此时无法利用-1值(EOF)做为eof()函数判断二进制文件结束的标志。  
    		{
    			line = ReadLine(outConfig);
    			if (!line.empty())
    			{
    				ch = line[0];
    				_infos[(unsigned char)ch]._count += atoi(line.substr(2).c_str());
    				//_infos[(unsigned char)ch]._count += atoi(line.c_str());
    				line.clear();
    			}
    			else
    			{
    				line = '\n';
    			}
    		}
    
    		HuffmanTree<CharInfo> ht;
    		CharInfo invalid(0);
    		ht.CreatTree(_infos, 256, invalid);//重新建树
    		HuffmanTreeNode<CharInfo>* root = ht.GetRootNode();
    		string  UnCompressFile = filename;
    		UnCompressFile += ".uncompress";
    		FILE* fIn = fopen(UnCompressFile.c_str(), "wb");
    		string CompressFile = filename;
    		CompressFile += ".compress";
    		FILE* fOut = fopen(CompressFile.c_str(), "rb");
    		int pos = 8;
    		HuffmanTreeNode<CharInfo>* cur = root;
    		ch=fgetc(fOut);
    		while ((unsigned char)ch != EOF)
    		//while(1)
    		{
    			--pos;
    			if ((unsigned char)ch &(1 << pos))
    			{
    				cur = cur->_right;
    			}
    			else
    			{
    				cur = cur->_left;
    			}
    			if (cur->_left == NULL && cur->_right == NULL)
    			{
    				fputc(cur->_weight._ch, fIn);
    				cur = root;
    				Charcount--;
    				
    			}
    			if (pos == 0)
    			{
    				ch = fgetc(fOut);
    				pos = 8;
    			}
    			if (Charcount==0)
    			{
    				break;
    			}
    		}
    
    		
    		fclose(fIn);
    		fclose(fOut);
            fclose(outConfig);
    		return true;
    	}



    文件压缩代码

    FileCompress.h

    #define _CRT_SECURE_NO_WARNINGS 1
    #pragma once
    #include"HuffmanTree.h"  
    #include<iostream>
    #include<algorithm>  
    #include<windows.h>  
    #include<string.h>  
    using namespace std;
    typedef long long Longtype;//为了扩大其范围,int型能处理的范围已经不能满足,所以定义Long Long型予以表示  
    
    struct CharInfo
    {
    	unsigned char _ch;//这里必须为unsigned,否则会造成截断,所以从-128~127调至0~255.  
    	Longtype _count;
    	string _code;
    
    	CharInfo(int count = 0)
    		:_ch(0)
    		, _count(count)
    		,_code("")
    	{}
    
    	CharInfo operator+(CharInfo& file)//重载+
    	{
    		CharInfo tmp;
    		tmp._count = _count + file._count;
    		return tmp;
    	}
    
    	bool operator < (CharInfo& file) const//重载<
    	{
    		return _count < file._count;
    	}
    
    	bool operator != (const CharInfo& file) const//重载!=
    	{
    		return _count != file._count;
    	}
    };
    
    
    template<class T>
    class FileCompress
    {
    public:
    	FileCompress()
    	{
    		for (int i = 0; i < 256; ++i)//初始化
    		{
    			_infos[i]._ch = i;
    		}
    	}
    	bool Compress(const char* filename)
    	{
    		//1.打开文件,统计文件字符出现的次数    
    		Longtype Charcount = 0;
    		assert(filename);
    		FILE* fOut = fopen(filename, "rb");//之前用“r”,结果出了一点问题
    		//"rb"为以二进制方式读取文件,这里的b就是binary。"wb"为以二进制方式写入文件  
    		assert(fOut);					//以二进制和文本打开方式区别在于:以文本打开方式会将\r\n
    		//转换为\n,二进制这不会有这样的转换
    		//char ch = fgetc(fOut);
    		int ch = fgetc(fOut);
    			while (ch != EOF)
    		{
    		_infos[(unsigned char)ch]._count++;
    		ch = fgetc(fOut);
    		Charcount++;
    		}
    		//2.生成对应的huffman编码    
    		GenerateHuffmanCode();
    		//3.文件压缩    
    		string compressFile = filename;
    		compressFile += ".compress";
    		FILE* fwCompress = fopen(compressFile.c_str(), "wb");//以二进制写入
    		assert(fwCompress);
    		fseek(fOut, 0, SEEK_SET);
    		ch = fgetc(fOut);
    		char inch = 0;
    		int pos = 0;
    		while (!feof(fOut))
    		{
    			string& code = _infos[(unsigned char)ch]._code;
    			for (size_t i = 0; i < code.size(); ++i)
    			{
    				inch = inch << 1;
    				if (code[i] == '1')
    				{
    					inch |= 1;
    				}
    				if (++pos == 8)//对于形成的长串字符编码的切割,每8个bit为一个字节,便于读取  
    				{
    					fputc(inch, fwCompress);
    					inch = 0;
    					pos = 0;
    				}
    			}
    			ch = fgetc(fOut);
    		}
    
    		if (pos)//考虑到可能会有切割完,剩余的字符码不够填充8个bit位的情况  
    		{
    			inch = inch << (8 - pos);
    			fputc(inch, fwCompress);
    		}
    		//4.配置文件,方便后续的解压缩;  
    		string configFile = filename;
    		configFile += ".config";
    		FILE *fconfig = fopen(configFile.c_str(), "wb");
    		assert(fconfig);
    		string infoStr;
    		//char CountStr[128];
    		char CountStr[128];
    		_itoa(Charcount >> 32, CountStr, 10);
    		fputs(CountStr, fconfig);
    		fputc('\n', fconfig);
    		_itoa(Charcount & 0xffffffff, CountStr, 10);
    		//_itoa(Charcount & -1, CountStr, 10);
    		fputs(CountStr, fconfig);
    		fputc('\n', fconfig);
    
    		CharInfo invalid;
    		for (int i = 0; i < 256; i++)
    		{
    			if (_infos[i] != invalid)
    			{
    				/*	fputc(_infos[i]._ch, fconfig);
    				fputc(',', fconfig);
    				fputc(_infos[i]._count + '0', fconfig);
    				fputc('\n', fconfig);*/
    				infoStr=_infos[i]._ch;
    				infoStr+=',';
    				_itoa(_infos[i]._count, CountStr, 10);
    			    infoStr+=CountStr;
    				infoStr+='\n';
    				fputs(infoStr.c_str(),fconfig);
    			}
    		}
    
    		fclose(fOut);
    		fclose(fwCompress);
    		fclose(fconfig);
    
    		return true;
    	}
    	//文件的解压缩 
    	bool UnCompresss(const char* filename)
    	{
    		string configfile = filename;
    		configfile += ".config";
    		FILE* outConfig = fopen(configfile.c_str(), "rb");
    		assert(outConfig);
    		char ch=0;
    		/*char ch;*/
    		Longtype Charcount = 0;
    		string line = ReadLine(outConfig);
    		Charcount = atoi(line.c_str());
    		Charcount <<= 32;
    		line.clear();
    		line = ReadLine(outConfig);
    		Charcount += atoi(line.c_str());
    		line.clear();
    
    		while (feof(outConfig))
    			//feof()遇到文件结束,函数值为非零值,否则为0。当把数据以二进制的形式进行存放时,可能会有-1值的出现,
    			//所以此时无法利用-1值(EOF)做为eof()函数判断二进制文件结束的标志。  
    		{
    			line = ReadLine(outConfig);
    			if (!line.empty())
    			{
    				ch = line[0];
    				_infos[(unsigned char)ch]._count += atoi(line.substr(2).c_str());
    				//_infos[(unsigned char)ch]._count += atoi(line.c_str());
    				line.clear();
    			}
    			else
    			{
    				line = '\n';
    			}
    		}
    
    		HuffmanTree<CharInfo> ht;
    		CharInfo invalid(0);
    		ht.CreatTree(_infos, 256, invalid);//重新建树
    		HuffmanTreeNode<CharInfo>* root = ht.GetRootNode();
    		string  UnCompressFile = filename;
    		UnCompressFile += ".uncompress";
    		FILE* fIn = fopen(UnCompressFile.c_str(), "wb");
    		string CompressFile = filename;
    		CompressFile += ".compress";
    		FILE* fOut = fopen(CompressFile.c_str(), "rb");
    		int pos = 8;
    		HuffmanTreeNode<CharInfo>* cur = root;
    		ch=fgetc(fOut);
    		while ((unsigned char)ch != EOF)
    		//while(1)
    		{
    			--pos;
    			if ((unsigned char)ch &(1 << pos))
    			{
    				cur = cur->_right;
    			}
    			else
    			{
    				cur = cur->_left;
    			}
    			if (cur->_left == NULL && cur->_right == NULL)
    			{
    				fputc(cur->_weight._ch, fIn);
    				cur = root;
    				Charcount--;
    				
    			}
    			if (pos == 0)
    			{
    				ch = fgetc(fOut);
    				pos = 8;
    			}
    			if (Charcount==0)
    			{
    				break;
    			}
    		}
    
    		
    		fclose(fIn);
    		fclose(fOut);
            fclose(outConfig);
    		return true;
    	}
    
    protected:
    	string ReadLine(FILE* fOut)
    	{
    		assert(fOut);
    		char ch = fgetc(fOut);
    		if (feof(fOut))
    		{
    			return 0;
    		}
    		string line;
    		while (ch != '\n')
    		{
    			line += ch;
    			ch = fgetc(fOut);
    
    			if (feof(fOut))
    				break;
    		}
    		return line;
    	}
    	void GenerateHuffmanCode()
    	{
    		HuffmanTree<CharInfo> hft;
    		CharInfo invalid;
    
    		hft.CreatTree(_infos, 256, invalid);
    		_GenerateHuffmanCode(hft.GetRootNode());
    	}
    protected:
    	void _GenerateHuffmanCode(HuffmanTreeNode<CharInfo>* root)//创建哈夫曼编码
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    
    		_GenerateHuffmanCode(root->_left);
    		_GenerateHuffmanCode(root->_right);
    
    		if (root->_left == NULL && root->_right == NULL)
    		{
    			HuffmanTreeNode<CharInfo>* cur = root;
    			HuffmanTreeNode<CharInfo>* parent = cur->_parent;
    			string& code = _infos[cur->_weight._ch]._code;
    
    			while (parent)
    			{
    				if (parent->_left == cur)//往左走+0
    				{
    					code += '0';
    				}
    				else if (parent->_right == cur)//往右走+1
    				{
    					code += '1';
    				}
    				cur = parent;
    				parent = cur->_parent;
    			}
    			//寻找编码从叶子节点开始。
    			reverse(code.begin(), code.end());
    		}
    	}
    
    	//递归实现哈夫曼编码
    	void _GenerateHuffmanCode_R(HuffmanTreeNode<CharInfo>* root,string code)//创建哈夫曼编码
    	{
    		if(root==NULL)
    			return;
    		_GenerateHuffmanCode_R(root->_left,code+'0');
    		_GenerateHuffmanCode_R(root->_right,code+'1');
    		if(root->_left==NULL&&root->_right==NULL)
    		{
    			_infos[root->_weight._ch]._code=code;
    		}
    	}
    private:
    	CharInfo _infos[256];
    };
    
    void TestFileCompress()
    {
    	cout<<"一次压缩"<<endl;
    	FileCompress<CharInfo> fc;
    	cout << "Input.txt文件压缩中...." << endl;
    	cout << "压缩用时: ";
    	int begin1 = GetTickCount();//记录开始时间
    	fc.Compress("Input.txt");//  
    	int end1 = GetTickCount();//  记录结束时间
    	cout << end1 - begin1 << endl << endl;//压缩时间
    
    	cout << "Input.txt文件解压中...." << endl;;
    	cout << "解压用时: ";
    	int begin2 = GetTickCount();
    	fc.UnCompresss("Input.txt");
    	int end2 = GetTickCount(); 
    	cout << end2 - begin2 << endl << endl;//解压用时
    
    	FileCompress<CharInfo> fc1;
    
    	cout << "Input.BIG文件压缩中...." << endl;
    	cout << "压缩用时: ";
    	int begin3 = GetTickCount();
    	fc1.Compress("Input.BIG");//  
    	int end3 = GetTickCount();//  
    	cout << end3 - begin3 << endl << endl;
    
    	cout << "Input.BIG文件解压中...." << endl;
    	cout << "解压用时: ";
    	int begin4 = GetTickCount();
    	fc1.UnCompresss("Input.BIG");
    	int end4 = GetTickCount();  
    	cout << (end4 - begin4 )<< endl;
    
    	FileCompress<CharInfo> fc2;
    	cout << "康熙字典.txt文件压缩中...." << endl;
    	cout << "压缩用时: ";
    	int begin5 = GetTickCount();//记录开始时间
    	fc2.Compress("康熙字典.txt");//  
    	int end5 = GetTickCount();//  记录结束时间
    	cout << end5 - begin5 << endl << endl;//压缩时间
    
    	cout << "康熙字典.txt文件解压中...." << endl;;
    	cout << "解压用时: ";
    	int begin6 = GetTickCount();
    	fc2.UnCompresss("康熙字典.txt");
    	int end6 = GetTickCount(); 
    	cout << end6 - begin6 << endl << endl;//解压用时
    }
    void TestFileCompressAgain()//二次压缩
    {
    	cout<<"二次压缩"<<endl;
    	FileCompress<CharInfo> fc;
    	cout << "Input.txt.compress文件压缩中...." << endl;
    	cout << "压缩用时: ";
    	int begin1 = GetTickCount();//记录开始时间
    	fc.Compress("Input.txt.compress");//  
    	int end1 = GetTickCount();//  记录结束时间
    	cout << end1 - begin1 << endl << endl;//压缩时间
    
    	cout << "Input.txt.compress文件解压中...." << endl;;
    	cout << "解压用时: ";
    	int begin2 = GetTickCount();
    	fc.UnCompresss("Input.txt.compress");
    	int end2 = GetTickCount(); 
    	cout << end2 - begin2 << endl << endl;//解压用时
    
    	FileCompress<CharInfo> fc1;
    	cout << "Input.BIG.compress文件压缩中...." << endl;
    	cout << "压缩用时: ";
    	int begin3 = GetTickCount();//记录开始时间
    	fc1.Compress("Input.BIG.compress");//  
    	int end3 = GetTickCount();//  记录结束时间
    	cout << end3 - begin3 << endl << endl;//压缩时间
    
    	cout << "Input.BIG.compress文件解压中...." << endl;;
    	cout << "解压用时: ";
    	int begin4 = GetTickCount();
    	fc1.UnCompresss("Input.BIG.compress");
    	int end4 = GetTickCount(); 
    	cout << end4 - begin4 << endl << endl;//解压用时
    
    
    	
    }
    void TestFileCompressThree()
    {
    	cout<<"三次压缩"<<endl;
    	FileCompress<CharInfo> fc;
    	cout << "Input.BIG.compress.compress文件压缩中...." << endl;
    	cout << "压缩用时: ";
    	int begin5 = GetTickCount();//记录开始时间
    	fc.Compress("Input.BIG.compress.compress");//  
    	int end5 = GetTickCount();//  记录结束时间
    	cout << end5 - begin5 << endl << endl;//压缩时间
    
    	cout << "Input.BIG.compress.compress文件解压中...." << endl;;
    	cout << "解压用时: ";
    	int begin6 = GetTickCount();
    	fc.UnCompresss("Input.BIG.compress.compress");
    	int end6 = GetTickCount(); 
    	cout << end6 - begin6 << endl << endl;//解压用时
    }
    
    void TestFileCompressFour()
    {
    	cout<<"四次压缩"<<endl;
    	FileCompress<CharInfo> fc;
    	cout << "Input.BIG.compress.compress.compress文件压缩中...." << endl;
    	cout << "压缩用时: ";
    	int begin5 = GetTickCount();//记录开始时间
    	fc.Compress("Input.BIG.compress.compress.compress");//  
    	int end5 = GetTickCount();//  记录结束时间
    	cout << end5 - begin5 << endl << endl;//压缩时间
    
    	cout << "Input.BIG.compress.compress.compress文件解压中...." << endl;;
    	cout << "解压用时: ";
    	int begin6 = GetTickCount();
    	fc.UnCompresss("Input.BIG.compress.compress.compress");
    	int end6 = GetTickCount(); 
    	cout << end6 - begin6 << endl << endl;//解压用时
    }
    void TestFileCompressFive()
    {
    	cout<<"五次压缩"<<endl;
    	FileCompress<CharInfo> fc;
    	cout << "Input.BIG.compress.compress.compress.compress文件压缩中...." << endl;
    	cout << "压缩用时: ";
    	int begin5 = GetTickCount();//记录开始时间
    	fc.Compress("Input.BIG.compress.compress.compress.compress");//  
    	int end5 = GetTickCount();//  记录结束时间
    	cout << end5 - begin5 << endl << endl;//压缩时间
    
    	cout << "Input.BIG.compress.compress.compress.compress文件解压中...." << endl;;
    	cout << "解压用时: ";
    	int begin6 = GetTickCount();
    	fc.UnCompresss("Input.BIG.compress.compress.compress.compress");
    	int end6 = GetTickCount(); 
    	cout << end6 - begin6 << endl << endl;//解压用时
    }
    void TestFileCompressPhoto()
    {
    	cout<<"图片压缩"<<endl;
    	FileCompress<CharInfo> fc;
    	cout << "166.jpg文件压缩中...." << endl;
    	cout << "压缩用时: ";
    	int begin5 = GetTickCount();//记录开始时间
    	fc.Compress("166.jpg");//  
    	int end5 = GetTickCount();//  记录结束时间
    	cout << end5 - begin5 << endl << endl;//压缩时间
    
    	cout << "166.jpg文件解压中...." << endl;;
    	cout << "解压用时: ";
    	int begin6 = GetTickCount();
    	fc.UnCompresss("166.jpg");
    	int end6 = GetTickCount(); 
    	cout << end6 - begin6 << endl << endl;//解压用时
    	
    }
    void TestFileCompressVadio()
    {
    	cout<<"视频压缩"<<endl;
    	FileCompress<CharInfo> fc;
    	cout << "釜山行_hd.mp4文件压缩中...." << endl;
    	cout << "压缩用时: ";
    	int begin5 = GetTickCount();//记录开始时间
    	fc.Compress("釜山行_hd.mp4");//  
    	int end5 = GetTickCount();//  记录结束时间
    	cout << end5 - begin5 << endl << endl;//压缩时间
    
    	cout << "釜山行_hd.mp4文件解压中...." << endl;;
    	cout << "解压用时: ";
    	int begin6 = GetTickCount();
    	fc.UnCompresss("釜山行_hd.mp4");
    	int end6 = GetTickCount(); 
    	cout << end6 - begin6 << endl << endl;//解压用时
    }
    main函数

    #include "FileCompress.h"
    using namespace std;
    int main()
    {
    
    	TestFileCompress();
    	TestFileCompressAgain();
    	TestFileCompressThree();
    	TestFileCompressFour();
    	TestFileCompressFive();
    	TestFileCompressPhoto();
    	TestFileCompressVadio();
    	system("pause");
    	return 0;
    }
    压缩结果分析

    1、多次压缩普通文件

    时间分析





    正确性分析

    源文件和解压完结果完全相同


    大小分析

    源文件和解压完结果完全相同


    由于文件太小倒置后面几次压缩大小未发生改变


    2、解压图片文件及视频文件

    时间分析

    视频文件较大用时238354ms


    图片正确性分析

    源文件和解压完结果完全相同


    分析大小

    源文件和解压完结果完全相同



    展开全文
  • 数据解压 byte[] --> String package tree.huffmancode; import java.util.*; public class HuffmanCodeDemo { public static void main(String[] args) { String content = "i like like like java do you ...

    赫夫曼编码

    数据解压

    byte[] --> String

    package tree.huffmancode;
    
    import java.util.*;
    
    public class HuffmanCodeDemo {
        public static void main(String[] args) {
            String content = "i like like like java do you like a java";
            byte[] contentBytes = content.getBytes();
            byte[] huffmanCodesBytes = huffmanZip(contentBytes);
            System.out.println("after compression:"+Arrays.toString(huffmanCodesBytes));
            byte[] sourceBytes = decode(huffmanCodes, huffmanCodesBytes);
            System.out.println("original string" +new String(sourceBytes));
    
            /*
            List<Node> nodes = getNode(contentBytes);
            System.out.println(nodes);
            // [Node{data=32, weight=9}, Node{data=97, weight=5}, Node{data=100, weight=1},
            Node huffmanTreeRoot = CreateHuffmanTree(nodes);
            huffmanTreeRoot.preOrder();
            System.out.println("huffman code: ");
            getCodes(huffmanTreeRoot);
            // System.out.println(huffmanCodes);
            byte[] huffmanCodeBytes =  zip(contentBytes,huffmanCodes);
            System.out.println(Arrays.toString(huffmanCodeBytes)); // length:17
             */
        }
    
    
        // decompression
    
        /**
         *
         * @param huffmanCodes huffman coding table -- map
         * @param huffmanBytes huffman code -> byte array [-88....]
         * @return original string corresponding array
         */
        private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){
            // 1. get binary string corresponding to huffmanBytes, eg:10101000..
            StringBuilder stringBuilder = new StringBuilder();
            // byte --> binary string
            for(int i = 0; i<huffmanBytes.length;i++){
                byte b = huffmanBytes[i];
                // 判断是不是最后一个字节
                boolean flag = (i==huffmanBytes.length-1);
                stringBuilder.append(byteToBitString(!flag,b));
            }
            // 把字符串安装指定的赫夫曼编码进行解码
            // 把赫夫曼编码表进行调换,因为要反向查询 a->100 100->a
            Map<String,Byte> map = new HashMap<String,Byte>();
            for(Map.Entry<Byte,String> entry:huffmanCodes.entrySet()){
                map.put(entry.getValue(),entry.getKey());
            }
            // build a collection, store byte
            List<Byte> list = new ArrayList<>();
            // i 可以理解成是索引,在扫描 stringBuilder
            for(int i = 0;i<stringBuilder.length();){
                int count = 1; // 计数器
                boolean flag = true;
                Byte b = null;
                while(flag){
                    // 取出一个 "1" "0"
                    // 递增的取出key
                    String key = stringBuilder.substring(i,i+count);
                    // i 不动,让 count 移动, 指定匹配到一个字符
                    b = map.get(key);
                    if(b==null){
                        count++;
                    } else{
                        // 匹配到
                        flag = false;
                    }
                }
                list.add(b);
                i+=count; // i直接移动到count
            }
            // for循环结束后,list中就存放了所有的字符
            // list中的数据放入byte[] 并返回
            byte b[] = new byte[list.size()];
            for(int i=0;i<b.length;i++){
                b[i] = list.get(i);
            }
            return b;
    
    
        }
    
    
        // date decompression
        // 1. huffman code bytes [-88,-65,-56...]
        //      ---> binary corresponding huffman code: 1001010...
        //      ---> "i like like...."
    
        /**
         * transfer a byte to a binary string
         * @param b 传入的byte
         * @param flag 标识是否需要补高位,如果是true,表示需要补高位,如果是false表示不补,如果是最后一个字节,无需补高位
         * @return 是该b 对应的二进制的字符串(注意是按补码返回)
         */
        private static String byteToBitString(boolean flag,byte b){
            // use a variable save b
            int temp = b; // transfer b to int
            // 如果是正数,需要补高位
            if(flag){
                temp |= 256; // 按位与 256:1 0000 0000
                //                      1:0000 0001
                //                      => 1 0000 0001
            }
            String str = Integer.toBinaryString(temp); // 返回的是temp对应的二进制的补码
            if(flag){
                return str.substring(str.length()-8); // 取后面的8位
            } else{
                return str;
            }
        }
    
    
    
    
    
        // use a method packaging methods' calls
    
        /**
         *
         * @param bytes byte array corresponding to the original string (content bytes)
         * @return byte array after processing by huffman code (compression array)
         */
        private static byte[] huffmanZip(byte[] bytes){
            List<Node> nodes = getNode(bytes);
            Node huffmanTreeRoot = CreateHuffmanTree(nodes);
            Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
            byte[] huffmanCodeBytes =  zip(bytes, HuffmanCodeDemo.huffmanCodes);
            return huffmanCodeBytes;
        }
    
        // byte[] of string ---> huffman code table ---> huffman code(byte[])
    
        /**
         *
         * @param bytes The byte array corresponding to the original string
         * @param huffmanCodes Huffman codes map
         * @return byte[] processed by huffman code, byte[] corresponding to "10101000..."
         * 8 bit --> 1 byte, put into huffmanCodeBytes
         * huffmanCodeBytes[0] = 10101000(complement补码) => byte[10101000=>10101000-1=>10100111(Inverted code 补码对应的反码)
         * => 11011000 = -88(original code 反码对应的原码:符号位/第一位不变,其他位取反))
         * huffmanCodeBytes[1] = -88
         */
        private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCodes){
            // 1. transfer bytes to string corresponding to huffmanCode using huffmanCodes
            StringBuilder stringBuilder = new StringBuilder();
            // traverse bytes
            for(byte b:bytes){
                stringBuilder.append(huffmanCodes.get(b));
            }
    
            // stringBuilder -> byte[]
            // count length of byte[] huffmanCodeBytes
            int len;
            if(stringBuilder.length() % 8 == 0){
                len = stringBuilder.length()/8;
            } else{
                len = stringBuilder.length() / 8 + 1;
            }
            // one line: int len = (stringBuilder.length()+7)/8;
    
            // create byte[] store data after compression
            byte[] huffmanCodeBytes = new byte[len];
            int index = 0; // record number of byte
            for(int i = 0;i < stringBuilder.length();i+=8){ // 8 bit->1 byte
                String strByte;
                if(i+8 > stringBuilder.length()){ // not enough 8 bit
                    strByte = stringBuilder.substring(i);
                }else{
                    strByte = stringBuilder.substring(i,i+8);
                    // strByte --> byte array --> put into huffmanCodeBytes
                }
                huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte,2); // string -> binary
                index++;
            }
            return huffmanCodeBytes;
        }
    
    
    
        // huffman coding based on huffman tree
        // 1. huffman coding is stored in Map<Byte,String>, eg: o:1000 u:10010
        static Map<Byte,String> huffmanCodes = new HashMap<Byte,String>();
        // 2. define a StringBuilder storing path of leaf node when creating huffman code
        static StringBuilder stringBuilder = new StringBuilder();
    
        // for convenience, override getCodes()
        private static Map<Byte,String> getCodes(Node root){
            if(root==null){
                return null;
            }
            getCodes(root.left,"0",stringBuilder);
            getCodes(root.right,"1",stringBuilder);
            return huffmanCodes;
        }
    
        /**
         * get all leaf nodes' huffman code of given node, putting into huffmanCodes collection
         * @param node given node, root
         * @param code path: left node:0; right node:1;
         * @param stringBuilder splice path
         */
        private static void getCodes(Node node,String code,StringBuilder stringBuilder){
            StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
            // add code into stringBuilder2
            stringBuilder2.append(code);
            if(node!=null){ // if node==null, pass
                // determine current node is leaf node or non-leaf node
                if(node.data==null){
                    // recursion
                    // left
                    getCodes(node.left,"0",stringBuilder2);
                    // right
                    getCodes(node.right,"1",stringBuilder2);
                } else{ // leaf node
                    huffmanCodes.put(node.data,stringBuilder2.toString());
                }
            }
        }
    
        private static void preOrder(Node root){
            if(root!=null){
                root.preOrder();
            }else{
                System.out.println("empty");
            }
        }
    
    
        /**
         *
         * @param bytes receive byte[]
         * @return List like: [Node[data=97 (ascii) ,weight = 5], Node[data = 32, weight = 9]]
         */
        private static List<Node> getNode(byte[] bytes){
            // 1. create an arraylist
            ArrayList<Node> nodes = new ArrayList<>();
            // 2. traverse bytes, count each byte frequency --> map[key,value]
            HashMap<Byte, Integer> counts = new HashMap<>();
            for(byte b:bytes){
                Integer count = counts.get(b);
                if(count==null){ // no data in map
                    counts.put(b,1);
                }else{
                    counts.put(b,count+1);
                }
            }
            // 3. transfer each key-value pair to a Node object, add to nodes collection
            for(Map.Entry<Byte,Integer> entry:counts.entrySet()){
                nodes.add(new Node(entry.getKey(),entry.getValue()));
            }
            return nodes;
        }
    
        // build huffman tree
        private static Node CreateHuffmanTree(List<Node> nodes){
            while(nodes.size()>1){
                Collections.sort(nodes);
                Node leftNode = nodes.get(0);
                Node rightNode = nodes.get(1);
                Node parent = new Node(null,leftNode.weight+rightNode.weight);
                parent.left = leftNode;
                parent.right = rightNode;
                nodes.remove(leftNode);
                nodes.remove(rightNode);
                nodes.add(parent);
            }
            return nodes.get(0);
        }
    }
    
    // create Node class, with data and weight
    class Node implements Comparable<Node>{
        Byte data; // store data, eg: 'a' --> 97 ' ' --> 32
        int weight; // weight: number of characters|frequency
        Node left;
        Node right;
    
        public Node(Byte data, int weight) {
            this.data = data;
            this.weight = weight;
        }
    
        @Override
        public int compareTo(Node o) {
            return this.weight-o.weight; // ascending
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", weight=" + weight +
                    '}';
        }
    
        // preOrder
        public void preOrder(){
            System.out.println(this);
            if(this.left!=null){
                this.left.preOrder();
            }
            if(this.right!=null){
                this.right.preOrder();
            }
        }
    }
    

    文件压缩

    读取文件 – 得到赫夫曼编码表 – 完成压缩 – 得到.zip文件

     // compress file
    
        /**
         *
         * @param srcFile path of file need to be compressed
         * @param dstFile path that stores the file after decompressing
         */
        public static void zipFile(String srcFile,String dstFile){
            // output stream
    
            // input stream read file
            FileInputStream fis = null;
            ObjectOutputStream oos = null;
            FileOutputStream fos = null;
            try {
                fis = new FileInputStream(srcFile);
                byte[] b = new byte[fis.available()]; // length of original file
                // read file
                fis.read(b);
                // get huffman code corresponding to file
                // compress original file
                byte[] huffmanBytes = huffmanZip(b);
                // create output stream storing compress file
                fos = new FileOutputStream(dstFile);
                // create ObjectOutputStream corresponding to file output stream
                oos = new ObjectOutputStream(fos);
                // 把赫夫曼编码后的字节数组写入压缩文件
                oos.writeObject(huffmanBytes);
                // 以对象流的方式写入赫夫曼编码,为了以后恢复源文件时使用
                oos.writeObject(huffmanCodes);
    
            } catch (Exception e) {
                System.out.println(e.getMessage());
            } finally {
                try {
                    fis.close();
                    fos.close();
                    oos.close();
                } catch (IOException e) {
                    System.out.println(e.getMessage());
                }
            }
        }
    
    			  // test compress file
            String srcFile = "/Users/pz/Desktop/img4.jpg";
            String dstFile = "/Users/pz/Desktop/dst.dmg";
            zipFile(srcFile,dstFile);
            System.out.println("compress done");
    

    文件解压

    读取解压文件(数据和赫夫曼编码表)-- 俄暗沉解压

    // unzip file
    
        /**
         *
         * @param zipFile file for unzip
         * @param dstFile path for saving
         */
        public static void unzipFile(String zipFile,String dstFile){
            // define file input stream
            InputStream is = null;
            // define a object input stream
            ObjectInputStream ois = null;
            // define file output stream
            OutputStream os = null;
            try{
                // create file input stream
                is = new FileInputStream(zipFile);
                // create a object input stream corresponding to is
                ois = new ObjectInputStream(is);
                // read byte[] huffmanBytes
                byte[] huffmanBytes = (byte[])ois.readObject();
                // read huffman codes
                Map<Byte,String> huffmanCodes = (Map<Byte, String>) ois.readObject();
                // decode
                byte[] bytes = decode(huffmanCodes,huffmanBytes);
                // write file to dsfFile
                os = new FileOutputStream(dstFile);
                // write data to file
                os.write(bytes);
    
            }catch(Exception e){
                System.out.println(e.getMessage());
            }finally {
                try {
                    os.close();
                    ois.close();
                    is.close();
                } catch (IOException e) {
                    System.out.println(e.getMessage());
                }
            }
        }
    
          // test decode file
            String zipFile = "/Users/pz/Desktop/dst.dmg";
            String dstFile = "/Users/pz/Desktop/su.jpg";
            unzipFile(zipFile,dstFile);
            System.out.println("success");
    
    展开全文
  • 【C语言】【数据结构】【压缩、解压缩】利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小,减少存储空间。这要求在首先对一个现有文件进行编码行成新的文件,也就是压缩。在文件使用时,再对压缩...
  • 数据结构实验报告 实验名称文件压缩 实验类型综合性试验 班级20112111 学号2011211107 姓名冯若航 实验日期2003.6.19 下午4:00 1.问题描述 文件压缩 = 1 \* GB3 基本要求 哈夫曼编码是一种常用的数据压缩技术对数据...
  • 学习数据结构和算法的日常Demo 文件压缩实例 代码实现 public class HuffmanCode { ... // 测试压缩文件 // String srcFile = "E:\\代码仓库\\Java_DataStructure\\数据结构与算法\\1.txt"; /...
  • 大二上学期做的数据结构课程设计–哈夫曼编码实现压缩文件。 哈夫曼树的数据结构 //哈夫曼树的结点的结构 class HufNode{ public: int weight = 0;//节点权重 char key;//节点数据 string code="";//节点编码 ...
  • 数据压缩实践-用哈夫曼编码压缩解压文件 引言: 哈夫曼编码的一大用处便是数据压缩,我们在学完之后,当然要学会试着运用其来压缩解压文件。一下便是写着做的文件压缩尝试。 文件准备: 首先在D盘下准备个了个34kB...
  • Java 数据结构和算法 - 文件压缩prefix codes哈夫曼算法实现位输入和位输出流类字符计数类哈夫曼树类压缩类主程序改进 假设你有一个文件,只包含下列字符:a、e、i、s、t、空格(sp)和换行符(nl)。而且,文件里...
  • 数据结构大作业——哈夫曼编码压缩BMP格式文件

    千次阅读 多人点赞 2020-04-17 10:21:06
    数据结构大作业——哈夫曼编码压缩BMP格式文件 首先需要了解BMP图像格式 BMP图像格式详解 其次需要了解哈夫曼编码如何对BMP文件进行压缩 哈夫曼压缩与解压缩 编程部分 从BMP文件中读取需要的内容 首先是自定义图像...
  • 数据结构 用哈夫曼编码实现文件压缩 直接能用不用改 带有实验报告书
  • huffman压缩 数据结构

    2012-11-19 10:42:05
    huffman 压缩文件 数据结构北邮
  • C++数据结构与算法_第4版_Adam. 共四个压缩文件,在我的所有资源里会找到剩下的三卷。
  • 数据结构课程设计-基于Huffman编码的文件压缩与解压缩 2.2.1结构设计 typedef struct Node { unsigned char ch;//字符 double weight;//字符的频数 int parent,lchild,rchild; }HTNode,HuffmanTree[2*N-1];//...
  • NULL 博文链接:https://qq-24665727.iteye.com/blog/2280055
  • 数据结构,哈夫曼编码,文件压缩和解压缩一个完整的程序,大神们最好能带点注释,简单点的就行。重点:哈夫曼编码,文件压缩和解压缩
  • 利用霍夫曼编码编写文本文件压缩程序.内有代码和设计报告
  • c语言 谭浩强版 ppt幻灯片 rar压缩文件 基础知识覆盖面很全,包含数据结构部分,值得下载
  • //17 //发送huffmanCodeBytes 数组 */ } //编写一个方法,完成对压缩文件的解压 /** * * @param zipFile 准备解压的文件 * @param dstFile 将文件解压到哪个路径 */ public static void unZipFile(String zipFile, ...
  • 数据结构实验报告利用 数据结构实验报告 利用Huffman编码对文件进行压缩解压 学生:XXX 学号:XXXXXXXX 联系:XXXXXX@ 实验题目 利用Huffman编码对文件进行压缩解压 完成人姓名学号 姓名XXX 学号XXXXXXXX 报告日期 2007...
  • 数据结构与算法之编码、解码、文件压缩文件解压实体映射代码实现 实体映射 public class Node implements Comparable<Node>{ Byte data; // 构造的节点树 int weight; // 权值 Node left; // 左节点 ...
  • 哈夫曼编码是一种编码格式,属于可变字长编码的一种,该方法依照字符出现的概率来构建异字头的平均长度最短的码字,最终实现根据使用频率来最大化节省码字(字符)的存储空间和提高传输效率的目的,在数据压缩和通讯...
  • 基于Huffman树的文件压缩C语言源码,自己做的数据结构课程设计。可以安装到系统,实现了文件的右键压缩功能。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,295
精华内容 1,318
关键字:

数据结构压缩文件

数据结构 订阅