贪心算法实现霍夫曼编解码

旧城等待， 2022-06-05 05:15 149阅读 0赞

霍夫曼编码是一种被广泛应用而且非常有效的数据压缩技术，根据待压缩数据的特征，一个可压缩掉20%~90%。这里考虑的数据指的是字符串序列。要理解霍夫曼编码，先要理解霍夫曼树，即最优二叉树，是一类带权路径长度最短的树。

路径是指从树中一个结点到另一个结点之间的通路，路径上的分支数目称为路径长度。

树的路径长度是从树根到每一个叶子之间的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与该结点权的乘积，树的带权路径长度为树中所有叶子结点的带权路径长度之和.

假设有一个包含100 000个字符的数据文件要压缩存储。各字符在该文件中的出现频度见表1。仅有6种不同字符出现过，字符a出现了45000次。

<table> 
 <tbody> 
  <tr> 
   <td> <p><span style="color:#006600">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;d&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;f</span></p> </td> 
  </tr> 
  <tr> 
   <td> <p><span style="color:#006600">频度（千字）&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;45&nbsp;&nbsp;&nbsp;&nbsp;13&nbsp;&nbsp;&nbsp;&nbsp;12&nbsp;&nbsp;&nbsp;&nbsp;16&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;9&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;5</span></p> <p><span style="color:#006600">固定代码字&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;000&nbsp;&nbsp;&nbsp;&nbsp;001&nbsp;&nbsp;&nbsp;010&nbsp;&nbsp;&nbsp;&nbsp;011&nbsp;&nbsp;&nbsp;100&nbsp;&nbsp;&nbsp;101</span></p> <p><span style="color:#006600">变长代码字&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;101&nbsp;&nbsp;&nbsp;100&nbsp;&nbsp;&nbsp;&nbsp;111&nbsp;&nbsp;&nbsp;1101&nbsp;&nbsp;1100</span></p> </td> 
  </tr> 
 </tbody> 
</table>

表1 一个字符编码问题。大小为100 000个字符的一个数据文件仅包含字符a~f，每个字符出现的频度如表中所示。如果对每个字符赋予一个三位的编码，则该文件可被编码为300000位。如果利用表中的可变长度编码，该文件可被编码为224000位。

可以用很多种方式来表示这样一个文件。采用固定长度编码，则需要三位二进制数字来表示六个字符：a=000，b=001，…，f=101。这种方法需要300 000来对整个原文件编码。

而可变长度编码是对频度高的字符赋以短编码，而对频度低的字符赋以较长一些的编码。表1显示了这种编码，其中一位串0表示a，四位串1100表示f。这种编码方式需要

（45\*1+13\*3+12\*3+16\*3+9\*4+5\*4）\*1000 = 224 000 位

来表示整个文件，即可压缩掉约25%。这其实就是最优字符编码（霍夫曼编码）

**前缀编码**

我们这里考虑的编码方案中，没有一个编码是另一个编码的前缀。这样的编码称为前缀编码（或许“无前缀编码“是个更好的名字，但是前缀编码是标准的书面语）。

对任何一种二进制字符编码来说编码总是简单的，这只要将文件中表示每个字符的编码并置起来即可。利用表1的可变长度编码，把包含三个字符的文件abc编成

0 . 101 . 100 = 0 101 100,其中“.“表示并置。

在前缀编码中解码也是很方便的。因为没有一个码是其他码的前缀，故被编码文件的开始处的编码是确定的。我们只要识别出第一个编码，将它翻译成原文字符，再对余下的编码文件重复这个解码过程即可。在我们的例子中，可将串001 011 101唯一地分析为0.0.101.1101，因此可解码为aabe。

下面是一个代码实例，实现了霍夫曼编码和解码功能：

