哈夫曼树与编码译码实现


一、哈弗曼树的基本概念。

哈夫曼树，又称最优树，是一类带权路径长度最短的树。下面有几个概念：

（1）路径。

树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。

（2）路径长度。

路径上的分枝数目。

（3）树的路径长度。

从树根到每一个结点的路径长度之和。

（4）结点的带权路径长度。

从该结点到树根之间的路径长度与结点上权的乘积。

（5）树的带权路径长度。

树中所有叶子节点的带权路径长度之和。通常记作：

带权路径长度WPL最小的二叉树叫做最优二叉树或哈夫曼树。

二、构造哈夫曼树。

采用哈夫曼法算法构造过程为：

（1）根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn},其中每棵树Ti中只有一个带权为wi的根结点，其左右子树均空。

（2）在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。

（3）在F中删除这两棵树，同时将新得到的二叉树加入到F中。

（4）重复（2）和（3），直到F只含一棵树为止。

例如权值为7,5,2,4的结点构造过程为：

------------------------------分割线------------------------------

C++ Primer Plus 第6版 中文版 清晰有书签PDF+源代码

读C++ Primer 之构造函数陷阱

读C++ Primer 之智能指针

读C++ Primer 之句柄类

将C语言梳理一下，分布在以下10个章节中：

  1. Linux-C成长之路（一）：Linux下C编程概要
  2. Linux-C成长之路（二）：基本数据类型
  3. Linux-C成长之路（三）：基本IO函数操作
  4. Linux-C成长之路（四）：运算符
  5. Linux-C成长之路（五）：控制流
  6. Linux-C成长之路（六）：函数要义
  7. Linux-C成长之路（七）：数组与指针
  8. Linux-C成长之路（八）：存储类，动态内存
  9. Linux-C成长之路（九）：复合数据类型
  10. Linux-C成长之路（十）：其他高级议题

三、编码和编码树。

1、等长编码和不等长编码。

（1）等长编码。

每个字符的编码长度相同（每个编码所含的二进制位数相同）。特点是编（译）码容易，抗干扰能力强，但长度不是最短，效率低。

（2）不等长编码。

与等长编码相对，效率高。若要设计长短不等的编码（考虑译码唯一性），则必须是任一个字符的编码都不是另一个字符的编码的前缀，这种编码称作前缀编码。

2、哈夫曼编码。

考虑利用二叉树来设计二进制的前缀编码。约定左分支表示字符0，右分支表示字符1，从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码，可以证明得到的必为二进制前缀码。

考虑如何得到使电文长度最短的二进制前缀编码。可以看出，设计电文总长最短的二进制前缀编码即以n种字符出现的频率作权，构造一颗哈夫曼树。

下面给出C++参考代码：

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <map>
using namespace std;

struct TNode
{
    unsigned int weight;
    unsigned int parent;
    unsigned int lchild;
    unsigned int rchild;
    struct TNode() : weight(0), parent(0), lchild(0), rchild(0){}
};

class HuffTree
{
public:
    void HuffmanCode(vector<TNode> &HT, vector<string> &HC, const vector<int> &wgh);
    void HuffDecodeing(vector<TNode> &HT, vector<string> &HC, vector<int> &SrcCode);
private:
    void InitHuffTree(vector<TNode> &HT, const vector<int> &wgh);
    void BuildHuffTree(vector<TNode> &HT, const vector<int> &wgh);
    void SelectTwoMin(vector<TNode> &HT, int n, int &min1, int &min2);
    void HuffCodeing(vector<TNode> &HT, vector<string> &HC, const vector<int> &wgh);
};

void HuffTree::InitHuffTree(vector<TNode> &HT, const vector<int> &wgh)
{
    if (wgh.empty())
    {
        return;
    }

    int wghSize = wgh.size();
    int m = 2 * wghSize - 1;
    HT.resize(m + 1);

    for (int i = 1; i <= wghSize; ++i)
    {
        HT[i].weight = wgh[i - 1];
    }
}

void HuffTree::SelectTwoMin(vector<TNode> &HT, int n, int &min1, int &min2)
{
    if (HT.empty())
    {
        return;
    }

    multimap<int, int> wghMap;
    multimap<int, int>::iterator iter;
    for (int i = 1; i < n; ++i)
    {
        if (HT[i].parent == 0)
        {
            wghMap.insert(make_pair(HT[i].weight, i));
        }
    }

    if (wghMap.size() >= 2)
    {
        iter = wghMap.begin();
        min1 = iter->second;
        min2 = (++iter)->second;
    }
}

void HuffTree::BuildHuffTree(vector<TNode> &HT, const vector<int> &wgh)
{
    if (HT.empty() || wgh.empty())
    {
        return;
    }

    int htSize = HT.size();
    int wghSize = wgh.size();
    int wghs1, wghs2;

    for (int i = wghSize + 1; i < htSize; i++)
    {
        SelectTwoMin(HT, i, wghs1, wghs2);

        HT[wghs1].parent = i;
        HT[wghs2].parent = i;
        HT[i].lchild = wghs1;
        HT[i].rchild = wghs2;
        HT[i].weight = HT[wghs1].weight + HT[wghs2].weight;
    }
}

void HuffTree::HuffCodeing(vector<TNode> &HT, vector<string> &HC, const vector<int> &wgh)
{
    if (HT.empty() || wgh.empty())
    {
        return;
    }

    int n = wgh.size() + 1;
    int cha, par;
    string codeTmp, code;

    for (int i = 1; i < n; i++)
    {
        code.clear();
        codeTmp.clear();
        for (cha = i, par = HT[i].parent; par != 0; cha = par, par = HT[par].parent)
        {
            if (HT[par].lchild == cha)
            {
                codeTmp = codeTmp + "0";
            }
            else
            {
                codeTmp = codeTmp + "1";
            }
        }

        for (int j = codeTmp.size() - 1; j >= 0; --j)
        {
            code = code + codeTmp[j];
        }
        HC.push_back(code);
    }
}

void HuffTree::HuffDecodeing(vector<TNode> &HT, vector<string> &HC, vector<int> &SrcCode)
{
    if (HT.empty() || HC.empty())
    {
        return;
    }

    string codeTmp;
    int p, strLen;
    for (int i = 0; i < HC.size(); ++i)
    {
        p = HT.size() - 1;                        //回到根结点
        codeTmp = HC[i];
        strLen = codeTmp.size();

        for (int j = 0; j < strLen; ++j)
        {
            if (codeTmp[j] == '0')
            {
                p = HT[p].lchild;
            }
            else
            {
                p = HT[p].rchild;
            }
        }
        SrcCode.push_back(HT[p].weight);   
    }
}   


void HuffTree::HuffmanCode(vector<TNode> &HT, vector<string> &HC, const vector<int> &wgh)
{
    if (wgh.empty())
    {
        return;
    }
    InitHuffTree(HT, wgh);

    BuildHuffTree(HT, wgh);

    HuffCodeing(HT, HC, wgh);
}

更多详情见请继续阅读下一页的精彩内容：

  • 1
  • 2
  • 下一页

相关内容