哈夫曼树与哈夫曼编码

data_structure

一、概念

哈夫曼树（Huffman tree），又名最优树，指给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。

二、想法

2.1、节点结构

哈夫曼树的节点中应该存在数据，权重，双亲以及左右孩子，
所以节点构造如下：

template <class T> 
struct HuffmanNode
{
    T data;                 //数据 
    double weight;          //符号出现的频率
    int parent;             //双亲结点的坐标
    int lchild;             //左孩子的坐标
    int rchild;             //右孩子的坐标
};

2.2、哈夫曼树结构及树的构造方法

我们先说，如何去构造一个哈夫曼树，应该是根据权值的不同，每次找到两个小值，把他们两个拼凑起来，其中，权值应该是通过统计得到的，后面会提到方法，这边暂且假设已经得到。

template<class T>
class HuffmanTree  
{
    ……………………
private:
    vector<HuffmanNode<T> > huffmantree;    //huffmantree所有节点的存储空间
    int n;          //叶子结点数
};

哈夫曼树，接受一个存有所有叶子节点的向量，根据这些向量，来构造一棵树，我们知道，n个叶子节点，最后会生成2n-1个节点，所以需要先resize树向量。然后把huffmantree里面初值赋完，接下来，我们要找两个权值最小和次小的节点，并用这两个节点信息生成新的节点，填入。

template<class T>
HuffmanTree<T>::HuffmanTree(vector<HuffmanNode<T> > &leafs)
{
    n = leafs.size();   //叶子节点个数赋值给n;
    huffmantree.resize(2*n-1);  //为为分支结点预留向量空间
    for (int i=0;i<n;i++)
    {
        huffmantree[i].data=leafs[i].data;
        huffmantree[i].weight=leafs[i].weight;
        huffmantree[i].parent=huffmantree[i].lchild=huffmantree[i].rchild=-1;
    }
    int least, less;  //最小数 次小数的下标
    for( i=n; i<2*n-1; i++)
    {
        SelectSmall(least, less, i); //找到最小值 次小值的结点下标
        //由之前的两个最小值生成新结点，
        huffmantree[least].parent = huffmantree[less].parent = i;//原2个节点的父节点置值
        huffmantree[i].data = i;//并没什么作用。。后面输出也会被过滤
        huffmantree[i].parent = -1;
        huffmantree[i].lchild = least;
        huffmantree[i].rchild = less;
        huffmantree[i].weight = huffmantree[least].weight + huffmantree[less].weight;
    }
}

2.3、找最小值以及次小值

下面介绍一下，如何找到最小值和次小值：
首先，只有没有被用过的节点才有比较的资格，也就是父节点为-1的才能参与比较，每轮比较，我们从头开始循环.循环判断过程如下

• 父节点是否为-1
  

  
  
  • 当当前值比最小值小
    

    
    
    • 那么先把原先的最小值抛给最小值，并保存次小值序号，
    • 更新最小值及序号。

  • 当前值大于等于最小值，且小于次小值
    

    • 更新次小值及其序号

template<class T>
void HuffmanTree<T>::SelectSmall(int &least,int &less,int i)
{
    least = less = 0;
    int min1 = INT_MAX;
    int min2 = INT_MAX;
    for(int j=0; j<i; j++)
    {
        if(huffmantree[j].parent == -1)     //当没有父节点才有资格比较
        {//筛选没有父结点的最小值和次小值
            if(huffmantree[j].weight<min1)
            {//如果比最小值小
                min2 = min1;    //把原来的最小值先抛给次小
                less = least;   //保存次小值的序号
                min1 = huffmantree[j].weight;//保存最小值
                least = j;  //能保存最小值序号
            }
            else if((huffmantree[j].weight>=min1)&&(huffmantree[j].weight<min2))
            {//如果大于等于最小值，且小于次小值
                min2 = huffmantree[j].weight;
                less = j;
            }
        }
    }
}

2.4、频率统计

上面的构造函数，是根据所给的含有频率信息的HuffmanNode数组构造数，下面，我来介绍一下，对于ASCII码的字符（非汉字）如何统计。
思路如下，因为ASCII码值，不超过256个，所以，可以建立一个大小为256的int数组，初值置为0，遍历字符串，遇到一个，对应值加1，可以达到简单的统计效果，键值就是0~256，内容就是出现的次数。

    int frequency[256];//用于记录每个ASCII出现的次数
    memset(frequency,0,sizeof(frequency));
    for (int i = 0; i < rst.length(); i++)
        frequency[rst[i]]++;    //每出现一次，次数加1
    for ( i = 0; i < 256; i++)
    {
        if (frequency[i] != 0)
        {
            weight.push_back(frequency[i]*1.0/rst.length()*100);        //当频率不为0的时候，压入权重向量//这个做了个规约处理
            s.push_back(i);                                         //同时把字符对应的ASCII值存到S向量
        }
    }
    for ( i = 0; i < s.size(); i++)                                 //把组织好的值压入向量中，供构造树。
    {
        HuffmanNode<char> tmp={ s[i], weight[i], -1, -1, -1 };
        huffnode.push_back(tmp);
    }
    HuffmanNode<char> *hn=new HuffmanNode<char> [s.size()];
    for (i=0;i<s.size();i++)
    {
        hn[i]=huffnode[i];
    }

