原理就是统计带压缩文件字符频率，构建哈夫曼树，然后求哈夫曼编码，将字符频率(解压的时候通过字符频率建树)和哈夫曼编码写入文件，完成压缩。
 
压缩代码：
 
//获取一个文件的每个字符的频率
void get_frequency(string filename, int frequency[256])
{
    ifstream fin(filename);
    
    if (!fin.is_open())
    {
        return ;
    }
    
    memset(frequency, 0, sizeof(int) * 256);
    
    while (!fin.eof())
    {
        unsigned char temp = fin.get();
        if (fin.eof())
        {
            break;
        }
        frequency[temp]++;
    }

    fin.close();
}
 
//哈夫曼树的节点
struct node
{
    unsigned char ch;
    int w;
    node *rch, *lch;
};
//获取一个行自定义属性的节点
node* new_node(unsigned char ch, int w, node* lch = NULL, node* rch = NULL)
{
    node* temp = (node*)malloc(sizeof(node));
    temp->ch = ch;
    temp->w = w;
    temp->rch = rch;
    temp->lch = lch;
    return temp;
}
//优先级队列比较大小的方法
struct cmp
{
    bool operator () (node* x, node* y)
    {
        return x->w > y->w;
    }
};
//建树，返回根节点
node* build_haffman(int frequency[256])
{
    priority_queue<node*, vector<node*>, cmp> q;
    for (int i = 0; i < 256; i++)
    {
        if (frequency[i] != 0)
        {
            node* temp = new_node((unsigned char)i, frequency[i]);
            q.push(temp);
        }
    }
    while (q.size() > 1)
    {
        node* x = q.top();
        q.pop();
        node* y = q.top();
        q.pop();
        
        node* temp = new_node(0, x->w + y->w, x, y);
        q.push(temp);
    }
    return q.top();
}
 
//后跟遍历销毁树
void destory_haffman(node **root)
{
    if (*root)
    {
        destory_haffman(&(*root)->lch);
        destory_haffman(&(*root)->rch);
        free(*root);
    }
}
 
//获取字符的哈夫曼编码
void get_haffman_code(node* root, vector<char>& v, string code[256])
{
    if (root)
    {
        if (root->lch == NULL && root->rch == NULL)
        {
            string temp = "";
            for (int i = 0; i < v.size(); i++)
            {
                temp += v[i];
            }
            code[root->ch] = temp;
        }
        v.push_back('0');
        get_haffman_code(root->lch, v, code);
        v.pop_back();
        v.push_back('1');
        get_haffman_code(root->rch, v, code);
        v.pop_back();
    }
}
 
//将8位01码表示为一个unsigned char
unsigned char create_uchar(string haff_code, int index)
{
    unsigned char ch = 0;
    unsigned char flag = 128;
    for (int i = index; i < index + 8; i++)
    {
        ch += flag * (haff_code[i] - '0');
        flag /= 2;
    }
    return ch;
}
//压缩文件的流程
void compress_to_file(string src_file, string dst_file)
{
    ifstream fin(src_file);
    ofstream fout(dst_file, ios::binary);
    
    if (!fin.is_open() || !fout.is_open())
    {
        return;
    }
    
    int frequency[256];
    string code[256];
    vector<char> v;
    get_frequency("/Users/Rubik/Desktop/123.txt", frequency);
    node* root = build_haffman(frequency);
    get_haffman_code(root, v, code);
    
    string haff_code = "";
    unsigned char ch;
    while (!fin.eof())
    {
        ch = fin.get();
        if (fin.eof()) break;
        haff_code += code[ch];
    }
    int len = (int)haff_code.length();
    cout << len << endl;
    fout.write((const char*)frequency, sizeof(int) * 256);
    fout.write((const char*)&len, sizeof(int));
    
    while (haff_code.length() % 8 != 0)
    {
        haff_code += '0';
    }
    
    for (int i = 0; i < haff_code.length(); i += 8)
    {
        unsigned char temp = create_uchar(haff_code, i);
        fout.write((const char*)&temp, sizeof(char));
    }
    
    fout.close();
    fin.close();
    destory_haffman(&root);
}
 
解压部分比较简单，获取字符频率，建树，获取unsigned char，遍历树，遇到叶子节点就输出到解压文件
 
