精华内容
下载资源
问答
  • 写入压缩文件,后缀.huf,先写入文件头(包括文件类型,权值列表,文件长度,以便于从压缩文件中再次生成哈夫曼编码来解压,也可以用其他的方式,比如直接将哈夫曼编码以先序遍历的方式写入压缩文件的开始,代码中有...
    1. 整体思路:
    • 读原文件,获得权值列表,生成哈夫曼树,遍历树生成哈夫曼编码。
    • 写入压缩文件,后缀.huf,先写入文件头(包括文件类型,权值列表,文件长度,以便于从压缩文件中再次生成哈夫曼编码来解压,也可以用其他的方式,比如直接将哈夫曼编码以先序遍历的方式写入压缩文件的开始,代码中有体现)。
    • 将原文件编码后写入压缩文件。
    • 读取压缩文件,生成哈夫曼树,每次读取到0则向左子树移动,读取到1向右子树移动,直到遇到叶子结点,将叶子结点存储的编码写入解压文件。
    • 值得注意的的是,权值数组的运作。图片文件按二进制读取,一个字节一个字节读,那么每个字节有8位二进制,则用unsigned char读取,最多只会有0~255种可能的值,即权值数组的大小设成256。
    1. 数据结构并没有使用真正意义上的树,即包括指向结点的指针,而使用一个结点数组来保存树,结点中存储的左右孩子和双亲都是数组下标。~然而这样非常难用,在需要遍历树的地方代码异常恶心~,同时哈夫曼树的一个性质是总结点数 = 叶子结点数 * 2 - 1,这样得到了开辟的存储树的数组大小。
    2. 其中用哈夫曼编码将原文件编码时,不能直接将编码(0101…)按1个char(即一个字节的大小)存1位编码来写入压缩文件,否则文件反而会变更大,而是用1个char的8位(即1byte中的8bits)来存8位的编码。在代码中有BitIO.h专门定义了做这些位运算的结构和函数,也有HuffmanTree.h中定义了Str2Byte函数,也有#define定义的GET_BYTE等函数。这三处功能是基本相同的,实现各有不同,这里我使用的是较简单的Str2Byte。

    代码的注释比较详细

    BitIO.h

    #ifndef HUFFMANCOMPRESSCPRO1_BITIO_H
    #define HUFFMANCOMPRESSCPRO1_BITIO_H
    
    #include <iostream>
    #define BITBUFFSIZE 1024
    #define SHIFT 3
    struct BIT{
        char b[BITBUFFSIZE];//位数组 bit数组
        int p; //指示数组填到哪一位的下一位
    };
    
    //向位数组栈顶推入一位
    bool pushBit(BIT *buffer, const bool istrue);
    
    //从文件加载多位
    int fPushBit(BIT* buffer, FILE* fp);
    
    //修改position位置的一位
    int changeBit(BIT* buffer, const int istrue, const int position);
    
    //读取一位
    int readBit(BIT* buffer, const int position);
    
    //栈顶弹出一位
    int popBit(BIT* buffer);
    
    #endif //HUFFMANCOMPRESSCPRO1_BITIO_H
    

    BitIO.cpp

    #include "BitIO.h"
    bool pushBit(BIT *buffer, const bool istrue){
        if(buffer->p >= BITBUFFSIZE * 8)
            return EOF;
        else if(istrue)
            buffer->b[buffer->p >> SHIFT] |= 128u >> buffer -> p % 8; //p所指位置填1
        else
            buffer->b[buffer->p >> SHIFT] &= ~(128u >> buffer -> p % 8); //p所指位置填0
        buffer->p++;
        return istrue;
    }
    int fPushBit(BIT* buffer, FILE* fp){
        memset(buffer, 0, sizeof(BIT));
        if(buffer -> p = fread(buffer->b, sizeof(char), BITBUFFSIZE, fp) && feof(fp)){
            buffer->p = (buffer->p - 2) * 8 + buffer -> b[buffer -> p - 1] + 1;
        } else
            buffer -> p *= 8;
        return buffer -> p;
    }
    int changeBit(BIT* buffer, const int istrue, const int position){
        if(position >= buffer -> p)
            return EOF;
        else if (istrue)
            buffer -> b[position >> SHIFT] |= 128u >> position % 8;
        else
            buffer -> b[position >> SHIFT] &= ~(128u >> position % 8);
        return istrue;
    }
    int readBit(BIT* buffer, const int position){
        if(position >= buffer -> p)
            return EOF;
        else
            return buffer->b[position >> SHIFT] & (128u >> position % 8);
    }
    int popBit(BIT* buffer){
        if(buffer -> p >= BITBUFFSIZE || buffer -> p < 0)
            return EOF;
        buffer->p--;
        return buffer->b[(buffer->p + 1) >> SHIFT] & (128u >> (buffer->p + 1) % 8);
    }
    

    HuffmanTree.h

    #ifndef HUFFMANCOMPRESSCPRO1_HUFFMANTREE_H
    #define HUFFMANCOMPRESSCPRO1_HUFFMANTREE_H
    #include <string>
    #include <iostream>
    #include "BitIO.h"
    #define SIZE 256
    #define NODES 2*SIZE - 1
    
    //各种各样的编码方法
    //取出index位,若取出的index位为0,则GET_BYTE值为假,否则为真
    #define GET_BYTE(vByte, index) (((vByte) & (1 << ((index) ^ 7))) != 0)
    //把index位设置为‘1’
    #define SET_BYTE(vbyte, index) ((vbyte) |= (1 << ((index) ^ 7)))
    //把index位设置为‘0’
    #define CLR_BYTE(vbyte, index) ((vbyte) &= (~(1 << ((index) ^ 7))))
    
    //n个叶子结点的哈夫曼树共有2n-1个结点
    //一个字节8位 读取文件的char可以从0-255 用weight[]数组记录每个char出现的频率
    //HuffmanTree 保存在HTNode[2n-1]的数组中
    struct Node{
        bool isLeaf();
        int ch = 0;
        int weight = 0;
        int lChild = 0, rChild = 0, parent = 0;
    };
    typedef Node HTNode, *HuffTree;
    
    struct HEAD{
        char type[4];
        int length;
        int weight[256];
    };
    
    void expand();
    void select(HuffTree HT, int end, int* s1, int* s2);
    void buildCode(std::string st[], Node x, std::string s, HuffTree HT);
    std::string* buildCode(Node root, HuffTree HT);
    void testBuildCode(std::string* st);
    void InitTrie(int *w, HuffTree& HT);
    void buildTrie(int* w, HuffTree& HT);
    void testBuildTrie(int *w, HuffTree HT);
    int InitHead(const char *Filename, HEAD& sHead);
    unsigned char Str2Byte(char* BinStr);
    void writeTrie(Node x, FILE* fpo, HuffTree& HT);
    void encode(FILE* fpi, FILE* fpo, std::string* st);
    void writeHead(FILE* fpo, HEAD& head);
    int Extract();
    
    #endif //HUFFMANCOMPRESSCPRO1_HUFFMANTREE_H
    
    

    HuffmanTree.cpp

    #include "HuffmanTree.h"
    //HT指向HuffmanTree end为保存树数组所需搜寻的末尾,s1,s2分别指向最小和次小结点在树数组中下标
    void select(HuffTree HT, int end, int* s1, int* s2){
        int min1, min2;
        int i = 0;
    
        while(HT[i].parent != 0 && i <= end){
            //找到第一个无双亲结点
            i++;
        }
    
        min1 = HT[i].weight;
        *s1 = i;
    
        i++;
        while(HT[i].parent != 0 && i <= end){
            //第二个无双亲结点
            i++;
        }
    
        if(HT[i].weight < min1){
            min2 = min1;
            min1 = HT[i].weight;
            *s2 = *s1;
            *s1 = i;
        }
        else{
            min2 = HT[i].weight;
            *s2 = i;
        }
    
        for(int j = i + 1; j <= end; j++){
            //两结点与后续无双亲结点比较
            if(HT[j].parent != 0){
                continue;
            }
            if(HT[j].weight < min1){
                //新结点小于min1
                min2 = min1;
                *s2 = *s1;
                min1 = HT[j].weight;
                *s1 = j;
            }
            else if(HT[j].weight >= min1 && HT[j].weight < min2){
                //新结点介于min1,min2 之间
                min2 = HT[j].weight;
                *s2 = j;
            }
        }
    }
    
    void InitTrie(int *w, HuffTree& HT){
        HT = (HuffTree) malloc(sizeof(HTNode) * NODES);
        for(int i = 0; i < SIZE; i++){
            //0-255 叶子结点
            HT[i].parent = 0;
            HT[i].rChild = 0;
            HT[i].lChild = 0;
            HT[i].weight = w[i];
            HT[i].ch = i;
        }
        for (int i = SIZE; i < NODES; i++){
            //256-510 内部结点
            HT[i].parent = 0;
            HT[i].lChild = 0;
            HT[i].rChild = 0;
            HT[i].weight = 0;
            HT[i].ch = 0;
        }
    }
    
    void buildTrie(int* w, HuffTree& HT){
        //每次搜寻两棵频率最小的树合并
        int s1, s2;
        for(int i = SIZE; i < NODES; i++){
            //从256开始填树结点,一直到把根结点510填满 NODES = 511
            select(HT, i - 1, &s1, &s2);
            HT[s1].parent = HT[s2].parent = i;
            HT[i].lChild = s1;
            HT[i].rChild = s2;
            HT[i].weight = HT[s1].weight + HT[s2].weight;
        }
    }
    
    void testBuildTrie(int *w, HuffTree HT){
        std::cout<<"字节ASCII "<<"频率"<<std::endl;
        //文件中出现的字节对应的ASCII(十六进制)和 出现的频率
        for(int i = 0; i < SIZE; i++){
            printf("0x%02X %d\n",i, w[i]);
        }
        //哈夫曼树中所有结点
        printf("结点下标\t频率\t双亲下标\t左孩子下标\t右孩子下标\n");
        for(int i = 0; i < NODES; i++){
            printf("HT[%d]\t%d\t%d  \t%d  \t\t%d\t%d\n", i, HT[i].weight, HT[i].parent, HT[i].lChild, HT[i].rChild,HT[i].ch);
        }
    }
    
    bool Node::isLeaf() {return lChild == 0 && rChild == 0;}
    
    void buildCode(std::string st[], Node x, std::string s, HuffTree HT){
        if(x.isLeaf()){
            st[x.ch] = s;
            return;
        }
        buildCode(st, HT[x.lChild], s + '0', HT);
        buildCode(st, HT[x.rChild], s + '1', HT);
    }
    
    std::string* buildCode(Node root, HuffTree HT){
        std::string st[SIZE];
        buildCode(st, root, "", HT);
        std::cout<<"HuffmanCode: "<<std::endl;
        std::cout<<"Bytes \t Codes"<<std::endl;
        for(int i= 0; i < SIZE; i++){
            printf("0x%02X :", i);
            printf("%s\n",st[i].c_str());
        }
        return st;
    }
    
    void testBuildCode(std::string* st){
        std::cout<<"HuffmanCode: "<<std::endl;
        std::cout<<"Bytes \t Codes"<<std::endl;
        for(int i= 0; i < SIZE; i++){
            printf("0x%02X :", i);
            printf("%s\n",(st+i)->c_str());
        }
    }
    
    int InitHead(const char *Filename, HEAD& sHead){
        //初始化文件头
        char* t = (char*)malloc(sizeof(char) * strlen(Filename));
        strcpy(t,const_cast<char*>(Filename));
        char* token = std::strtok(t, ".");
        std::string str[4];
        int it = 0;
        while(token != nullptr){
            str[it++] = token;
            token = strtok(NULL, ".");
        }
        char t2[8] = {'\0'};
        for(int k = 0; k < str[it - 1].size(); k++){
            t2[k] = str[it - 1].at(k);
        }
        strcpy(sHead.type, t2);
        sHead.length = 0;
        for(int i = 0; i < 256; i++){
            sHead.weight[i] = 0;
        }
    
        //以二进制流打开文件
        FILE* in = fopen(Filename, "rb");
        int ch;
        while((ch = fgetc(in)) != EOF){
            sHead.weight[ch]++;
            sHead.length++;//原文件长度多少字节
        }
        fclose(in);
        in = nullptr;
        return 1;
    }
    
    //将8位char变成一个char 即把 char数组 中的 char01 变成 一个char 中的 位01
    unsigned char Str2Byte(char* BinStr){
         unsigned char b = 0x00;
        for (int i = 0; i < 8; i++)
        {
            b = b << 1;
            if (BinStr[i] == '1')
            {
                b = b | 0x01;
            }
        }
        return b;
    }
    
    //可以将编码好的单词查找树写在文件开头,代价是文件变大, 也可以利用文件头(上述HEAD)中的weight数组在解压时重新构建树
    //按位写入查找树
    void writeTrie(Node x, FILE* fpo, HuffTree& HT){
        char ch;
        if(x.isLeaf()){
            bool t = true;
            fwrite(&t,sizeof(bool),1,fpo);
            ch = (char)x.ch;
            fwrite(&ch, sizeof(char), 1, fpo);
            return;
        }
        bool t = false;
        fwrite(&t, sizeof(bool), 1, fpo);
        writeTrie(HT[x.lChild], fpo, HT);
        writeTrie(HT[x.rChild], fpo, HT);
    }
    
    //原文件编码后写入压缩文件
    void encode(FILE* fpi, FILE* fpo, std::string* st){
        int ch;
        char cd[SIZE] ={0};
        int pos = 0;
        //unsigned char pBuffer[1000] = {0}; //debug
        if(!fpo){
            std::cerr<<"outFile opening failed"<<std::endl;
            exit(EXIT_FAILURE);
        }
        while((ch = fgetc(fpi)) != EOF){
            std::string code = st[ch];
            strcat(cd, code.c_str());
    
            while(strlen(cd) >= 8){
                unsigned char w = Str2Byte(cd);
                //pBuffer[pos++] = w;
                fwrite(&w, sizeof(char), 1, fpo);//写入文件
                for(int i = 0; i < SIZE - 8; i++){
                    //cd整体向左偏移8位
                    cd[i] = cd[i + 8];
                }
            }
        }
        //处理可能剩余不足8位
        if(strlen(cd) > 0){
            unsigned char w = Str2Byte(cd);
            fwrite(&w, sizeof(char), 1, fpo); //最后不足8位的位都为0
        }
    }
    
    void writeHead(FILE* fpo, HEAD& head){
        fwrite(&head, sizeof(head), 1, fpo);
    }
    
    int Extract(){
        std::cout<<"File to extract: ";
        char efile[256];
        std::cin>>efile;
        FILE* in = fopen(efile, "rb");
        if(!in){
            std::cerr<<"File opening failed"<< std::endl;
            return EXIT_FAILURE;
        }
        HEAD head;
        fread(&head, sizeof(HEAD), 1, in);
        char file[SIZE] = {'\0'};
        char* t = (char*)malloc(sizeof(char) * strlen(efile));
        strcpy(t, const_cast<char*>(efile));
        char* token = strtok(t, ".");
        strcpy(file, token);
        strcat(file, "_extracted.");
        strcat(file, head.type);
        FILE* out = fopen(file, "wb");
    
        fseek(in, 0L, SEEK_END);
        long filesize = ftell(in);
    
        HuffTree HT;
        InitTrie(head.weight, HT);
        buildTrie(head.weight, HT);
        std::string st[SIZE];
        buildCode(st,HT[NODES-1], "", HT);
    
        fseek(in, 1032, SEEK_SET);
        long curLoc = ftell(in);
    
        unsigned char outValue;
        int index = 0;
        int root = NODES - 1;
        unsigned char ch = fgetc(in);
        fseek(out, 0, SEEK_SET);
        while(true){
            if(HT[root].lChild == 0 && HT[root].rChild == 0){
                outValue = (char)HT[root].ch;
                fwrite(&outValue, sizeof(char), 1, out);
                if(curLoc >= filesize){
                    break;
                }
                root = NODES - 1;
            }
            if (!(ch & (1 << (index ^ 7)))) {
                root = HT[root].lChild;
            } else {
                root = HT[root].rChild;
            }
    
            if(++index >= 8){
                index = 0;
                ch = fgetc(in);
                curLoc = ftell(in);
            }
        }
    
        fclose(in);
        fclose(out);
        return 1;
    }
    

    Compress.h

    #ifndef HUFFMANCOMPRESSCPRO1_COMPRESS_H
    #define HUFFMANCOMPRESSCPRO1_COMPRESS_H
    
    void Compress(char* Filename);
    
    #endif //HUFFMANCOMPRESSCPRO1_COMPRESS_H
    

    Compress.cpp

    #include "Compress.h"
    #include "HuffmanTree.h"
    
    void Compress(char* Filename){
        int weight[SIZE] = {0};
        FILE* fin = fopen(Filename, "rb");
        if(!fin){
            std::cerr<<"File opening failed"<<std::endl;
            exit(EXIT_FAILURE);
        }
        int ch;
        while((ch = fgetc(fin)) != EOF){
            weight[ch]++;
        }
        fclose(fin);
    
        HuffTree HT;
        InitTrie(weight, HT);
        buildTrie(weight, HT);
        testBuildTrie(weight, HT);
    
        std::string st[SIZE];
        buildCode(st,HT[NODES-1], "", HT);
        std::cout<<"HuffmanCode: "<<std::endl;
        std::cout<<"Bytes \t Codes"<<std::endl;
        for(int i= 0; i < SIZE; i++){
            printf("0x%02X :", i);
            printf("%s\n",st[i].c_str());
        }
        //testBuildCode(str);
    //    std::cout<<"HuffmanCode: "<<std::endl;
    //    std::cout<<"Bytes \t Codes"<<std::endl;
    //    for(int i= 0; i < SIZE; i++){
    //        printf("0x%02X :", i);
    //        printf("%s\n",str[i].c_str());
    //    }
    
        HEAD head;
        InitHead(Filename, head);
    
        char filename[256] = {'\0'};
        strcpy(filename, Filename);
        strcat(filename, ".huf");
    
        FILE* out = fopen(filename, "wb");
        writeHead(out, head);
    
        fin = fopen(Filename, "rb");
        encode(fin, out, st);
    
        fclose(fin);
        fclose(out);
    
        Extract();
    }
    

    main.cpp

    #include <iostream>
    #include "HuffmanTree.h"
    #include "Compress.h"
    using namespace std;
    int main() {
        cout<<"==== Huffman Compress & Extract ===="<<endl;
        cout<<"filename: ";
        char filename[SIZE];
        cin>>filename;
        Compress(filename);//解压函数也在这里运行了
        return 0;
    }
    
    
    展开全文
  • 参考Crash Course的课程,做下笔记,原视频在这里 ↓ ... 我们要对如下一张 4像素 X 4像素的 图片进行压缩, 而在磁盘中图片是一串像素值的形式...为了能够压缩图片,我们需要减少冗余的信息或者用更紧凑的表示方...

    参考Crash Course的课程,做下笔记,原视频在这里 ↓

    https://www.bilibili.com/video/BV1EW411u7th?p=21

    1. 我们要对如下一张 4像素 X 4像素的 图片进行压缩,
      在这里插入图片描述
      而在磁盘中图片是一串像素值的形式存储的,每个像素的颜色由RGB确定,这样一张图片需要 48(16*3) 个字节
      在这里插入图片描述
    2. 为了能够压缩图片,我们需要减少冗余的信息或者用更紧凑的表示方法。可以发现,有很多相同的排列:白黄、黑黄、黄黄、白白,这个序列可以有这四种排列组成(当然也有其他不同的方式),我们为这四种排列生成紧凑代码,用更少的字节表示每对排列

    在这里插入图片描述

    1. 我们会发现,这四对出现的频率并不相同
      在这里插入图片描述
      黄黄出现的次数最多,所以我们希望通过最紧凑的方式来表示,其次是白黄,黑黄和白白出现的次数最少,我们可以用长一点的来表示

    2. 为了实现以上的表示,我们需要构造哈夫曼树

      • 列出所有的块和频率,每轮选择两个最低的频率,将它们组成一个树。这里BY和WW频率最低,将其组成一个树,组成后的频率为2,这样就完成了一轮算法。
        在这里插入图片描述
      1. 下一轮中重复这样的操作。现在白色的两个频率最低,合并!
        在这里插入图片描述
        合并之后的情况如下
        在这里插入图片描述
      2. 第三轮同理
        在这里插入图片描述
        这样我们就完成了哈夫曼树,它是按照频率排序的,频率低的在下面,频率高的在上
    3. 完成了哈夫曼树,我们还需要生成字典,即如何访问各个节点。我们可以将所有的左子树的分支用0标示,右子树用1标示
      在这里插入图片描述
      这样我们就完成了字典
      在这里插入图片描述
      这样我们可以用0 标示YY,111标示 WW…
      经过这样的压缩后,原本的字符可以表示为如下的形式
      在这里插入图片描述
      这样原来的48字节我们用14位就能表示了!!! (48字节=48 X 8位 = 384 位)

    4. 当然,只保存14位的数据是没有意义的,我们需要将字典也保存下来才能知道表示的信息
      在这里插入图片描述
      加上字典信息后我们需要30字节的空间,仍然比48字节好很多。

    展开全文
  • 哈夫曼编码压缩和解压文件的Java实现 上一次已经介绍了如何用Huffman树实现文件的压缩及其原理,那么今天我们试着真正运用它实现文件的压缩与解压 前戏 我们先来整理一下思路 首先我们拿到一个文件,看起来是一串串...

    哈夫曼编码压缩和解压文件的Java实现

    上一次已经介绍了如何用Huffman树实现文件的压缩及其原理,那么今天我们试着真正运用它实现文件的压缩与解压

    前戏

    我们先来整理一下思路

    首先我们拿到一个文件,看起来是一串串字符/音频/图片/视频,实际上它是一堆01串。

    我们对这个01串所表示的字符统计词频,用新的01串来表示它,可能原来每个字符要用到8个bit,现在有些字符出现频率高的字符只要一两个bit,而有些出现频率少的字符在新的表示中对应了几十个bit,这也就是Huffman编码的过程,这里我们得到了两个东西,一个是字符与01串的对应关系,我们把它用键值对的形式存储在Hashmap中,另一个是用Huffman编码后的文件(一长串01)。这些都是上次博客中已经实现的部分。

    现在考虑把上面得到的两个东西写入一个.zip文件,然后再把这个.zip文件转换成一个正常文件实现解压,本文中以txt为例。

    由于这篇博客是用Java实现的,而Java不能直接对bit进行操作(事实上任意一种高级编程语言都不能直接操作bit),Java操作的最小单位是byte,但是我们上一段得到的那个代表压缩后数据的01串如果不能被8整除的话,是无法直接转成byte数组的(一个byte由8个bit组成,也就是8个01)。所以这里把这串01串后面用0补齐,补到8的倍数个,并且记这个数字为number_of_zeronumber\_of\_zero。由于之后我们从.zip文件里面读取信息的时候要区分代表键值对的部分和代表原文件数据的部分,所以我们这里引进一个int型变量head_lengthhead\_length,用来表示键值对部分的长度。为了方便,把这四个东西打包成一个ZipResult对象。

    得到这些以后,我们把它们写入.zip文件,接下来从.zip中读取数据,并解码成一个根原文件一样的文件。

    读取到了ZipResult对象中的四个东西,再根据上述描述,反过来操作,可以把它们整理成两个部分,一个Hashmap表示解码的码表,一个01串表示原文件数据,再用码=码表反解码数据得到解压后的文件。

    再简单提一提Java的文件读写

    Java的文件读写是java.io中的FileInputStream和FileOutputStream实现的。通过创建流,提供了读取、写入、刷新、关闭等方法其中读取是读取到的字节数组,写入也是写入的字节数组。

    正文

    要用到的类

    import java.util.*;
    import java.io.*;
    
    //创建ZipResult类
    class ZipResult{
        int head_length;
        int number_of_zero;
        byte[] head;
        byte[] data;
        public ZipResult(int head_length, int number_of_zero, byte[] head, byte[] data){
            this.head_length = head_length;
            this.number_of_zero = number_of_zero;
            this.head = head;
            this.data = data;
        }
    }
    
    //为了让Huffman节点之间可比大小,需要实现compareTo方法
    class HTreeNode implements Comparable<HTreeNode>{
        Integer count;
        char c;
        String code = "";
        HTreeNode left;
        HTreeNode right;
        HTreeNode parent;
        public HTreeNode(int count){
            this.count = count;
        }
        public HTreeNode(int count,char c){
            this.count = count;
            this.c = c;
        }
        @Override
        public int compareTo(HTreeNode o) {
            return this.count.compareTo(o.count);
        }
    }
    

    Huffman树节点类的主要方法

    统计词频

    输入一个字符串,这个方法可以统计每一个字符的频率,返回词频表

    private static Map<Character,Integer> transferString(String s){
            char[] cl = new char[s.length()];
            int[] nl = new int[s.length()];
            ArrayList<Character> list = new ArrayList<>();
            char[] chars = s.toCharArray();//将字符串转化成字符数组
            for (int i = 0; i < chars.length; i++) {
                char aChar = chars[i];
                list.add(aChar);//将字符数组元素添加到集合中
            }
            for (int i = 0; i < list.size(); i++) {//遍历集合取出每个字符
                int count = 0;//定义计数器
                Character character = list.get(i);
                for (int j = 0; j < chars.length; j++) {//遍历数组取出每个字符和集合中的元素比较
                    char aChar = chars[j];
                    if (character.equals(aChar)){//如果集合中的元素有等于数组中的字符,计数器加1
                        count++;
                    }
                }
                cl[i] = character;
                nl[i] = count;
            }
            Character[] ncl = new Character[cl.length];
            for(int i=0;i<cl.length;i++){
                ncl[i] = (Character)cl[i];
            }
            Map<Character,Integer> map = new HashMap<Character,Integer>();
            for(int i=0;i<ncl.length;i++){
                map.put(ncl[i],nl[i]);
            }
            return map;
    
        }
    

    用优先队列构建Huffman树

    根据上面那个词频表,创建一个优先队列,并且迭代更新

    private static Queue<HTreeNode> init(Map<Character,Integer> map){
        Set<Character> s = map.keySet();
        Character[] cl = new Character[s.size()];
        cl =  s.toArray(cl);
        Queue<HTreeNode> q = new PriorityQueue<HTreeNode>();
        for(int i=0;i<map.size();i++){
            HTreeNode h = new HTreeNode((int)map.get(cl[i]),(char)cl[i]);
            q.add(h);
        }
        return q;
    }
    
    private static void update(Queue<HTreeNode> q){
      
            HTreeNode a = q.poll();
            HTreeNode b = q.poll();
            HTreeNode c = new HTreeNode(a.count+b.count);
            c.left  = a;
            c.right = b;
            a.parent = c;
            b.parent = c;
            q.add(c);
    
     }
    private static void countTreeCode(HTreeNode t){
    
            if(t.left!=null){
                t.left.code += t.code+"0";
                countTreeCode(t.left);
            }
    
            if(t.right!=null){
                t.right.code += t.code+"1";
                countTreeCode(t.right);
            }
    }
    

    Huffman编码

    从Huffman树得到码表,然后对原文件中的数据进行压缩,得到01串,再把这个01串转码成字节数组的格式,好写进.zip文件。还有我们的map部分,要转化成字符串储存到.zip文件里。

    private static Map<Character,String> coding(HTreeNode t){
        Map<Character,String> map = new HashMap<Character,String>();
        if(t.c!='\0'){
            if(t.c=='\t'){
                System.out.println("\\t"+" 的出现频率为"+t.count+" Huffman编码为:"+t.code);
                map.put(t.c, t.code);
            }else if(t.c=='\r'){
                System.out.println("\\r"+" 的出现频率为"+t.count+" Huffman编码为:"+t.code);
                map.put(t.c, t.code);
            }else if(t.c=='\n'){
                System.out.println("\\n"+" 的出现频率为"+t.count+" Huffman编码为:"+t.code);
                map.put(t.c, t.code);
            }else {
                System.out.println(t.c + " 的出现频率为" + t.count + " Huffman编码为:" + t.code);
                map.put(t.c, t.code);
            }
        }
        if (t.left!=null){
            map.putAll(coding(t.left));
        }
    
        if (t.right!=null){
            map.putAll(coding(t.right));
        }
        return map;
    }
    
    private static String String2HFMcode(String s,Map<Character,String> map){
            char[] cl = s.toCharArray();
            String[] vl = new String[cl.length];
            for(int i=0;i<cl.length;i++){
                try {
                    vl[i] = map.get(cl[i]);
                }catch (NullPointerException e){
                    e.printStackTrace();
                }
            }
            for(int i=1;i<vl.length;i++){
                vl[0] += vl[i];
            }
            return vl[0];
    }
    
    private static byte[] binaryStringToBytes(String str) {
            ByteArrayOutputStream baos = new ByteArrayOutputStream();
            int curByte = 0;
            int i, bc = 0;
            for (i = 0; i < str.length(); i++) {
                int bit;
                char charAt = str.charAt(i);
                if (charAt == '1')
                    bit = 1;
                else if (charAt == '0')
                    bit = 0;
                else
                    continue;
                curByte |= bit << (7 - bc % 8);
                if (bc % 8 == 7) {
                    baos.write(curByte);
                    curByte = 0;
                }
                bc++;
            }
            if (bc % 8 != 0)
                baos.write(curByte);
            try {
                baos.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return baos.toByteArray();
    }
    
    private static String Map2mapString(Map<Character,String> map){
            Character[] ca = new Character[map.size()];
            ca =  map.keySet().toArray(ca);
            String[] sa = new String[map.size()];
            for(int i=0;i<ca.length;i++){
                try {
                  	//注意!下面这里等号的后面有一个空格
                    sa[i] = ca[i] + "= " + map.get(ca[i]);
                }catch (NullPointerException e){
                    e.printStackTrace();
                }
            }
            for(int i=1;i<sa.length;i++){
              	//这里为啥用“,@,”
                sa[0] += ",@,"+sa[i];
            }
            return sa[0];
     }
    

    回答上面代码中的问题: 其实一开始我用的是一个逗号做的分隔,但是后来发现,如果只用逗号的话,会出现这样的情况“,=10110”,这种就是表示在原文件里读到了逗号,并且它的Huffman编码是10110,如果这样,用我下面那种解压的方法就会出问题,我下面那种方法是取split以后的数组的第一项和第二项作为键和值,如果按这种方法,遇到了这种问题,就会出现上述第一个逗号被split吞掉,返回一个键和值均为空字符串的键值对,所以就会报错,而第二个逗号split以后会变成一个键为空,值为10110的键值对,一样会报错。所以这里采用“,@,”,因为不会出现“,@,”作为键的情况。上面一个地方那里用的是”“= ”而不是“=”,原因是一样的,否则当我们压缩的文件里面有等号这个字符串的话就会报错。

    文件压缩

    文件压缩的过程

    //压缩的过程
    public static ZipResult zip(String s){
            Map<Character,Integer> char_intmap = transferString(s);
            Queue<HTreeNode> q = init(char_intmap);
            while (q.size()>1){
                update(q);
            }
            HTreeNode t = q.poll();
            countTreeCode(t);
            //创建码表
            Map<Character,String> map = coding(t);
            //压缩文件
            String HFMcode = String2HFMcode(s, map);
            int number_of_zero = 0;
            if(HFMcode.length()%8!=0){
                number_of_zero = 8 - HFMcode.length()%8;
                HFMcode = HFMcode+"0".repeat(number_of_zero);
            }
    
            byte[] head = Map2mapString(map).getBytes();
            byte[] data = binaryStringToBytes(HFMcode);
            int head_length = head.length;
            return new ZipResult(head_length,number_of_zero,head,data);
    }
    

    解压预备

    从读取到的byte数组中,得到01串。根据读取到的字符串,得到解码的码表,根据这两个东西把文件解压

    private static String Bytes2binaryString(byte[] bl){
        ByteArrayInputStream bais = new ByteArrayInputStream(bl);
        String [] sa = new String[bl.length];
        for(int i=0;i<bl.length;i++){
            String s = Integer.toBinaryString(bais.read());
            int delta = 8-s.length();
            s = "0".repeat(delta) + s;
            sa[i] = s;
            if(i!=0) {
                sa[0] += sa[i];
            }
        }
        return sa[0];
    }
    
    public static Map<String,Character> mapStringToMap(String str){
      	//呐,这里的“,@,”对应上面的
        String[] strs=str.split(",@,");
        Map<String,Character> map = new HashMap<String, Character>();
    
        for (String string:strs){
          //这里的“= ”对应上面的
            String key   = string.split("= ")[1];
            Character value = string.split("= ")[0].charAt(0);
            map.put(key,value);
        }
        return map;
    }
    

    文件解压

    public static byte[] unzip(ZipResult zipresult){
    
        byte[] head = zipresult.head;
        byte[] data = zipresult.data;
        int number_of_zero = zipresult.number_of_zero;
    
    
        //取到解码表
        String mapstring = new String(head);
        Map<String, Character> enmap = mapStringToMap(mapstring);
    
    
        //取到01串
        String HFMcode_with_zero = Bytes2binaryString(data);
        //System.out.println(HFMcode_with_zero);
        //System.out.println(number_of_zero);
        String HFMcode = HFMcode_with_zero.substring(0,HFMcode_with_zero.length()-number_of_zero);
        String str = "";
        String content ="";
        for(int i=0;i<HFMcode.length();i++){
            str += HFMcode.charAt(i);
            if(enmap.containsKey(str)){
                content += enmap.get(str);
                str = "";
            }
        }
    
        byte[] result = content.getBytes();
        return result;
    
    }
    

    文件层面的操作

    读取正常文件

    public static String ReadFile(String path){
    
        try {
            //读取指定路径的文件
            FileInputStream ips = new FileInputStream(path);
            //把文件写进字节数组
            byte[] buffer = ips.readAllBytes();
            String content = new String(buffer);
            ips.close();
    
            return content;
    
        } catch (FileNotFoundException e) {
            e.printStackTrace();
            System.out.println("指定路径不存在");
        } catch (IOException e) {
            e.printStackTrace();
            System.out.println("读取文件失败");
        }
    
        return null;
    
    }
    

    创建压缩文件

    public static void CreateZipFile(ZipResult zipresult,String path){
        try {
            FileOutputStream ops = new FileOutputStream(path);
            int head_length = zipresult.head_length;
            int number_of_zero = zipresult.number_of_zero;
            byte[] head = zipresult.head;
            byte[] data = zipresult.data;
            ops.write((Integer.toString(head_length)+"\r\n").getBytes());
            ops.flush();
            ops.write((Integer.toString(number_of_zero)+"\r\n").getBytes());
            ops.flush();
            ops.write(head);
            ops.flush();
            ops.write(data);
            ops.flush();
            ops.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
            System.out.println("创建路径失败");
        } catch (IOException e) {
            e.printStackTrace();
            System.out.println("写入失败");
        }
    
    }
    

    读取压缩文件

    public static ZipResult ReadZipFile(String path) {
            if (path.contains(".myzip")) {
    
                try {
                    //读取指定路径的文件
                    FileInputStream ips = new FileInputStream(path);
                    //把文件写进字节数组
                    byte[] whole = ips.readAllBytes();
                    String content = new String(whole);
                    String[] sa = content.split("\r\n");
                    int head_length = Integer.parseInt(sa[0]);
                    int number_of_zero = Integer.parseInt(sa[1]);
                    String s = sa[0] + "\r\n" + sa[1] + "\r\n";
    
                    byte[] head = Arrays.copyOfRange(whole, s.length(), s.length() + head_length);
                  	//!!!!!!这里一定要注意
                    byte[] data = Arrays.copyOfRange(whole, s.length() + head_length, whole.length);
                    ips.close();
    
                    return new ZipResult(head_length, number_of_zero, head, data);
    
                } catch (FileNotFoundException e) {
                    e.printStackTrace();
                    System.out.println("指定路径不存在");
                } catch (IOException e) {
                    e.printStackTrace();
                    System.out.println("读取文件失败");
                }
    
                return null;
    
            }else {
                System.out.println("只有后缀名为.myzip的文件才可以被解压");
                return null;
            }
     }
    

    ps:这里没用.zip是因为这个是标准的压缩文件后缀名,咱们自己弄着玩玩嘛,就取一个后缀名为.myzip就好了

    上面代码中那个要注意的地方,是数组切片生成data的最后的那个参数,应该是whole.lengthwhole.length而不应该是content.lengthcontent.length()。按道理来说,两者应该是一样的,但是其实不一样。事实上在文件文本全是英文的情况下是一样的,因为一个英文对应一个字符,但是当你的文件中出现中文时,你要知道,一个中午呢是占两个字符的,所以字节数组读出来的前者,要比后者的长度大,其差值就是中文字符的个数

    创建正常文件

    public static void CreateFile(byte[] buffer,String path){
        try {
            FileOutputStream ops = new FileOutputStream(path);
            ops.write(buffer);
            ops.flush();
            ops.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
            System.out.println("创建路径失败");
        } catch (IOException e) {
            e.printStackTrace();
            System.out.println("写入失败");
        }
    
    }
    

    三个打包的方法

    //压缩
    private static void ZIP(String inputpath,String outputpath){
        String content = ReadFile(inputpath);
        ZipResult zipresult = HFMtree.zip(content);
        CreateZipFile(zipresult,outputpath);
    }
    //解压
    private static void UNZIP(String inputpath,String outputpath){
        ZipResult zipresult = ReadZipFile(inputpath);
        byte[] buffer = HFMtree.unzip(zipresult);
        CreateFile(buffer,outputpath);
    }
    
    public static void main(String[] args){
        ZIP("D:\\javacode\\src\\数据结构\\input.txt","D:\\javacode\\src\\数据结构\\zip.myzip");
        UNZIP("D:\\javacode\\src\\数据结构\\zip.myzip","D:\\javacode\\src\\数据结构\\output.txt");
    }
    

    一个容易遇到的问题

    写Huffman压缩文件时最容易遇到的问题就是,有的时候你会惊人地发现,经过Huffman压缩后的压缩文件居然要比原文件还大。

    这个大概率是因为你的data部分是直接用01字符串存储的(直接把01字符串getBytes()getBytes()),或者你是用的Arrays.toString()Arrays.toString()方法,把字节数组转化成字符串存储(Arrays.toString()Arrays.toString()以后再getBytes()getBytes()写入)。这种情况,你打开你的.zip,就会发现你的这个文件几乎没有乱码,全都是你看得懂的,根据你以前玩电脑的经验,这里边一定有问题。其实是你用字符串形式存储这些的话,所占内存并没有怎么减少,而且Arrays.toString()Arrays.toString()这个方法还会帮你生成很多不必要的空格,这都会使得你的.zip文件很大。正确的方法是像上面那样直接用byte写入。这样你得到的.zip文件你直接用UTF-8打开应该data部分全是乱码(但是head部分可以不是,我这里也是用字符串形式存储的,方便调试,事实上这个也可以直接byte写进去)

    大家来看一看正常的zip文件的画风

    Java源码

    package 数据结构;
    
    import java.util.*;
    import java.io.*;
    
    class ZipResult{
        int head_length;
        int number_of_zero;
        byte[] head;
        byte[] data;
        public ZipResult(int head_length, int number_of_zero, byte[] head, byte[] data){
            this.head_length = head_length;
            this.number_of_zero = number_of_zero;
            this.head = head;
            this.data = data;
        }
    }
    
    class HTreeNode implements Comparable<HTreeNode>{
        Integer count;
        char c;
        String code = "";
    
        HTreeNode left;
        HTreeNode right;
        HTreeNode parent;
    
        public HTreeNode(int count){
            this.count = count;
        }
        public HTreeNode(int count,char c){
            this.count = count;
            this.c = c;
        }
    
        @Override
        public int compareTo(HTreeNode o) {
            return this.count.compareTo(o.count);
        }
    
    
    }
    
    class HFMtree {
    
        private static Map<Character,Integer> transferString(String s){
            char[] cl = new char[s.length()];
            int[] nl = new int[s.length()];
            ArrayList<Character> list = new ArrayList<>();
            char[] chars = s.toCharArray();//将字符串转化成字符数组
            for (int i = 0; i < chars.length; i++) {
                char aChar = chars[i];
                list.add(aChar);//将字符数组元素添加到集合中
            }
            for (int i = 0; i < list.size(); i++) {//遍历集合取出每个字符
                int count = 0;//定义计数器
                Character character = list.get(i);
                for (int j = 0; j < chars.length; j++) {//遍历数组取出每个字符和集合中的元素比较
                    char aChar = chars[j];
                    if (character.equals(aChar)){//如果集合中的元素有等于数组中的字符,计数器加1
                        count++;
                    }
                }
                cl[i] = character;
                nl[i] = count;
            }
            Character[] ncl = new Character[cl.length];
            for(int i=0;i<cl.length;i++){
                ncl[i] = (Character)cl[i];
            }
            Map<Character,Integer> map = new HashMap<Character,Integer>();
            for(int i=0;i<ncl.length;i++){
                map.put(ncl[i],nl[i]);
            }
            return map;
    
        }
    
        private static Queue<HTreeNode> init(Map<Character,Integer> map){
            Set<Character> s = map.keySet();
            Character[] cl = new Character[s.size()];
            cl =  s.toArray(cl);
            Queue<HTreeNode> q = new PriorityQueue<HTreeNode>();
            for(int i=0;i<map.size();i++){
                HTreeNode h = new HTreeNode((int)map.get(cl[i]),(char)cl[i]);
                q.add(h);
            }
            return q;
        }
    
        private static void update(Queue<HTreeNode> q){
            HTreeNode a = q.poll();
            HTreeNode b = q.poll();
            HTreeNode c = new HTreeNode(a.count+b.count);
            c.left  = a;
            c.right = b;
            a.parent = c;
            b.parent = c;
            q.add(c);
    
        }
    
        private static void countTreeCode(HTreeNode t){
    
            if(t.left!=null){
                t.left.code += t.code+"0";
                countTreeCode(t.left);
            }
    
            if(t.right!=null){
                t.right.code += t.code+"1";
                countTreeCode(t.right);
            }
    
    
        }
    
        private static Map<Character,String> coding(HTreeNode t){
    
            Map<Character,String> map = new HashMap<Character,String>();
            if(t.c!='\0'){
                if(t.c=='\t'){
                    System.out.println("\\t"+" 的出现频率为"+t.count+" Huffman编码为:"+t.code);
                    map.put(t.c, t.code);
                }else if(t.c=='\r'){
                    System.out.println("\\r"+" 的出现频率为"+t.count+" Huffman编码为:"+t.code);
                    map.put(t.c, t.code);
                }else if(t.c=='\n'){
                    System.out.println("\\n"+" 的出现频率为"+t.count+" Huffman编码为:"+t.code);
                    map.put(t.c, t.code);
                }else {
                    System.out.println(t.c + " 的出现频率为" + t.count + " Huffman编码为:" + t.code);
                    map.put(t.c, t.code);
                }
            }
    
            if (t.left!=null){
                map.putAll(coding(t.left));
            }
    
            if (t.right!=null){
                map.putAll(coding(t.right));
            }
            return map;
        }
    /*
        private static Map<String,Character> encoding(HTreeNode t){
    
            Map<String,Character> enmap = new HashMap<String,Character>();
            if(t.c!='\0'){
                enmap.put(t.code,t.c);
            }
    
            if (t.left!=null){
                enmap.putAll(encoding(t.left));
            }
    
            if (t.right!=null){
                enmap.putAll(encoding(t.right));
            }
            return enmap;
        }
    */
        private static String String2HFMcode(String s,Map<Character,String> map){
            //System.out.print(map.keySet().toString());
            char[] cl = s.toCharArray();
            //System.out.println(s);
            String[] vl = new String[cl.length];
            for(int i=0;i<cl.length;i++){
                //System.out.print((int)cl[i]);
                try {
                    vl[i] = map.get(cl[i]);
                    //System.out.println(" "+vl[i]);
                }catch (NullPointerException e){
                    e.printStackTrace();
                }
            }
            for(int i=1;i<vl.length;i++){
                vl[0] += vl[i];
                //System.out.println(vl[0]);
            }
            return vl[0];
        }
    
        private static byte[] binaryStringToBytes(String str) {
            ByteArrayOutputStream baos = new ByteArrayOutputStream();
            int curByte = 0;
            int i, bc = 0;
            for (i = 0; i < str.length(); i++) {
                int bit;
                char charAt = str.charAt(i);
                if (charAt == '1')
                    bit = 1;
                else if (charAt == '0')
                    bit = 0;
                else
                    continue;
                curByte |= bit << (7 - bc % 8);
                if (bc % 8 == 7) {
                    baos.write(curByte);
                    curByte = 0;
                }
                bc++;
            }
            if (bc % 8 != 0)
                baos.write(curByte);
            try {
                baos.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
            //System.out.println(Arrays.toString(baos.toByteArray()));
            return baos.toByteArray();
    
        }
    
        private static String Map2mapString(Map<Character,String> map){
            Character[] ca = new Character[map.size()];
            ca =  map.keySet().toArray(ca);
            //System.out.println(s);
            String[] sa = new String[map.size()];
            for(int i=0;i<ca.length;i++){
                //System.out.print((int)cl[i]);
                try {
                    sa[i] = ca[i] + "= " + map.get(ca[i]);
                    //System.out.println(" "+vl[i]);
                }catch (NullPointerException e){
                    e.printStackTrace();
                }
            }
            for(int i=1;i<sa.length;i++){
                sa[0] += ",@,"+sa[i];
                //System.out.println(vl[0]);
            }
            return sa[0];
        }
    
        private static String Bytes2binaryString(byte[] bl){
            ByteArrayInputStream bais = new ByteArrayInputStream(bl);
            String [] sa = new String[bl.length];
            for(int i=0;i<bl.length;i++){
                String s = Integer.toBinaryString(bais.read());
                int delta = 8-s.length();
                s = "0".repeat(delta) + s;
                sa[i] = s;
                if(i!=0) {
                    sa[0] += sa[i];
                }
            }
            //System.out.println(sa[0]);
            return sa[0];
        }
    
        public static Map<String,Character> mapStringToMap(String str){
            //str = str.substring(1, str.length()-1);
            String[] strs=str.split(",@,");
            Map<String,Character> map = new HashMap<String, Character>();
    
            for (String string:strs){
                //System.out.println(string);
                String key   = string.split("= ")[1];
                Character value = string.split("= ")[0].charAt(0);
                map.put(key,value);
            }
            return map;
        }
    
        public static ZipResult zip(String s){
            Map<Character,Integer> char_intmap = transferString(s);
            Queue<HTreeNode> q = init(char_intmap);
            while (q.size()>1){
                update(q);
            }
            HTreeNode t = q.poll();
            countTreeCode(t);
            //创建码表
            Map<Character,String> map = coding(t);
            //压缩文件
            //System.out.println(s);
            String HFMcode = String2HFMcode(s, map);
            int number_of_zero = 0;
            if(HFMcode.length()%8!=0){
                number_of_zero = 8 - HFMcode.length()%8;
                HFMcode = HFMcode+"0".repeat(number_of_zero);
            }
    
            byte[] head = Map2mapString(map).getBytes();
            byte[] data = binaryStringToBytes(HFMcode);
            //System.out.println(Arrays.toString(data));
            //System.out.println(HFMcode);
            int head_length = head.length;
            return new ZipResult(head_length,number_of_zero,head,data);
    
        }
    
        public static byte[] unzip(ZipResult zipresult){
    
            byte[] head = zipresult.head;
            byte[] data = zipresult.data;
            //System.out.println(Arrays.toString(data));
            int number_of_zero = zipresult.number_of_zero;
    
    
            //取到解码表
            String mapstring = new String(head);
            Map<String, Character> enmap = mapStringToMap(mapstring);
    
    
            //取到01串
            String HFMcode_with_zero = Bytes2binaryString(data);
            //System.out.println(HFMcode_with_zero);
            //System.out.println(number_of_zero);
            String HFMcode = HFMcode_with_zero.substring(0,HFMcode_with_zero.length()-number_of_zero);
            /*String[] sa = content.split(", ");
            byte[] ba = new byte[sa.length];
            for(int i=0;i<ba.length;i++){
                ba[i] = (byte)Integer.parseInt(sa[i]);
            }
    
            //System.out.println(Arrays.toString(sa));
            //System.out.println(Arrays.toString(ba));
            String s_with_0 = Bytes2binaryString(ba);
            String s = s_with_0.substring(0,s_with_0.length()-number_of_zero);
            //System.out.println(s);
            */
    
    
            String str = "";
            String content ="";
            for(int i=0;i<HFMcode.length();i++){
                str += HFMcode.charAt(i);
                if(enmap.containsKey(str)){
                    content += enmap.get(str);
                    str = "";
                }
            }
    
            byte[] result = content.getBytes();
    
            //System.out.println(content);
            return result;
    
        }
    
    }
    
    
    public class HFM {
    
        public static String ReadFile(String path){
    
            try {
                //读取指定路径的文件
                FileInputStream ips = new FileInputStream(path);
                //把文件写进字节数组
                byte[] buffer = ips.readAllBytes();
                String content = new String(buffer);
                ips.close();
    
                return content;
    
            } catch (FileNotFoundException e) {
                e.printStackTrace();
                System.out.println("指定路径不存在");
            } catch (IOException e) {
                e.printStackTrace();
                System.out.println("读取文件失败");
            }
    
            return null;
    
        }
    
    
        public static void CreateZipFile(ZipResult zipresult,String path){
            try {
                FileOutputStream ops = new FileOutputStream(path);
                int head_length = zipresult.head_length;
                int number_of_zero = zipresult.number_of_zero;
                byte[] head = zipresult.head;
                byte[] data = zipresult.data;
                ops.write((Integer.toString(head_length)+"\r\n").getBytes());
                ops.flush();
                ops.write((Integer.toString(number_of_zero)+"\r\n").getBytes());
                ops.flush();
                ops.write(head);
                ops.flush();
                ops.write(data);
                ops.flush();
                ops.close();
            } catch (FileNotFoundException e) {
                e.printStackTrace();
                System.out.println("创建路径失败");
            } catch (IOException e) {
                e.printStackTrace();
                System.out.println("写入失败");
            }
    
        }
        public static ZipResult ReadZipFile(String path) {
            if (path.contains(".myzip")) {
    
                try {
                    //读取指定路径的文件
                    FileInputStream ips = new FileInputStream(path);
                    //把文件写进字节数组
                    byte[] whole = ips.readAllBytes();
                    //System.out.println(whole.length);
                    String content = new String(whole);
                    //System.out.println(content.length());
                    String[] sa = content.split("\r\n");
                    int head_length = Integer.parseInt(sa[0]);
                    int number_of_zero = Integer.parseInt(sa[1]);
                    String s = sa[0] + "\r\n" + sa[1] + "\r\n";
    
    
                    byte[] head = Arrays.copyOfRange(whole, s.length(), s.length() + head_length);
                    byte[] data = Arrays.copyOfRange(whole, s.length() + head_length, whole.length);
                    //System.out.println(Arrays.toString(data));
                    ips.close();
    
                    return new ZipResult(head_length, number_of_zero, head, data);
    
                } catch (FileNotFoundException e) {
                    e.printStackTrace();
                    System.out.println("指定路径不存在");
                } catch (IOException e) {
                    e.printStackTrace();
                    System.out.println("读取文件失败");
                }
    
                return null;
    
            }else {
                System.out.println("只有后缀名为.myzip的文件才可以被解压");
                return null;
            }
        }
    
        public static void CreateFile(byte[] buffer,String path){
            try {
                FileOutputStream ops = new FileOutputStream(path);
                ops.write(buffer);
                ops.flush();
                ops.close();
            } catch (FileNotFoundException e) {
                e.printStackTrace();
                System.out.println("创建路径失败");
            } catch (IOException e) {
                e.printStackTrace();
                System.out.println("写入失败");
            }
    
        }
    
        //压缩
        private static void ZIP(String inputpath,String outputpath){
            String content = ReadFile(inputpath);
            ZipResult zipresult = HFMtree.zip(content);
            CreateZipFile(zipresult,outputpath);
        }
        //解压
        private static void UNZIP(String inputpath,String outputpath){
            ZipResult zipresult = ReadZipFile(inputpath);
            byte[] buffer = HFMtree.unzip(zipresult);
            CreateFile(buffer,outputpath);
        }
    
        public static void main(String[] args){
            ZIP("D:\\javacode\\src\\数据结构\\input.txt","D:\\javacode\\src\\数据结构\\zip.myzip");
            UNZIP("D:\\javacode\\src\\数据结构\\zip.myzip","D:\\javacode\\src\\数据结构\\output.txt");
        }
    }
    
    
    

    看看,代码里不知道有多少个//System.out.println();//System.out.println();,每一个都是一次崩溃,哭哭,不过最后还是Processfinishedwithexitcode0Process finished with exit code 0了,开心!!!终于可以出门喝茶颜辽!
    加倍开心!

    展开全文
  • 哈夫曼树和哈夫曼编码应用之图片压缩编码c++实现

    千次阅读 多人点赞 2018-12-07 22:38:04
    因此今天我就分享给大家c语言数据结构有关哈夫曼压缩图片的项目实现。   一:下面先介绍有关的知识: 1.背景 压缩软件是用特定算法压缩数据的工具,压缩后的文件称为压缩包,可以对其进行解压。那么为什么要...

    本人正在学习数据结构,在前几天做了压缩图片的项目,感觉到有必要分享给大家。因此今天我就分享给大家c语言数据结构有关哈夫曼树压缩图片的项目实现。

     

    一:下面先介绍有关的知识:
    1.背景

    压缩软件是用特定算法压缩数据的工具,压缩后的文件称为压缩包,可以对其进行解压。那么为什么要用到压缩软件呢?我们都知道,文件是用编码进行存储的,编码要用到字节,而不可避免的一个文件中会出现很多重复的字节,用压缩软件可以减少重复的字节,方便在互联网上实现更快的传输,也可以减少文件在磁盘上的占用空间,常见的压缩软件有rar,zip等。

    压缩可以分为无损压缩和有损压缩两种,无损压缩后的文件,经过解压后可以完全恢复到之前的文件,rar,zip等格式都是无损压缩格式,而图片文件jpg,音乐文件mp3都是有损压缩格式。

     

    2.编码介绍

    计算机文件是由一个个字节组成的,一个字节有8位二进制编码构成,共有0-255种可能的情况。由于文件中的字节可能会重复出现,可以对不同的字节设计长度不等的编码,让出现次数较多的字节,采用较短的编码,这样可以使文件编码的总长度减少。

     

    3.哈夫曼树和哈夫曼编码

    (1)哈夫曼树

    有关二叉树的知识这里就不讲解了,大家可以自行学习。这里我们统计文件中256种字节重复的次数作为权值,构造一棵有256个叶节点的二叉树,如果带权路径长度最小,我们称为这样的二叉树为最有二叉树,也叫哈夫曼(Huffman)树。

    (2)哈夫曼编码

    哈夫曼树从根结点到每个叶子结点都有一条路径,对路径上的分支,约定指向左子树的为0,指向右子树的为1,从根到每个叶子结点路径上的0和1构成的序列就是这个叶节点的哈夫曼编码。

    如图所示:

    这时编码就是:

    A:000  B:001  C:010 D:011 E:11

    使用哈夫曼编码给每个字节重新编码,重复次数较多的字节,哈夫曼编码较短,这样就比以前的二进制编码短了许多,因此可以实现压缩。

     

     

    这里我们实现把一个bmp格式的图片进行压缩编码。

    二:过程和代码实现与分析

    1.流程简述:

    (1)读取文件

    先读取文件,生成一棵带权二叉树。树在程序中可以使用顺序结构,链式结构两种方式实现,由于这棵带权二叉树的叶子节点有256个,存储空间是固定的,则这里可以使用顺序结构来表示二叉树。

    (2)定义二叉树结构

    定义一个结构体HaffNode来表示二叉树的叶子节点,记录每个结点的权值,标记,父结点,左孩子和右孩子。创建一个结构体数组来存储这棵带权二叉树的每个叶子结点的信息。

    (3)生成哈夫曼编码

    其次,生成Huffman树后,要生成哈夫曼编码,就要先遍历这棵二叉树,这里我用的是先序遍历方法,定义一个字符串数组Code来存储每个叶子结点的哈夫曼编码。

    (4)字符串转字节实现压缩

    )由于哈夫曼编码是以字符串数组的形式保存的,重新编码后的数据将是一个很长的字符串。定义Str2byte函数,将字符串转化为字节,才能转化为最终的编码,将其保存到*.huf中,则实现了文件压缩。

    (5)解压缩

    最后,为了保证压缩后的数据能够被正常解压,除了保存压缩的数据,还应保存原文件的长度和256种字节重复出现的次数。这时就需要定义一个文件头,用于保存这些信息,再保存压缩文件时,同时向文件中写入文件头和压缩数据,保证文件能够被还原。

     

    2.代码实现与分析

    (1)打开Microsoft Visual Studio 2010,创建一个解决方案,名字为"HuffmanSLN",在HuffmanSLN解决方案下面新建一个空的win32控制台工程,名字为"HfmCompressCPro"。

    (2)打开文件

    在源文件(Source Files)中新建"main.cpp"文件,作为程序运行的入口函数。

    导入<iostream>头文件,声明using bamespace std,使用cout输出信息,用cin接受键盘输入文件信息。

    代码如下:
     

    #include <iostream>
    #include <stdlib.h>
    using namespace std;
    
    int main()
    {
            cout<<"--------------Huffman文件压缩编码---------------"<<endl;
    	cout<<"请输入文件名:";
    	char filename[256];//文件名
    	cin>>filename;
            return 0;
    }

    (3)读取原文件

    以二进制流的方式,只读打开文件,一个个地逐个读取字节数据,统计文件中256种字节重复出现的次数,保存到一个数组中

    int weight[256]中,然后将扫描的结果在控制台打印下来。

    代码如下:

    #include <iostream>
    #include <stdlib.h>
    using namespace std;
    
    int main()
    {
            cout<<"--------------Huffman文件压缩编码---------------"<<endl;
    	cout<<"请输入文件名:";
    	char filename[256];//文件名
    	cin>>filename;
    
            char ch;
    	int weight[256]={0};
    
    	//以二进制流的方式打开文件
    	FILE* in = fopen(filename,"rb");
    	if(in == NULL)
    	{
    		printf("打开文件失败");
    		return 0;
    	}
    	//扫描文件,获得权重
    	while(ch = getc(in) != EOF)
    	{
    		weight[ch]++;
    	}
    	//关闭文件
    	fclose(in);
    
            //显示256个字节出现的次数
    	cout<<"Byte "<<"Weight"<<endl;
    	for(int i=0;i<256;i++)
    	{
    		printf("0x%02X %d\n",i,weight[i]);
    	}
    	system("pause");
            return 0;
    }

    这里我们的图片在E盘的根目录下:

    即下面的一张图:

    运行结果如下:

    (4)生成哈夫曼树

    在Haffman.h文件中,定义一个存储哈夫曼树结点信息的结构体,有权值,标记(若当前结点未加入结构体,flag=0;若当前结点加入结构体,flag=1),双亲结点下标,左孩子结点下标,右孩子结节下标。

    在Haffman.cpp文件中创建构造哈夫曼树的函数,在Haffman.h文件中声明。

    Haffman.h文件

    typedef struct
    {
    	int weight;		//权值
    	int flag;	    //标记
    	int parent;		//双亲结点下标
    	int leftChild;	//左孩子下标
    	int rightChild;	//右孩子下标
    }HaffNode;
    
    //创建叶结点个数为n,权值数组为weight的哈夫曼树haffTree
    void Haffman(int weight[],int n,HaffNode haffTree[]);

    Haffman.cpp文件

    #include "Huffman.h"
    #define MaxValue 10000
    
    //创建叶结点个数为n,权值数组为weight的哈夫曼树haffTree
    void Haffman(int weight[],int n,HaffNode haffTree[])
    {
    	int i,j,m1,m2,x1,x2;
    	//哈夫曼树haffTree初始化,n个叶结点的二叉树共有2n-1结点
    	for(i = 0;i < 2 * n - 1;i++)
    	{
    		if(i < n)	//如果是小于n的结点(叶子结点),则把每个字节的重复次数作为权值赋给这些该结点
    			haffTree[i].weight = weight[i];
    		else
    			haffTree[i].weight = 0;	//其他非叶子结点权值设为0
    		haffTree[i].parent = -1;
    		haffTree[i].flag   = 0;
    		haffTree[i].leftChild  = -1;
    		haffTree[i].rightChild = -1;
    	}
    
    	//构造哈夫曼树haffTree的n-1个非叶结点
    	for(i = 0;i < n - 1;i++)
    	{
    		//这里假设先进行一次循环,i=0,后面的代码注释方便大家理解
    		m1=m2=MaxValue;
    		x1=x2=0;
    		//找到权值最小和次小的子树,就是找到权值最小的两个结点
    		for(j = 0;j < n + i;j++)	//这里先让i=0;则对于n个叶子结点,按权值最小和次小的顺序连接结点生成哈夫曼树
    		{
    			//这里比较每个结点的权值,如果小于上一个结点(已查找的最小权值结点)权值且该结点没有被访问
    			if(haffTree[j].weight < m1 && haffTree[j].flag == 0)	
    			{
    				m2 = m1;	//令m2为上一个结点(非最小结点的前面的权值)的下标
    				x2 = x1;	//x2为上一个结点(非最小结点的前面的权值)下标
    				m1 = haffTree[j].weight;	//m1记录该结点的权值
    				x1 = j;						//x1为该结点的下标
    			}
    			//这里比较每个结点的权值,如果小于非最小结点的前面的结点权值且该结点没有被访问
    			else if(haffTree[j].weight < m2 && haffTree[j].flag == 0)		
    			{
    				m2 = haffTree[j].weight;	//m2记录该结点的权值
    				x2 = j;						//x2记录该结点的下标
    			}
    			//比较完所有的结点后,x1就为最小权值结点的下标,x2就为次小权值结点的下标
    		}
    
    		//将找出的两棵权值最小和次小的子树合并为一棵子树
    		haffTree[x1].parent = n + i;	//x1就为最小权值结点的下标
    		haffTree[x2].parent = n + i;	//x2就为次小权值结点的下标
    		haffTree[x1].flag   = 1;		//x1被访问
    		haffTree[x2].flag   = 1;		//x2被访问
    		haffTree[n+i].weight = haffTree[x1].weight + haffTree[x2].weight;
    		haffTree[n+i].leftChild = x1;	//左孩子存储结点x1
    		haffTree[n+i].rightChild = x2;	//右孩子存储结点x2
    	}
    }

    在main.cpp中编测试一下,改为如下形式:

     

    #include <iostream>
    #include <stdlib.h>
    #include "Haffman.h"
    #define MaxValue 10000
    using namespace std;
    
    int main(){
    	cout<<"--------------Huffman文件压缩编码---------------"<<endl;
    	cout<<"请输入文件名:";
    	char filename[256];//文件名
    	cin>>filename;
    
    	char ch;
    	int i;
    	int n = 256;
    	int weight[256]={0};
    
    	//以二进制流的方式打开文件
    	FILE* in = fopen(filename,"rb");
    	if(in == NULL)
    	{
    		printf("打开文件失败");
    		return 0;
    	}
    	//扫描文件,获得权重
    	while(ch = getc(in) != EOF)
    	{
    		weight[ch]++;
    	}
    	//关闭文件
    	fclose(in);
    
    	//测试哈夫曼树构造函数
    	HaffNode *myHaffNode = (HaffNode *)malloc(sizeof(HaffNode)*(2*n-1));
    	if(n >MaxValue)
    	{
    		printf("给出的n越界,修改MaxValue");
    		exit(1);
    	}
    	Haffman(weight,n,myHaffNode);
    
    	printf("字节种类 权值 标记 双亲结点下标 左孩子结点下标 右孩子结点下标\n");
    	for(i = 0;i < n;i++)
    	{
    		printf("pHT[%d]\t%d\t%d\t%d\t%d\t%d\n",i,myHaffNode[i].weight,myHaffNode[i].flag,myHaffNode[i].parent,myHaffNode[i].leftChild,myHaffNode[i].rightChild);
    	}
    	system("pause");
    	return 0;
    }

    运行结果如下:

    (5)生成哈夫曼编码

    按照先序遍历的算法对上面生成的哈夫曼树进行遍历,生成哈夫曼编码。

    在Haffman.h文件中创建结构体哈夫曼数组,用于存储编码的起始下表和权值。

    在Haffman.cpp文件中创建构造哈夫曼树编码的函数,在Haffman.h文件中声明。

    Haffman.h文件

    typedef struct
    {
    	int weight;		//权值
    	int flag;	    //标记
    	int parent;		//双亲结点下标
    	int leftChild;	//左孩子下标
    	int rightChild;	//右孩子下标
    }HaffNode;
    
    typedef struct
    {
    	int bit[10000];	//数组
    	int start;	//编码的起始下标
    	int weight;	//字符的权值
    }Code;
    
    //创建叶结点个数为n,权值数组为weight的哈夫曼树haffTree
    void Haffman(int weight[],int n,HaffNode haffTree[]);
    
    //有n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode
    void HaffmanCode(HaffNode haffTree[],int n,Code haffNode[]);

    Haffman.cpp文件

    //有n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode
    void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[])
    {
    	Code *cd = (Code *)malloc(sizeof(Code));
    	int i,j,child,parent;
    	//求n个叶结点的哈夫曼编码
    	for(int i = 0;i < n;i++)
    	{
    		cd->start  = n-1;					//不等长编码的最后一位为n-1
    		cd->weight = haffTree[i].weight;	//取得编码对应的权值
    		child  = i;
    		parent = haffTree[child].weight;
    		//由叶结点向上直到根节点
    		while(parent != -1)
    		{
    			if(haffTree[parent].leftChild == child)	//判断左孩子是否存在
    				cd->bit[cd->start] = 0;
    			else									//判断右孩子是否存在
    				cd->bit[cd->start] = 1;
    			cd->start--;
    			child  = parent;
    			parent = haffTree[child].parent;
    		}
    		for(j = cd->start+1;j < n;j++)
    			haffCode[j].bit[j] = cd->bit[j];
    		haffCode[i].start  = cd->start + 1;
    		haffCode[i].weight = cd->weight;
    	}
    }

    现在在主函数中测试一下:

    #include <iostream>
    #include <stdlib.h>
    #include "Haffman.h"
    using namespace std;
    #define MaxValue 10000
    
    
    int main(){
    	cout<<"--------------Huffman文件压缩编码---------------"<<endl;
    	cout<<"请输入文件名:";
    	char filename[256];//文件名
    	cin>>filename;
    
    	char ch;
    	int i,j;
    	int n = 256;
    	int weight[256]={0};
    
    	//以二进制流的方式打开文件
    	FILE* in = fopen(filename,"rb");
    	if(in == NULL)
    	{
    		printf("打开文件失败");
    		fclose(in);
    		return 0;
    	}
    	//扫描文件,获得权重
    	while(ch = fgetc(in) != EOF)
    	{
    		weight[ch]++;
    	}
    	
    	//关闭文件
    	fclose(in);
    
    	
    	//显示256个字节出现的次数
    	cout<<"Byte "<<"Weight"<<endl;
    	for(i=0;i<256;i++)
    	{
    		printf("0x%02X %d\n",i,weight[i]);
    	}
    	
    	HaffNode *myHaffNode = (HaffNode *)malloc(sizeof(HaffNode)*(2*n-1));
    	Code *myHaffCode = (Code *)malloc(sizeof(Code)*n);
    	if(n >MaxValue)
    	{
    		printf("给出的n越界,修改MaxValue");
    		exit(1);
    	}
    	
    
    	//测试哈夫曼树构造函数
    	Haffman(weight,n,myHaffNode);
    	//测试哈夫曼编码函数
    	HaffmanCode(myHaffNode,n,myHaffCode);
    
    	//输出每个字节叶结点的哈夫曼编码
    	printf("编码信息为:");
    	for(i = 0;i < n;i++)
    	{
    		//printf("0x%02X ",i);
    		printf("Weight = %d,Code = ",myHaffCode[i].weight);
    		for(j = myHaffCode[i].start;j < n;j++)
    			printf("%d",myHaffCode[i].bit[j]);
    		printf("\n");
    	} 
    
    	system("pause");
    	return 0;
    }

    运行结果如下:

    这里我们发现权值为141291的字节没有显示编码,原因是这个编码个数太长了,在这里显示不出来。

    (6)压缩源文件

    创建Compress.h和Compress,cpp文件,定义Compress函数用于压缩原文件。

    由于编码是以字符数组的形式保存的,重新编码后的数据将是一个很长的字符串,先计算需要的空间,然后把编码按位进行存放到字符数组中,或者直接存放,这里采用直接存放的方式。

    int k,ji=0;
    	int jiShu[1000];
    	//输出每个字节叶结点的哈夫曼编码
    	printf("编码信息为:");
    	for(i = 0;i < n;i++)
    	{
    		for(j = myHaffCode[i].start;j < n;j++)
    			for(k = 0;k < myHaffCode[k].weight+1;k++)
    			{
    				printf("%d",myHaffCode[i].bit[j]);
    				jiShu[ji] = myHaffCode[i].bit[j];
    				ji++;
    			}
    	} 

    结果如下:

    (6)写入文件

    建立一个新文件,文件名为"原文件名字+.huf",将压缩后的数据写入文件。

    为了保证压缩后的数据能够被正确解压,必须把相关的解压缩规则写进去,就是把权值信息写入进去,还有文件类型,长度,权值。

    在Huffman.h中定义一个文件头结构和InitHead函数声明,在Huffman.cpp中写入函数。

    代码如下:
    Huffman.h文件

    struct HEAD
    {
    	char type[4]; //文件类型
    	int length;	  //原文件长度
    	int weight[256]; //权值数组
    }

    Huffman.cpp文件

    //记录文件信息
    int initHead(char pFileName[256],HEAD &sHead)
    {
    	int i;
    	//初始化文件头
    	strcpy(sHead.type,"bmp");
    	sHead.length = 0;	//原文件长度
    	for(i = 0;i<256;i++)
    	{
    		sHead.weight[i] = 0;
    	}
    
    	//以二进制流的方式打开文件
    	FILE* in = fopen(pFileName,"rb");
    	if(in == NULL)
    	{
    		printf("打开文件失败");
    		fclose(in);
    		return 0;
    	}
    	char ch;
    	//扫描文件,获得权重
    	while(ch = fgetc(in) != EOF)
    	{
    		sHead.weight[ch]++;
    		sHead.length++;
    	}
            //关闭文件
    	fclose(in);
    	in = NULL;
    	return 0;
    }

    现在我们得到文件的信息和编码,就可以得到压缩后的文件,直接在主函数中写代码:

    #include <iostream>
    #include <stdlib.h>
    #include <io.h>
    #include "Haffman.h"
    //#include "Compress.h"
    using namespace std;
    #define MaxValue 10000
    
    
    int main(){
    	cout<<"--------------Huffman文件压缩编码---------------"<<endl;
    	cout<<"请输入文件名:";
    	char filename[256];//文件名
    	cin>>filename;
    
    	char ch;
    	int i,j;
    	int n = 256;
    	int weight[256]={0};
    
    	//以二进制流的方式打开文件
    	FILE* in = fopen(filename,"rb");
    	int fn = _fileno(in); /*取得文件指针的底层流式文件号*/
    	int sz = _filelength(fn);/*根据文件号取得文件大小*/
    	printf("%d字节\n",sz);
    	if(in == NULL)
    	{
    		printf("打开文件失败");
    		fclose(in);
    		return 0;
    	}
    	//扫描文件,获得权重
    	while(ch = fgetc(in) != EOF)
    	{
    		weight[ch]++;
    	}
    	
    	//关闭文件
    	fclose(in);
    
    	/*
    	//显示256个字节出现的次数
    	cout<<"Byte "<<"Weight"<<endl;
    	for(i=0;i<256;i++)
    	{
    		printf("0x%02X %d\n",i,weight[i]);
    	}
    	*/
    	
    	HaffNode *myHaffNode = (HaffNode *)malloc(sizeof(HaffNode)*(2*n-1));
    	Code *myHaffCode = (Code *)malloc(sizeof(Code)*n);
    	if(n >MaxValue)
    	{
    		printf("给出的n越界,修改MaxValue");
    		exit(1);
    	}
    	
    
    	//测试哈夫曼树构造函数
    	Haffman(weight,n,myHaffNode);
    	//测试哈夫曼编码函数
    	HaffmanCode(myHaffNode,n,myHaffCode);
    
    	/*
    	printf("字节种类 权值 标记 双亲结点下标 左孩子结点下标 右孩子结点下标\n");
    	for(i = 0;i < n;i++)
    	{
    		printf("pHT[%d]\t%d\t%d\t%d\t%d\t%d\n",i,myHaffNode[i].weight,myHaffNode[i].flag,myHaffNode[i].parent,myHaffNode[i].leftChild,myHaffNode[i].rightChild);
    	}
    	*/
    	
    	HEAD sHead;
    	initHead(filename,sHead);
    
    	int cc=0;
    	//生成文件名
    	char newFileName[256] = {0};
    	strcpy(newFileName,filename);
    	strcat(newFileName,".huf");
    	//以二进制流的方式打开文件
    	FILE* out = fopen(newFileName,"wb");
    	//写文件头
    	//fwrite(&sHead,sizeof(HEAD),1,out);
    	//int k,ji=0;
    	//int jiShu[1000];
    	//输出每个字节叶结点的哈夫曼编码
    	//printf("编码信息为:");
    	for(i = 0;i < n;i++)
    	{
    		for(j = myHaffCode[i].start;j < n;j++)
    		{
    				//printf("%d",myHaffCode[i].bit[j]);
    				//写压缩后的编码
    				cc+=sizeof(myHaffCode[i].bit[j]);
    		}
    
    	} 
    
    	fclose(out);
    	out = NULL;
    	cout << "生成压缩文件:" << newFileName <<endl;
    	printf("\n");
    	printf("%d字节",sizeof(newFileName)+cc);
    	double bi=(sizeof(newFileName)+cc)/(double)sz;
    	printf("压缩比例为:%.2f",bi);
    	system("pause");
    	return 0;
    }

    结果如下:

    而我们也生成了该buf的压缩文件:

     

    需要详细代码请私信我:

    qq:1657264184

    微信:liang71471494741

     

     

    展开全文
  • 哈夫曼图片压缩

    2016-05-23 22:19:08
    构建哈夫曼树,哈夫曼编码,实现图片压缩
  • 256色灰度图哈夫曼编码压缩

    千次阅读 2015-12-02 22:56:32
    哈夫曼编码原理:设256种颜色在图片中各出现了a1、a2、…、an次,于是可以得到一个对应的权重数组。将权重数组以以下范例形式建立哈夫曼树。 范例:假设一个含有6个数值的权重数组9、8、3、6、7、1: 1. 首先选出...
  • 一、 哈夫曼编码开关、 二、 哈夫曼编码原理、 三、 libjpeg-turbo 函数库、 四、 libjpeg-turbo 函数库下载
  • 哈夫曼图片压缩及解压

    千次阅读 2019-09-28 02:35:33
    哈夫曼图片压缩及解压 ...哈夫曼编码 compress 解压 //Compress.h #ifndef COMPRESS_H #define COMPRESS_H typedef unsigned char * buffer; int Compress(const char *pFilename); unsigned char Str2by...
  • 压缩图片文件5 . 解压缩图片文件 二、将项目分成三个小任务,下一任务是在上一任务的基础上完成:1.任务一:统计权值、创建Huffman树2.任务二:生成Huffman编码、保存压缩文件3.任务三:解压压缩文件,恢复原...
  • 哈夫曼编码

    2013-08-22 21:16:21
    利用哈夫曼编码实现对文本图片音频的压缩,简单的操作平台visualC++ 6.0
  • 哈夫曼压缩图片.rar

    2019-07-10 10:40:51
    每次选出权值最小且没有双亲的两个节点建立新的哈弗曼树。 无栈非递归遍历Huffman树,求Huffman编码。...要注意的是当文件较小时,不宜使用哈夫曼来进行压缩,此时文件头占比过大,会使压缩结果很差。
  • 功能要求 1. 针对一幅BMP格式的图片文件,统计...2. 利用上述哈夫曼树产生的哈夫曼编码图片文件进行压缩。 3. 压缩后的文件与原图片文件同名,加上后缀.huf(保留原后缀),如pic.bmp 压缩后pic.bmp.huf 4. 解压缩
  • 哈夫曼编码用于常用的压缩算法,比如JPEG图片的有损压缩。也是一种不定长的前缀编码, 即任何一个编码都不是其他编码的前缀。 (http://www.cnblogs.com/wuyuankun/p/3982216.html) ...
  • 通过“图片压缩编码”的编程实践,学习树、二叉树、哈夫曼树、哈夫曼编码及其应用。 (1)掌握二叉树的存储结构 (2) 掌握并理解Huffman树、Huffman编码等知识和应用 (3)掌握文件的操作 (4)使用Huffman算法实现图像压缩...
  • 图像、电影、音乐,数据不仅仅限制于文本,绝大多数数据会有冗余,例如在文本文件中,很多字符出现的频率远高于其他字符,图片编码中也存在大片的相同区域,电影、声音等类似信号的文件都含有大量重复模式。...
  • (笔记图片截图自课程Image and video processing: From ...JPEG用哈夫曼编码(Huffman Encoder)作为其符号编码。哈弗曼编码是压缩算法中的经典,它理论上可以将数据编成平均长度最小的无前缀码(Prefix-Free Code)。 ...
  • 通过“图片压缩编码”的编程实践,学习树、遍历二叉树、哈夫曼树、哈夫曼编码和他们的编程应用。 (1)掌握树的存储结构 (2)掌握二叉树的三种遍历方法 (3)掌握并理解Huffman树、Huffman编码等知识和应用 (4)掌握文件的...
  • huffman 哈夫曼编码

    2013-03-13 12:46:45
    数据结构编写的程序,经测试可压缩图片,音乐,电影,然后完整解压,附文档。
  • 也可以用多线程优化运行速度,LZ编码类可以试着增加独立性,取消与霍夫曼编码的关联,建议试运行时使用较小的图片,过一下main函数。 文中参考网址及部分代码来源: dct变换及逆变换的代码及量化部分的参考代码 ...
  • 4、生成哈夫曼编码。 5、压缩原文件。 6、保存压缩文件。 7、扩展功能。 实验代码参考:https://blog.csdn.net/cxh_1231/article/details/80530668 main.cpp 主函数 #include "iostream" #include "file.h" #include...
  • C语言实现哈夫曼编码

    2012-07-03 01:22:47
    C语言实现的huffman编码程序,可对文本文件,图片文件等几乎所有文件类型进行编码压缩
  • 哈夫曼 编码c实现

    2013-05-21 22:28:26
    c实现的无失真压缩哈弗曼编码压缩压缩功能,所压缩的可以是word。txt等文件,图片还不能压缩,只能一般的文件格式。
  • What is Huffman Coding? The Huffman Coding algorithm is a building block of many compression ...哈夫曼编码算法是很多压缩算法的基础,如PNG图片和GZIP使用的DEFLATE算法。 Why should I care? Have you e.
  • 哈夫曼压缩技术

    2013-07-01 22:00:09
    基于哈夫曼编码的无损压缩,能处理word 、excel、pdf、图片压缩,但图片压缩效率低(用EZW)。
  • 哈夫曼压缩软件

    2018-05-03 23:54:19
    利用哈夫曼编码的原理,编写一个压缩软件。可以压缩基本的文件,如doc、docx、excel、ppt、pptx、pdf、txt等文档,也可以压缩png、gif、jpg、mp3、mov、mp4等图片、声音、视频等文件。
  • 图像压缩编码哈夫曼树)

    千次阅读 2019-01-16 12:13:28
    1.首先图片压缩编码对不同文件的压缩效率是不一样的  这也是我在最后发现...哈夫曼编码压缩解压缩实现&amp;不同类型文件压缩比的测试 https://blog.csdn.net/to_be_better/article/details/50431352   ...

空空如也

空空如也

1 2 3 4
收藏数 63
精华内容 25
关键字:

哈夫曼编码压缩图片