这个统计字频的思路很简单，但是对于中文是完全无效的，算是缺陷。这边在频率统计完了之后，顺便构造了Node数组，便于后面构造树。

2.5、生成编码字符串

首先，我们要对这棵哈夫曼树的叶子节点编码，得到每个叶子节点的码值，然后在读取源码，生成对应的01编码。
编码的原理，就是从当前节点向前回溯，如是其父节点的左孩子插入1，相反插0；知道根节点停止。

template<class T>
vector<int> HuffmanTree<T>::GetCode(int i)
{
    vector<int> code;
    int parent;
    parent = huffmantree[i].parent;   //先获得父节点的下标找到父节点
    while(parent != -1)  //parent == -1 时，表明已经到了根节点了
    {
        if(i == huffmantree[parent].lchild)
            code.insert(code.begin(), 0);
        else
            code.insert(code.begin(), 1);
        i = parent;  //把父节点换成当前的子节点
        parent = huffmantree[i].parent;  //沿父指针上溯
    }
    return code;
}

编码函数：

    //编码,并把结果存在codes向量里面，并用hash表存储，便于读取
    int hash[256];  
    memset(hash,-1,sizeof(hash));
    vector<string> codes;
    vector<int> code;
    cout<<endl<<"字符编码如下："<<endl;
    for( i=0; i<HT.GetN(); i++)
    {
        char c=HT.GetData(i);       cout<<c<<":   ";
        hash[c]=i;
        code = HT.GetCode(i);
        string tmp;
        for(int j=0; j<code.size(); j++)
            tmp+=(char)(code[j]+48);
        codes.push_back(tmp);
        cout<<tmp<<endl;
    }

下面是生成编码字符串

    string res;
    for ( i=0;i<rst.length();i++)
    {
        char c=rst.at(i);
        res+=codes[hash[c]];
    }
    ofstream out;
    out.open("code.txt");
    out<<res;
    out.close();
    cout<<endl<<"编译码已经写入code.txt!"<<endl;

2.6、解码

根据01编码进行解码。

template<class T>    
void HuffmanTree<T>::DeCode(string source)
{
    int root = huffmantree.size()-1;   //获得根节点下标
    int p = root;   //p为当前结点的下标
    for(int i=0; i<source.size(); i++)
    {
        if(source.at(i) == '0')
            p = huffmantree[p].lchild;
        else
            p = huffmantree[p].rchild;
        if( (huffmantree[p].lchild == -1) && (huffmantree[p].rchild == -1) )  //如果到了叶子节点 
        {
            cout<<huffmantree[p].data;
            p = root;   //当前结点再次是根结点
        }
    }
}

    //下面是译码
    cout<<endl<<"译码结果："<<endl;
    HT.DeCode(res);
    cout<<endl;

2.7、打印

为了方便查看哈夫曼树的结构，设计了这个方法：

template<class T>
void HuffmanTree<T>::Print()
{
    cout<<"编号"<<"\t"<<"符号"<<"\t"<<"频率"<<"\t"<<"父结点"<<"\t"<<"左孩子"<<"\t"<<"右孩子"<<endl;
    for(int i=0; i<2*n-1; i++)
    {
        cout<<i<<"\t";
        if (i<n)
        {   
            cout<<huffmantree[i].data<<"\t";
        }
        else
        {
            cout<<"\t";
        }
        cout<<setprecision(4)<<huffmantree[i].weight<<"%"<<"\t";
        cout<<huffmantree[i].parent<<"\t";
        cout<<huffmantree[i].lchild<<"\t";
        cout<<huffmantree[i].rchild<<"\t";
        cout<<endl;
    }
}

2.8、保存哈夫曼树

为了讲编码翻译成源码，需要有哈夫曼树的存在，本来可以用对象的序列化存为二进制文件更加安全的，这边还是用文件的写保存。