//通过一个unsigned char遍历haffman树，存到s[]里，s长度为slen， cnt为已走长度，len为有效长度
node* get_res(node* root, node* pos, unsigned char temp, char* s, int &slen, int &cnt, int len)
{
    slen = 0;
    for (int i = 128; i > 0 && cnt < len; i >>= 1)
    {
        if (i & temp)
        {
            pos = pos->rch;
        }
        else
        {
            pos = pos->lch;
        }
        cnt++;
        if (pos->lch == pos->rch && pos->lch == NULL)
        {
            s[slen++] = pos->ch;
            pos = root;
        }
    }
    return pos;
}

void decompress_to_file(string src_file, string dst_file)
{
    ifstream fin(src_file);
    ofstream fout(dst_file, ios::binary);
    
    int frequency[256];
    fin.read((char*)frequency, sizeof(int) * 256);
    
    node* root = build_haffman(frequency);
    
    vector<char> v;
    string code[256];
    get_haffman_code(root, v, code);
    
    for (int i = 0; i < 256; i++)
    {
        if (code[i].length() > 0)
        {
            cout << code[i] << endl;
        }
    }
    
    int len;
    fin.read((char*)&len, sizeof(int));
    
    unsigned char temp;
    node *pos = root;
    char s[8];
    int slen, cnt = 0;
    while (!fin.eof())
    {
        fin.read((char*)&temp, sizeof(char));
        pos = get_res(root, pos, temp, s, slen, cnt, len);
        for (int i = 0; i < slen; i++)
        {
            fout << s[i];
        }
    }
    
    destory_haffman(&root);
    
    fin.close();
    fout.close();
}
 
int main()
{
    compress_to_file("/Users/Rubik/Desktop/123.txt", "/Users/Rubik/Desktop/out.txt");
    decompress_to_file("/Users/Rubik/Desktop/out.txt", "/Users/Rubik/Desktop/456.txt");
    return 0;
}
 
效果如下
 

代码
 
public class Main {
    public static void main(String[] args) {
        String srcFile = "e://des.zip";
        String desFile = "e://222.jpg";
        //zipFile(srcFile,desFile);
        unZipFile(srcFile,desFile);
    }
    static Map<Byte,String> map = new HashMap<Byte,String>();
    public static void unZipFile(String srcFile,String desFile){
        //创建文件输入流 对象输入流 文件输出流
        FileInputStream fis = null;
        ObjectInputStream ois = null;
        FileOutputStream fos = null;

        try {
            //对文件输入流和对象输入流进行初始化
            fis = new FileInputStream(srcFile);
            ois = new ObjectInputStream(fis);

            //创建字节数组，接收读取的 经过哈夫曼编码后的 字节数组
            byte[] huffmanBytes = (byte[])ois.readObject();
            //创建map集合 接收读取的 哈夫曼编码
            Map<Byte,String> huffmanCode = (Map<Byte,String>)ois.readObject();

            //创建文件输出流
            fos = new FileOutputStream(desFile);
            //创建字节数组 接收解压之后的 字节数组
            byte[] afterUnZipBytes = decode(huffmanCode,huffmanBytes);
            //将字节数组写出
            fos.write(afterUnZipBytes);
        }catch (Exception e){
            e.printStackTrace();
        }finally {
            try {
                fis.close();
                ois.close();
                fos.close();
            }catch (Exception e){
                e.printStackTrace();
            }
        }
    }
    public static void zipFile(String srcFile,String desFile){
        //创建文件输入流 输出流 对象输出流
        //用对象流  便于恢复
        FileInputStream fis = null;
        FileOutputStream fos = null;
        ObjectOutputStream oos = null;

        try {
            //首先创建文件输入流
            fis = new FileInputStream(srcFile);
            //创建与文件大小相同的字节数组，用于装源文件
            byte[] srcBytes = new byte[fis.available()];
            //将文件读入字节数组中
            fis.read(srcBytes);

            //创建字节数组，用于接收经哈夫曼编码后的字节数组
            byte[] afterZipBytes = huffmanZip(srcBytes);

            //创建输出流
            fos = new FileOutputStream(desFile);
            oos = new ObjectOutputStream(fos);
            oos.writeObject(afterZipBytes);
            oos.writeObject(map);//一定要把哈夫曼编码写出去

        }catch (Exception e){
            e.printStackTrace();
        }finally {
            try {
                fis.close();
                fos.close();
                oos.close();
            }catch (Exception e){
                e.printStackTrace();
            }
        }
    }
    /**
     *
     * @param bytes 原始的字节数组
     * @return  经过赫夫曼编码后的字节数组
     */
    public static byte[] huffmanZip(byte[] bytes){
        //首先得到每个节点，封装成集合
        List<Node> list = getList(bytes);

        //然后利用节点集合，创建赫夫曼树
        Node huffmanTree = createHuffmanTree(list);

        //根据赫夫曼树，得到每个字符的编码,保存在map中
        getCode(huffmanTree,new StringBuilder(),"");

        //根据字符的编码，得到最终的字节数组
        byte[] huffmanByte = getHuffmanByte(bytes);

        return huffmanByte;
    }

