贪心策略-哈弗曼编码

问题描述

哈夫曼编码是用于数据文件压缩的一个非常有效的编码方法。其压缩率通常在20%到90%之间。哈夫曼算法使用一个字符在一个文件中出现的频率表来建立一个用0,1串表示各字符的最有表示方法，试图以最少的01串表示出现频率最高的字符，以较长的01串表示出现频率较低的字符，以降低整个文件的存储空间。

前缀码概念：

我们对每一个字符规定一个01串作为其代码，并要求任意01串都不是其他字符代码的前缀。我们称这样的编码为前缀码。前缀码会使译码变得非常简单，由于任意字符的代码都不是其他字符代码的前缀，所以从编码文件中不断取出代表某一字符的前缀码，转换为原字符，即可逐个译出文件中的所有字符。由于哈夫曼编码是一种变长码所以哈夫曼码也被要求是前缀码。

容易看出，二叉树是表示前缀码的最有数据结构，而且表示前缀码的二叉树的任意一个节点如果有儿子，那么一定有两个儿子，否则就没有儿子（王晓东的书上说一定是一颗完全二叉树，我个人认为是不对的）。对n个字符进行编码的前缀码二叉树有n个叶子节点和n-1个内部节点。

给定编码字符集C及其频率分布f，C的一个前缀编码方案对应一个前缀码二叉树T，设字符c在前缀码二叉树T中的深度为d，则该编码方案的平均码长定义为：B(T)= ∑f(i)*d(i)，

使平均码长达到最小的前缀码编码方案称为C的一个最优前缀编码

哈夫曼编码是一种最优前缀编码。

算法思考

哈夫曼编码具有贪心选择性质

证明：

1、贪心选择性质  
易证字符编码集C中，最小频率的两个字符x和y，
则最优前缀编码一定使x和y具有相同的码长且仅最后一位编码不同。

2、最优子结构性质  
设T是表示字符集C中的一个最优前缀编码的完全二叉树。
C中的字符频率表位f(c)，设x和y是树T中的两个互为兄弟的叶子节点，
z是他们的父亲，若将z的频率设为f(x)+f(y)则，
易证字符集C’=C-{x,y}U{z}的一个最优前缀编码是T’=T-{x,y}

哈夫曼算法：

首先我们视字符集C中的每一个字符皆为一颗树，利用优先队列，每次选出字符集C中的频率最小的两个元素，即两颗树，并构成一课新树，新树的频率为两颗子树频率之和，然后将两颗子树从C中删去，并将新树加入到C中，重复进行n-1次则字符C中只剩下一颗树，此树即为哈夫曼树，每个叶子节点为字符集C中的字符，其编码为从根到该叶子节点的路径上的权值，生成左儿子的边的权值为0，右儿子的为1。

逸闻趣事

1951年，哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是，寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。

由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。哈夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。

代码实现

#include <stdio.h>
#include <cstdlib>
#include <queue>
#include <iostream>
#include <string>
#include <stack>
using namespace std;
struct treenode{
    int f;
    char c;
    struct treenode *left;
    struct treenode *right;
};
typedef treenode* btree;
void init(btree &bt,int ff,char cc)
{
    if(!(bt=(btree)malloc(sizeof(treenode))))
        exit(0);
    bt->f=ff;
    bt->c=cc;
    bt->left=NULL;
    bt->right=NULL;
}
btree merge(btree t1,btree t2)
{
    btree bt=(btree)malloc(sizeof(struct treenode));
    bt->f=t1->f+t2->f;
    bt->c=' ';
    bt->left=t1;
    bt->right=t2;
    return bt;
}
struct node{
    btree tree;
    //node(char cc,int ff){c=cc;f=ff;}
    friend bool operator < ( node n1,node n2)
    {
        return n1.tree->f > n2.tree->f;
//此处我为了偷懒，将小于号改成了大于号实现了优先队列大数优先向小数优先的转换，
//实际上这么写是不规范的
    }

};
priority_queue<node> q;
void in()
{
    int ff;
    char cc;
    printf("please putin the alphabet and the frequency(end with ?,0)\n");
    while(true)
    {
        scanf("%c %d",&cc,&ff);
        getchar();
        if(ff==0)
            break;
        node temp;
        init(temp.tree,ff,cc);
        q.push(temp);
    }
}
void huffman()
{
    int i;
    int n=q.size();
    node n1,n2;
    btree bt;
    for(i=1;i<n;++i)
    {
        n1=q.top();
        q.pop();
        n2=q.top();
        q.pop();
        bt=merge(n1.tree,n2.tree);
        n1.tree=bt;
        q.push(n1);
    }
}
void outn(int n,int n0)
{
    stack<int> s;
    int i,m;
    if(0==n)
    {
        for(i=0;i<n0;++i)
            printf("0");
        printf("\n");
    }
    else
    {
        while(n)
        {
            m=n%2;
            s.push(m);
            if(m==0)
                n0--;
            n=n/2;
        }
        for(i=0;i<n0;++i)
            printf("0");
        while(!s.empty())
        {
            cout<<s.top();
            s.pop();
        }
        printf("\n");
    }
}
void traverse(btree bt,int n,int n0)
//其中n0记录该字符哈夫曼编码中0的个数，因为为了简便，
//我用十进制数来存储哈夫曼编码，
//然后转换成二进制输出，但是当十进制转换成二进制时为了让前导0也会输出（比如w我们）
//应该输出001而不是1），所以需要记录0的个数来输出前导0
{
    if(bt->left==NULL && bt->right==NULL)
    {
        printf("%c %d ",bt->c,bt->f);
        outn(n,n0);
    }
    else
    {
        if(bt->left!=NULL)
            traverse(bt->left,2*n,n0+1);
        if(bt->right!=NULL)
            traverse(bt->right,2*n+1,n0);
    }
}
void out()
{
    node n=q.top();
    traverse(n.tree,0,0);
}
int main()
{
    in();
    huffman();
    out();
    return 0;
}