精华内容
下载资源
问答
  • 哈夫曼编码压缩文件

    2012-07-09 02:57:00
    用Java实现,哈夫曼编码实现文件压缩,有详细注释
  • 利用二叉树哈夫曼编码实现对文件压缩以及解压缩
  • 通过哈夫曼编码压缩文件

    千次阅读 2018-10-11 15:04:06
    原理就是统计带压缩文件字符频率,构建哈夫曼树,然后求哈夫曼编码,将字符频率(解压的时候通过字符频率建树)和哈夫曼编码写入文件,完成压缩。 压缩代码: //获取一个文件的每个字符的频率 void get_frequency...

    原理就是统计带压缩文件字符频率,构建哈夫曼树,然后求哈夫曼编码,将字符频率(解压的时候通过字符频率建树)和哈夫曼编码写入文件,完成压缩。

    压缩代码:

    //获取一个文件的每个字符的频率
    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;
    }
    

    效果如下

    展开全文
  • 哈夫曼编码和解码代码,利用哈夫曼编码压缩和解压文件的小工具。
  • 哈夫曼编码压缩文件

    热门讨论 2012-05-09 15:57:03
    可以对文件进行压缩和解压缩,支持2种压缩算法,文件名称和压缩模式在命令行参数设置。内有编译好的执行文件,测试结果,数据文件,比较详细的使用说明和注释。程序使用c语言编写,未使用任何第三方库。在某些情况下...
  • 采用哈夫曼编码文件进行压缩解压。先将文件各字节读出,统计频率。进行哈夫曼编码,将编码重新写入文件。 编码命令:c <input file> 解码命令:d <input file> 对于编码的output file和解码的input file可以...
  • //创建字节数组,接收读取的 经过哈夫曼编码后的 字节数组 byte[] huffmanBytes = (byte[])ois.readObject(); //创建map集合 接收读取的 哈夫曼编码 Map,String> huffmanCode = (Map,String>)ois.readObject(); //...
    代码
    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的课程,做下笔记,原视频在这里 ↓ ... 我们要对如下一张 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字节好很多。

    展开全文
  • C++:利用哈夫曼编码压缩文件

    千次阅读 2016-08-13 23:05:13
    C++,堆heap,哈夫曼树,Huffman,文件压缩编码

    首先需要借助一个堆
    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;
    }
    展开全文
  • 利用哈夫曼编码压缩文件

    千次阅读 2017-09-05 17:54:48
    本大作业主要考核如何以C实现集成电路测试向量文件的无损压缩。在通常的文件存储中,无论是二进制格式的文件还是文本文件,几乎都是等宽的编码。比如ASCII码格式的文本文件,每个字符由一个ASCII码表示,宽度为8bit...
  • 哈夫曼编码是一种编码格式,属于可变字长编码的一种,该方法依照字符出现的概率来构建异字头的平均长度最短的码字,最终实现根据使用频率来最大化节省码字(字符)的存储空间和提高传输效率的目的,在数据压缩和通讯...
  • 一、运行环境: Win7、python3.7 二、运行过程说明: 数据文件格式:txt、docx、csv、doc、pdf、xls等任意格式的文件。 输入格式:首先,在cmd中进入代码所在的目录;...压缩文件:python main.py 0 ...
  • 使用哈夫曼编码统计字符的频率作为权值来实现压缩技术 ,包括哈夫曼树的创建,构造哈夫曼编码,使用哈夫曼编码压缩文件,和解压文件
  • 哈夫曼树压缩文件与解压文件,统计字符频率与对应的哈夫曼编码,注释超详细
  • 本文采用哈夫曼编码的方式进行文件(文本文件)压缩和解压缩,首先介绍项目的整体思路:哈夫曼编码压缩文件实际就是统计出文件中各个字符出现的频率,然后为每个字符生成对应的编码,然后将每个字符用哈夫曼编码的...
  • 文件目录 binaryTreeNode.h linkedBinaryTree.h 源.cpp 代码如下 binaryTreeNode.h #ifndef binaryTreeNode_ #define binaryTreeNode_ #include #include #include using namespace std; template struct ...
  • 使用哈夫曼编码压缩文件,其实就是将每个字符的哈夫曼编码得到,每8位转为一个字节存到文件中,解压缩的时候,在将字节转为二进制重新找到哈夫曼编码对应的字符,这样即可完成文件的解压缩。 文件解压缩的方法: ①...
  • 哈夫曼编码实现文本文件压缩,可作为数据压缩作业的参考
  • 运用哈夫曼编码压缩解压文件源代码,代码有详细的注释,很好的压缩解压的源代码
  • 哈夫曼编码-文件压缩

    2012-11-25 17:31:14
    哈夫曼编码-文件压缩,数据结构作业,C语言 用哈夫曼树对ASCII文件进行压缩,编码后得到实际压缩文件,同时还有解码功能,界面的效果 文件夹中含程序的多个版本,分别是代表程序编写是的不同阶段 程序使用C编写,...
  • 利用哈夫曼编码思想,设计对一个文本文件(.txt)中的字符进行哈夫曼编码,生成编码压缩文件(.txt),并且还可将压缩后的文件进行解码还原为原始文本文件(.txt)。 实现的功能: (1)压缩:实现对文件的压缩,生成...
  • 基于huffman哈夫曼编码文件进行压缩和解压缩

空空如也

空空如也

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

哈夫曼编码压缩文件