    //得到每个字符与其权值，封装成集合返回
    public static List<Node> getList(byte[] bytes){
        List<Node> nodeList = new ArrayList<Node>();

        //创建map集合 用作存储data 和 weight
        HashMap<Byte, Integer> byteIntegerHashMap = new HashMap<>();
        for (byte oneByte: bytes){
            if (byteIntegerHashMap.get(oneByte) == null){
                //说明是第一次添加
                byteIntegerHashMap.put(oneByte,1);
            }else {
                //不是第一次添加
                byteIntegerHashMap.put(oneByte,byteIntegerHashMap.get(oneByte) + 1);
            }
        }

        //遍历map集合 将data和weight加到Node
        for (Map.Entry<Byte,Integer> entry: byteIntegerHashMap.entrySet()){
            nodeList.add(new Node(entry.getKey(),entry.getValue()));
        }

        return nodeList;
    }

    //得到哈夫曼树
    public static Node createHuffmanTree(List<Node> nodeList){
        while (nodeList.size() > 1){
            Collections.sort(nodeList);

            Node leftNode = nodeList.get(0);
            Node rightNode = nodeList.get(1);

            Node parent = new Node(null,leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            //System.out.println("leftNode=" + leftNode + "rightNode="+rightNode);
            nodeList.remove(leftNode);
            nodeList.remove(rightNode);
            nodeList.add(parent);
        }

        return nodeList.get(0);
    }

    //得到哈夫曼编码值
    public static void getCode(Node node,StringBuilder stringBuilder,String code){
        //这个if是针对 根节点有可能是null
        if (node != null){
            //这里需要创建一个新的StringBuilder对象，我目前还不知道为啥 但是不创建就不对
            StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
            stringBuilder1.append(code);
            //System.out.println("node="+node+"stringBuilder="+stringBuilder1);
            if (node.data == null){
                //说明是非叶子节点
                //它的left和right一定不是null 这是哈夫曼树的特点
                getCode(node.left,stringBuilder1,"0");

                getCode(node.right,stringBuilder1,"1");
            }else {
                //把这个叶子节点加到map集合中
                map.put(node.data,stringBuilder1.toString());
            }
        }
    }

    //返回得到的字节数组
    public static byte[] getHuffmanByte(byte[] bytes){
        StringBuilder stringBuilder = new StringBuilder();

        //得到全是数的序列
        for (byte oneByte: bytes){
            stringBuilder.append(map.get(oneByte));
        }

        //将序列按8个一组（一个字节）进行划分
        //首先得到分组的数目
        int len;
        if (stringBuilder.length() % 8 == 0){
            //说明是8的整数倍
            len = stringBuilder.length() / 8;
        }else {
            len = stringBuilder.length() / 8 + 1;
        }

        //然后根据得到的len创建数组
        byte[] finalBytes = new byte[len];
        int index = 0;

        for (int i = 0;i < stringBuilder.length();i += 8){
            //finalBytes[index] = stringBuilder.substring(i,i + 8) 这种是不对的 不能直接加
            String oneByte;
            if (i + 8 > stringBuilder.length()){
                //说明有可能一共就少于8个数 也有可能是到了最后一个不足8个数的组
                oneByte = stringBuilder.substring(i);
            }else {
                oneByte = stringBuilder.substring(i,i + 8);
            }

            finalBytes[index] = (byte)Integer.parseInt(oneByte,2);//这里还要转成byte类型，后面的参数中还有2
            index++;
        }

        return finalBytes;

    }

    //将一个byte元素转成二进制
    public static String byteToBitString(boolean flag,byte b){
        int temp = b;//将字节类型转为int类型

        if (flag){//需要补高位，如果是最后一个字节，无需补高位
            temp |= 256;//按位或
        }

        String str = Integer.toBinaryString(temp);

        if (flag){
            return str.substring(str.length() - 8);
        }else {
            return str;
        }
    }

    //进行解码

    /**
     *
     * @param huffmanMap 表示哈夫曼编码表
     * @param huffmanBytes 表示经过哈夫曼编码之后得到的字节数组 [-88,......]
     * @return 返回原字节数组[i, ,l,i,.....]
     */
    public static byte[] decode(Map<Byte,String> huffmanMap,byte[] huffmanBytes){
        //首先将经过哈夫曼编码之后得到的字节数组，转成很长的一串数字
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0;i < huffmanBytes.length;i++){
            if (i == huffmanBytes.length - 1){
                //是最后一个 无需补高位
                stringBuilder.append(byteToBitString(false,huffmanBytes[i]));
            }else {
                stringBuilder.append(byteToBitString(true,huffmanBytes[i]));
            }
        }
        //这样就得到了 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100

        //得到key和value互换的 哈夫曼编码表
        Map<String,Byte> reverseHuffmanMap = new HashMap<>();
        for (Map.Entry<Byte,String> entry: huffmanMap.entrySet()){
            reverseHuffmanMap.put(entry.getValue(),entry.getKey());
        }

        //根据反转之后的哈夫曼编码表，得到字节数组
        List<Byte> arrayList = new ArrayList<Byte>();//这个地方要Byte 而不是 byte

        int i = 0;
        while (i < stringBuilder.length()){
        //for (int i = 0;i < stringBuilder.length();){
            int count = 1;
            boolean flag = true;

            while (true){
                String binaryNum = stringBuilder.substring(i,i + count);

                Byte oneByte = reverseHuffmanMap.get(binaryNum);

                if (oneByte == null){
                    //说明没匹配到，那就将count++

                    count++;
                }else {
                    //说明匹配到了
                  //  System.out.println("oneByte="+oneByte);
                    arrayList.add(oneByte);
                    break;
                }
            }
            i = i + count;
        }

        //}
        System.out.println("集合为："+ arrayList);
        //将集合转为byte数组
        byte[] finalBytes = new byte[arrayList.size()];
        for (int j = 0;j < finalBytes.length;j++){
            finalBytes[j] = arrayList.get(j);
        }

        return finalBytes;
    }

}
class Node implements Comparable<Node>{
    Byte data;//存放值
    int weight;//存放权值
    Node left;
    Node right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    //前序遍历
    public void preList(Node root){
        if (root == null){
            System.out.println("树为空");
            return;
        }else {
            this.preList();
        }
    }