template<class T>
void HuffmanTree<T>::Save(char *fname)
{
    ofstream out;
    out.open(fname);
    out<<n<<endl;
    for(int i=0; i<2*n-1; i++)
    {
        if (i<n)
        {   
            out<<huffmantree[i].data<<"\t";
        }
        else
        {
            out<<0<<"\t";
        }
        out<<setprecision(4)<<huffmantree[i].weight<<"\t";
        out<<huffmantree[i].parent<<"\t";
        out<<huffmantree[i].lchild<<"\t";
        out<<huffmantree[i].rchild<<"\t";
        out<<endl;
    }
    out.close();
    cout<<endl<<"该树已经写入"<<fname<<endl;
}

2.9、还原哈夫曼树

也就是按照文件读入来构造哈夫曼树，实质上是构造函数，可能对于后于需要的其他功能提供方便。

template<class T>
HuffmanTree<T>::HuffmanTree(char *fname)
{
    ifstream in;
    in.open(fname);
    in>>n;   //叶子节点个数赋值给n;
    huffmantree.resize(2*n-1);  //为为分支结点预留向量空间
    for(int i=0; i<2*n-1; i++)
    {
        char c;
        in>>c;
        if (c!='0')
        {
            huffmantree[i].data = c;
        }
        in>>huffmantree[i].weight;
        in>>huffmantree[i].parent;
        in>>huffmantree[i].lchild;
        in>>huffmantree[i].rchild;
    }
}

三、测试函数

int main()
{
    //统计字频
    vector<char> s;     //字符集
    vector<double> weight;//每个字符个数
    vector<HuffmanNode<char> > huffnode;//存每个结点
    string rst;
    ifstream in;
    cout<<"字符串内容来源于data.txt!"<<endl;
    in.open("data.txt");
    string tmp;
    while(getline(in,tmp))
    {
        rst+=tmp;
    }
    in.close();
    //cout << "请输入一个字符串：";
    //cin >> rst;
    //对rst做频率统计
    int frequency[256];//用于记录每个ASCII出现的次数
    memset(frequency,0,sizeof(frequency));
    for (int i = 0; i < rst.length(); i++)
        frequency[rst[i]]++;    //每出现一次，次数加1
    for ( i = 0; i < 255; i++)
    {
        if (frequency[i] != 0)
        {
            weight.push_back(frequency[i]*1.0/rst.length()*100);        //当频率不为0的时候，压入权重向量//这个做了个规约处理
            s.push_back(i);                                         //同时把字符对应的ASCII值存到S向量
        }
    }
    for ( i = 0; i < s.size(); i++)                                 //把组织好的值压入向量中，供构造树。
    {
        HuffmanNode<char> tmp={ s[i], weight[i], -1, -1, -1 };
        huffnode.push_back(tmp);
    }
    HuffmanNode<char> *hn=new HuffmanNode<char> [s.size()];
    for (i=0;i<s.size();i++)
    {
        hn[i]=huffnode[i];
    }
    //建树
    vector< HuffmanNode<char> > leafs(hn,hn+s.size());
    HuffmanTree<char> HT(leafs);
    cout<<"此哈夫曼树存储结构如下："<<endl;
    HT.Print();
    //编码,并把结果存在codes向量里面，并用hash表存储，便于读取
    int hash[256];  //存的是字符对应在codes的位置。
    memset(hash,-1,sizeof(hash));
    vector<string> codes;//存的是字符对应的码值
    vector<int> code;
    cout<<endl<<"字符编码如下："<<endl;
    for( i=0; i<HT.GetN(); i++)
    {
        char c=HT.GetData(i);       cout<<c<<":   ";
        hash[c]=i;
        code = HT.GetCode(i);
        string tmp;
        for(int j=0; j<code.size(); j++)
            tmp+=(char)(code[j]+48);
        codes.push_back(tmp);
        cout<<tmp<<endl;
    }
    //下面是生成编码字符串
    string res;
    for ( i=0;i<rst.length();i++)
    {
        char c=rst.at(i);
        res+=codes[hash[c]];
    }
    ofstream out;
    out.open("code.txt");
    out<<res;
    out.close();
    cout<<endl<<"编译码已经写入code.txt!"<<endl;
    //下面是译码
    cout<<endl<<"译码结果："<<endl;
    HT.DeCode(res);
    cout<<endl;
    delete hn;
    return 0;
}

测试一：提供源码文件，统计频率，输出编码，并译码。

    HuffmanTree<char> ht("MyTree.txt");
    ht.Print();
    cout<<endl;
    string code;
    ifstream in;
    in.open("code.txt");
    string tmp;
    while(getline(in,tmp))
    {
        code+=tmp;
    }
    in.close();
    ht.DeCode(code);
    cout<<endl;

测试二：提供哈夫曼树，提供编码，译码（有误？）

这边空格被误识别，原因未知。