#include <iostream>
    #include <list>
    #include <stack>
    #include <vector>
    #define N 6
    using namespace std;
    char C[] = {'f','e','c','b','d','a'};//字符集合
    int F[] = {5, 9, 12, 13, 16, 45};//出现频率
    
    
    typedef struct node
    {
        char ch;
        bool inCode;
        int priority;
        node *left;
        node *right;
        node *parent;
        
    }Node;
    
    void insertAsPriorityList(list<node*> &priorityList, Node * node);
    
    void insertAsPriorityList(list<node*> &priorityList, Node * node)//维护一个优先级队列,这里参数一定要用引用形式
    {
        
        std::list<Node*>::iterator it = priorityList.begin();
        while (it != priorityList.end() && (*it)->priority < node->priority)
            ++ it;
        priorityList.insert(it, node);
        
        
    }
    
    void HuffmanEncode( Node * root);
    
    void HuffmanEncode( Node * leaf)//实现霍夫曼编码
    {
        //使用回溯的方法得到霍夫曼编码
        char ch = leaf->ch;
        stack<bool> isOne;
        while (leaf->parent) 
        {
            if (leaf == leaf->parent->left)
                isOne.push(false);
            else
                isOne.push(true);
            leaf = leaf->parent;
        }
        cout <<ch<<" 的编码是： ";
        while (!isOne.empty()) 
        {
            cout << isOne.top();
            isOne.pop();
        }
        cout << endl;
    }
    
    void HuffmanDecode(vector<bool> &code , Node *root);
    void HuffmanDecode(vector<bool> &code , Node *root)//霍夫曼解码
    {
        vector<char> chs;
        
        int i = 0;
        while (i < code.size()) {
            Node *temp = root;
            while (temp->left != NULL && temp->right != NULL && i < code.size()) {
                if (code[i])
                    temp = temp->right;
                else
                    temp = temp->left;
                ++ i;
            }
            
            if (temp->left == NULL && temp->right == NULL)
                chs.push_back(temp->ch);
            else
            {
                cout <<"编码出错！"<<endl;
                return;
            }
        }
        for (i =0; i < code.size(); ++ i )
            cout << code[i];
        
        cout << " 的解码结果是："<<endl;
        for (i =0 ; i < chs.size(); ++ i) {
            cout << chs[i] << " ";
        }
        cout <<endl;
    }
    
    void clearTree(Node * root);
    void clearTree(Node * root)
    {
        //释放空间
        if (!root -> left && !root->right)
        {
            delete root;
            root = NULL;
        }
        else
        {
            clearTree(root->left);
            clearTree(root->right);
            delete  root;
        }
    }
    
    int main(int argc, char **argv)
    {
    
        list<bool> huffCode;//用来记录霍夫曼编码
        list<node*> HuffmanList;
        list<node*> leaf;//保存叶子节点
        for (int i = 0; i < N; ++ i)
        {
            Node *tempPtr = new Node();
            tempPtr->ch = C[i];
            tempPtr->priority = F[i];
            tempPtr->left = tempPtr->right = tempPtr->parent = NULL;
            insertAsPriorityList(HuffmanList, tempPtr);
            leaf.push_back(tempPtr);
        }
        
        //进行霍夫曼编码
        while (HuffmanList.size() > 1) {
            Node *ptr1, *ptr2;
            ptr1 = HuffmanList.front();
            HuffmanList.pop_front();
            ptr2 = HuffmanList.front();
            HuffmanList.pop_front();
            
            Node *newPtr = new Node();
            newPtr->priority = ptr1->priority + ptr2->priority;
            newPtr->left = ptr1;
            newPtr->right = ptr2;
            newPtr->parent = NULL;
            ptr1->parent = ptr2->parent = newPtr;
            insertAsPriorityList(HuffmanList, newPtr);
        }
        
        
        while (!leaf.empty()) {
            HuffmanEncode(leaf.front());
            leaf.pop_front();
        }
        cout << endl;
        
        vector<bool> codes;
        codes.push_back(0);//a
        
        codes.push_back(1);//b
        codes.push_back(0);
        codes.push_back(1);
        
        codes.push_back(1);//c
        codes.push_back(0);
        codes.push_back(0);
        
        codes.push_back(1);//d
        codes.push_back(1);
        codes.push_back(1);
        
        codes.push_back(1);//e
        codes.push_back(1);
        codes.push_back(0);
        codes.push_back(1);
        
        codes.push_back(1);//f
        codes.push_back(1);
        codes.push_back(0);
        codes.push_back(0);
        
        HuffmanDecode(codes, HuffmanList.front());
        
        
        clearTree(HuffmanList.front());
     
    
            
        return 0;
    }

程序的运行结果如下：

**f** **的编码是：** **1100**

**e** **的编码是：** **1101**

**c** **的编码是：** **100**

**b** **的编码是：** **101**

**d** **的编码是：** **111**

**a** **的编码是：** **0**

**010110011111011100** **的解码结果是：**

**a b c d e f**