    public void preList(){
        System.out.println(this);
        if (this.left != null){
            this.left.preList();
        }
        if (this.right != null){
            this.right.preList();
        }
    }
    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
}
 
结果
 

参考Crash Course的课程，做下笔记，原视频在这里 ↓
 
 
 
https://www.bilibili.com/video/BV1EW411u7th?p=21
 
 
我们要对如下一张 4像素 X 4像素的 图片进行压缩，
 
 而在磁盘中图片是一串像素值的形式存储的，每个像素的颜色由RGB确定，这样一张图片需要 48（16*3） 个字节
 
为了能够压缩图片，我们需要减少冗余的信息或者用更紧凑的表示方法。可以发现，有很多相同的排列：白黄、黑黄、黄黄、白白，这个序列可以有这四种排列组成（当然也有其他不同的方式），我们为这四种排列生成紧凑代码，用更少的字节表示每对排列
 
 
 
我们会发现，这四对出现的频率并不相同
 
 黄黄出现的次数最多，所以我们希望通过最紧凑的方式来表示，其次是白黄，黑黄和白白出现的次数最少，我们可以用长一点的来表示
 
 
为了实现以上的表示，我们需要构造哈夫曼树。
 
  
列出所有的块和频率，每轮选择两个最低的频率，将它们组成一个树。这里BY和WW频率最低,将其组成一个树，组成后的频率为2，这样就完成了一轮算法。
 
 
  
下一轮中重复这样的操作。现在白色的两个频率最低，合并！
 
 合并之后的情况如下
 
第三轮同理
 
 这样我们就完成了哈夫曼树，它是按照频率排序的，频率低的在下面，频率高的在上
 
 
完成了哈夫曼树，我们还需要生成字典，即如何访问各个节点。我们可以将所有的左子树的分支用0标示，右子树用1标示
 
 这样我们就完成了字典
 
 这样我们可以用0 标示YY,111标示 WW…
 经过这样的压缩后，原本的字符可以表示为如下的形式
 
 这样原来的48字节我们用14位就能表示了！！! (48字节=48 X 8位 = 384 位）
 
 
当然，只保存14位的数据是没有意义的，我们需要将字典也保存下来才能知道表示的信息
 
 加上字典信息后我们需要30字节的空间，仍然比48字节好很多。
 

首先需要借助一个堆 
 Heap.hpp
 
#pragma once
#include<iostream>
#include<vector>
#include<assert.h>

template<class T>
class Greater
{
public:
    bool operator()(const T&left, const T&right) const
    {
        return left > right;
    }
};

template<class T>
class Less
{
public:
    bool operator()(const T&left, const T&right) const
    {
        return left < right;
    }
};



template<class T, class Compare = Less<T> >
class Heap
{
public:
    Heap(){}
    Heap(const T* arr, size_t size)
    {
        assert(arr);
        for (size_t i = 0; i < size; ++i)
        {
            _heap.push_back(arr[i]);
        }
        size_t root = _heap.size() / 2 - 1;
        for (int i = root; i >= 0; --i)
        {
            _adjustDown(i);
        }
    }

    size_t Size()
    {
        return _heap.size();
    }

    bool Empty()
    {
        if (_heap.size())
            return 1;
        return 0;
    }

    const T& Top()const
    {
        assert(_heap.size());
        return _heap[0];
    }

    void Insert(const T&data)
    {
        _heap.push_back(data);
        if (_heap.size() > 1)
        {
            size_t child = _heap.size() - 1;
            _adjustUp(child);
        }
    }

    void Print()
    {
        assert(!_heap.empty());
        for (size_t i = 0; i < _heap.size(); ++i)
        {
            std::cout << _heap[i] << " ";
        }
        std::cout << std::endl;
    }

    void Pop()
    {
        assert(!_heap.empty());
        if (_heap.size() > 1)
        {
            _heap[0] = _heap[_heap.size() - 1];
            _heap.pop_back();
            _adjustDown(0);
        }
        else
        {
            _heap.pop_back();
        }
    }

private:
    void _adjustUp(size_t child)
    {
        size_t root = (child - 1) / 2;
        while ((child>0) && (Compare()(_heap[child], _heap[root])))
        {
            std::swap(_heap[child], _heap[root]);
            child = root;
            root = (root - 1) / 2;
        }
    }

    void _adjustDown(size_t root)
    {
        size_t child = root * 2 + 1;
        while (child<_heap.size())
        {
            if (((child + 1)<_heap.size()) && (Compare()(_heap[child + 1], _heap[child])))
            {
                child = child + 1;
            }
            if (Compare()(_heap[child], _heap[root]))
            {
                std::swap(_heap[root], _heap[child]);
            }
            root = child;
            child = child * 2 + 1;
        }

    }
private:
    std::vector< T > _heap;
};

 
其次需要借助哈夫曼树 HuffmanTree.hpp
 
#pragma once
#include"Heap.hpp"
#include<queue>

template<class T>
class Compare
{
public:
    bool operator()(T left, T right)
    {
        return left->_weight < right->_weight;
    }
};


template<class T>
struct HuffmanTreeNode
{
    HuffmanTreeNode(const T &weight)
    :_weight(weight)
    , pleft(NULL)
    , pright(NULL)
    , parent(NULL)
    {}
    T _weight;
    HuffmanTreeNode* pleft;
    HuffmanTreeNode* pright;
    HuffmanTreeNode* parent;
};


template<class T>
class HuffmanTree
{
public:
    HuffmanTree(){}
    HuffmanTree(T* WeightList, int size, T invalid)
    {
        assert(WeightList);
        Heap< HuffmanTreeNode<T>*, Compare<HuffmanTreeNode<T>* > > heap;
        for (int i = 0; i < size; ++i)
        {
            if (WeightList[i] != invalid)
            {
                HuffmanTreeNode<T>* node = new HuffmanTreeNode<T>(WeightList[i]);
                heap.Insert(node);
            }
        }
        HuffmanTreeNode<T>* parent = NULL;
        while (heap.Size()>1)
        {
            HuffmanTreeNode<T>* left = heap.Top();
            heap.Pop();
            HuffmanTreeNode<T>* right = heap.Top();
            heap.Pop();

            parent = new HuffmanTreeNode<T>(left->_weight + right->_weight);
            parent->pleft = left;
            parent->pright = right;
            left->parent = parent;
            right->parent = parent;
            heap.Insert(parent);
        }
        proot = parent;
    }

    void showLeavelOrder()
    {
        assert(proot);
        showLeavelOrder(proot);
    }
    ~HuffmanTree()
    {
        DestroyNodes(proot);
    }

    HuffmanTreeNode<T>* GetRoot()
    {
        return proot;
    }
private:
    void showLeavelOrder(HuffmanTreeNode<T>* root)
    {
        std::queue<HuffmanTreeNode<T>*> Q;
        Q.push(root);
        while (!Q.empty())
        {
            HuffmanTreeNode<T>* TMP = Q.front();
            std::cout << TMP->_weight << "  ";
            Q.pop();
            if (TMP->pleft)
                Q.push(TMP->pleft);
            if (TMP->pright)
                Q.push(TMP->pright);
        }
        std::cout << std::endl;
    }
    void DestroyNodes(HuffmanTreeNode<T>* root)
    {
        if (root)
        {
            if (root->pleft)
            {
                DestroyNodes(root->pleft);
                delete root->pleft;
            }
            if (root->pright)
            {
                DestroyNodes(root->pright);
                delete root->pright;
            }
        }
        else
            return;
    }
private:
    HuffmanTreeNode<T>* proot;
};
 
FileCompress.h
 
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include"HuffmanTree.hpp"
#include<stdlib.h>

struct FileInfo
{
    FileInfo(size_t count):_count(count){}
    FileInfo(){}
    unsigned char _ch;           //字符
    std::string _strcode;             //编码
    size_t _count;               //出现次数

    FileInfo operator+(const FileInfo& fileinfo)
    {

        FileInfo ret(*this);
        ret._count += fileinfo._count;
        return ret;
    }
    bool operator<(const FileInfo& fileinfo)
    {
        return _count < fileinfo._count;
    }

    bool operator!=(const FileInfo& fileinfo) const
    {
        return fileinfo._count != _count;
    }
};


class FileCompress
{
public:
    FileCompress();

    void CompressFile(const std::string&filename);

    void UnCompressFile(const std::string&filename);

private:
    void GetUnCompressCode(FILE* fr);

    void WriteContent(const std::string&dest, const std::string src);

    void FileCompress::GetHead(std::string&StrHead, const std::string&name, const std::string src);

    void WriteHead(const std::string&name, const std::string src);

    void _GentHuffmancode(HuffmanTreeNode<FileInfo>* pRoot);//获取霍夫曼编码

    void ReadFrom(const std::string&filename, size_t size);

    std::string GetFilename(const std::string& strFilePath); //获取文件名

    std::string GetFilePostFix(const std::string& strFilePath); //获取后缀名

    FileInfo _fileInfo[256];

};
 
FileCompress.cpp
 
#include"FileCompress.h"


FileCompress::FileCompress()
{
    for (int idx = 0; idx < 256; idx++)
    {
        _fileInfo[idx]._ch = idx;
        _fileInfo[idx]._count = 0;
        _fileInfo[idx]._strcode = "";
    }
}

void FileCompress::ReadFrom(const std::string&filename, size_t size)//读文件并且添加fileinfo
{
    FILE *fr = fopen(filename.c_str(), "rb");
    assert(fr);
    unsigned char* buf = new unsigned char[1024];
    while (1)
    {
        size_t _s= fread(buf, 1, 1024, fr);
        for (size_t idx = 0; idx < _s; idx++)
        {
            _fileInfo[buf[idx]]._count++;
        }
        if (_s < 1024)
            break;
    }
    delete[] buf;
    fclose(fr);
}

void FileCompress::_GentHuffmancode(HuffmanTreeNode<FileInfo>* pRoot)
{
        if (pRoot)
        {
            _GentHuffmancode(pRoot->pleft);
            _GentHuffmancode(pRoot->pright);

            if (NULL == pRoot->pleft && NULL == pRoot->pright)
            {
                HuffmanTreeNode<FileInfo>* pParent = pRoot->parent;
                std::string& code = _fileInfo[pRoot->_weight._ch]._strcode;
                while (pParent)
                {
                    if (pParent->pleft == pRoot)
                    {
                        code += '0';
                    }

                    if (pParent->pright == pRoot)
                    {
                        code += '1';
                    }

                    pParent = pParent->parent;
                    pRoot = pRoot->parent;
                }

                std::reverse(code.begin(), code.end());
            }
        }
}

std::string FileCompress::GetFilename(const std::string& strFilePath)     //获取文件名
{
    size_t pos = strFilePath.find_last_of('\\');
    return strFilePath.substr(pos + 1, strFilePath.find_last_of('.'));
}

std::string FileCompress::GetFilePostFix(const std::string& strFilePath) //获取后缀名
{
    size_t pos = strFilePath.find_last_of('.');
    return strFilePath.substr(pos, strFilePath.length() - pos);
}

char* ITOA(size_t size,char*str)
{
    int i = 0;
    while (size != 0)
    {
        char c = size % 10 + '0';
        str[i++] = c;
        size /= 10;
    }
    str[i] = '\0';
    int len = strlen(str);
    for (int j = 0; j < len / 2; j++)
    {
        std::swap(str[j], str[len - j - 1]);

    }
    return str;
}

bool ReadLine(FILE* fr, std::string& codeInfo)
{
    assert(fr);
    char ch = fgetc(fr);
    if (EOF == ch)
        return false;

    //
    while ('\n' != ch)
    {
        codeInfo += ch;

        ch = fgetc(fr);
        if (EOF == ch)
            return false;
    }

    return true;
}

void FileCompress::GetHead(std::string&StrHead, const std::string&name, const std::string src)
{
    std::string CodeInfo;
    char count[32] = {0};
    int LineCount = 0;
    for (int idx = 0; idx < 256; idx++)
    {
        if (_fileInfo[idx]._count)
        {
            CodeInfo += _fileInfo[idx]._ch;
            CodeInfo += ',';
            ITOA(_fileInfo[idx]._count,count);
            CodeInfo += count;
            CodeInfo += '\n';
            LineCount++;

        }
    }
    StrHead += GetFilePostFix(src);
    StrHead += '\n';
    ITOA(LineCount, count);
    StrHead += count;
    StrHead += '\n';
    StrHead += CodeInfo; 

}
void FileCompress::WriteHead(const std::string&name, const std::string src)
{
    FILE *fw = fopen(name.c_str(), "wb");
    assert(fw);
    std::string StrHead;
    GetHead(StrHead,name,src);

    fwrite(StrHead.c_str(), 1, StrHead.length(), fw);//写入头部信息
    fclose(fw);
}


void FileCompress::WriteContent(const std::string&dest,const std::string src)
{

    FILE *fw = fopen(dest.c_str(), "ab");
    FILE *fr = fopen(src.c_str(), "rb");
    assert(fw);
    assert(fr);

    int pos = 0;
    char ch = 0;
    unsigned char* Wbuf = new  unsigned char[1024];
    unsigned char *Rbuf = new unsigned char[1024];
    int wrIdx = 0;
    while (true)
    {
        int _rsize = fread(Rbuf, 1, 1024, fr);
        if (_rsize == 0)
            break;
        // 1024
        for (int i = 0; i < _rsize; ++i)
        {
            std::string code = _fileInfo[Rbuf[i]]._strcode; 
            for (size_t idx = 0; idx < code.size(); ++idx)
            {
                ch <<= 1;
                pos++;
                if (code[idx] == '1')
                {
                    ch |= 1;
                }

                if (pos == 8)
                {
                    Wbuf[wrIdx++] = ch;
                    if (wrIdx == 1024)
                    {
                        // 写入文件
                        fwrite(Wbuf, 1, 1024, fw);
                        wrIdx = 0;
                    }
                    ch = 0;
                    pos = 0;
                }
            }
        }
    }

    if (wrIdx!=0&&pos < 8)
    {
        ch <<= (8 - pos);
        Wbuf[wrIdx++] = ch;
        Wbuf[wrIdx] = '\0';
        fwrite(Wbuf, 1, wrIdx, fw);
    }

    delete[] Rbuf;
    delete[] Wbuf;

    fclose(fr);
    fclose(fw);
}


void FileCompress::GetUnCompressCode(FILE* fr)
{
    std::string strLineCount;
    ReadLine(fr, strLineCount);

    int lineCount = atoi(strLineCount.c_str());

    // 读取编码信息
    std::string strCodeInfo;
    while (lineCount)
    {
        ReadLine(fr, strCodeInfo);//
        if ("" != strCodeInfo)
        {
            lineCount--;
            unsigned char ch = strCodeInfo[0];
            _fileInfo[ch]._ch = ch;
            strCodeInfo = strCodeInfo.substr(2);
            _fileInfo[ch]._count = atoi(strCodeInfo.c_str());
            strCodeInfo = "";
        }
        else
        {
            strCodeInfo += '\n';
        }
    }
}

void FileCompress::CompressFile(const std::string&filename)
{
    ReadFrom(filename, 1024);
    FileInfo invalid;
    invalid._count = 0;
    HuffmanTree<FileInfo> ht(_fileInfo, 256, invalid);
    _GentHuffmancode(ht.GetRoot());

    std::string CompressName = GetFilename(filename);
    std::string Postname = GetFilePostFix(filename);
    CompressName += ".hzp";

    WriteHead(CompressName,filename);//写入头部信息

    WriteContent(CompressName,filename);//追加压缩后的编码
}

void FileCompress::UnCompressFile(const std::string& FilePath)
{
    FILE* fr = fopen(FilePath.c_str(), "rb");
    assert(fr);

    //获取后缀
    std::string strPostFix;
    ReadLine(fr, strPostFix);

    //得到fileinfo
    GetUnCompressCode(fr);



    //用fileinfo构建Huffman树
    HuffmanTree<FileInfo> ht(_fileInfo, 256, FileInfo(0));
    HuffmanTreeNode<FileInfo>* PRoot = ht.GetRoot();


    std::string filename = GetFilename(FilePath);
    filename += strPostFix;//得到要解压的文件名及后缀

    unsigned char* Rbuf = new  unsigned char[1024];
    size_t lenth = PRoot->_weight._count;
    size_t _wsize = 0;
    int pos = 7;

    FILE* fw = fopen(filename.c_str(), "wb");
    unsigned char* Wbuf = new  unsigned char[1024];
    int _rsize = 0;
    while (true)
    {
        _rsize = fread(Rbuf, 1, 1024, fr);
        if ( _rsize == 0)
            break;
        size_t idx = 0;
        while (idx < _rsize)
        {
            if (Rbuf[idx] & 1 << pos--)
            {
                PRoot = PRoot->pright;

            }
            else
            {
                PRoot = PRoot->pleft;
            }

            if (NULL == PRoot->pleft && NULL == PRoot->pright)
                //0就往左走，1就往右走，一直走到叶子节点就是编码，然后找到编码对应的符号
            {
                Wbuf[_wsize++] = PRoot->_weight._ch;//把这个符号写进输出缓冲区
                if (1024 == _wsize&& _wsize<lenth )
                {
                    //写文件
                    fwrite(Wbuf, 1, 1024, fw);
                    lenth-=1024;
                    _wsize = 0;
                }

                PRoot = ht.GetRoot();
            }

            if (0 > pos)
            {
                ++idx;
                pos = 7;
            }
        }

    }

    if (_wsize < 1024 && lenth>0)
    {
        fwrite(Wbuf, 1, lenth, fw);
    }

    delete[] Wbuf;
    delete[] Rbuf;
    fclose(fr);
    fclose(fw);
}
 
main.cpp
 
#include"FileCompress.h"

void test()
{
    FileCompress fl;
    fl.CompressFile("Text.txt");
    fl.UnCompressFile("Text.hzp");
}

int main()
{
    test();
    system("pause");
    return 0;
}