哈夫曼编码

---

---

前言

哈夫曼编码是根据一段数据的成员的占比，来对其编码，频率高的成员编码应该尽量短，这样整体所占的内存就比固定长度编码要小。

字母	A	B	C	D	E
普通编码	000	001	010	011	100

那么一个长度为N的字符串，仅由ABCDE组成，进行编码，则占用3N位空间大小。

---

---

哈夫曼树

假如一个长度为26的字符串中，A有2个，B有3个，C有6个，D有7个，E有8个。
（1）首先找到出现频率最小的，即A和B，将它们作为一个新的结点AB的左右孩子，频率小的作为左孩子，大的作为右孩子。新的结点AB则包含A和B，出现的频率为5。

（2）现在频率最小的是AB和C，它们再组成一个子树，新结点ABC的频率为11。

（3）当前各部分的频率分别为ABC（11）、D（7）、E（8），因此D和E组成新的子树，新结点DE的频率为15。

（4）最后ABC和DE组成哈夫曼树，ABC为左子树，DE为右子树。

（5）将树的左分支权值设为0，右分支权值设为1。

---

---

哈夫曼编码

我们将从哈夫曼树的树根到叶子所经过的路径作为叶子的编码。

字母	A	B	C	D	E
哈夫曼编码	000	001	01	10	11

普通编码所占用的空间大小：3 × \times × 26 = 78。

哈夫曼编码所占用的空间大小：3 × \times × 2 + 3 × \times × 3 + 2 × \times × 6 + 2 × \times × 7 + 2 × \times × 8 = 57。

减小了27%的存储空间大小。

---

哈夫曼树的创建

思路：

（1）首先树的创建，应该先定义树的结点；
（2）结点的成员包括此结点的权重weight，初始化为0；以及该结点的左右孩子，这里以结点在数组中位置表示，亦可以用指针表示，初始化为-1；
（3）为了方便从叶向根遍历，因此需要访问其父节点，因此包括parent成员，初始化为-1。

class Node
{
  public:
    int lchild = -1, rchild = -1;
    int parent = -1;
    int weight = 0;
};

---

然后我们从键盘输入权重：

void InitWeight(Node *p, int num)
{
    for (int i = 0; i < num; i++)
    {
        int weight;
        cout << i << " Weight: " ;
        cin >> weight;
        p[i].weight = weight;
    }
    cout << "---------------Finish !------------------" << endl;
}

---

寻找最小两结点，合并结点
在叶子结点数组尾部加上N-1位合并结点，每次在没有父结点的结点中，找到权值最小的两个结点，将其合并。

思路：
（1）先找到第一个根结点（无父结点，parent = -1），暂将其权重作为最小值
（2）遍历所有根结点，通过比较，找到权重最小的结点，min1等于其在数组的位置。

（3）找到第二个根结点（不等于min1），暂将其权重作为第二小值；
（4）遍历除min1以外的所有根结点，找到权重最小的结点，min2等于其在数组的位置。

void SearchMin(const Node *p, int num, int &min1, int &min2)
{
    for (int i = 0; i < num; i++) //找到第一个根结点
    {
        if (p[i].parent == -1)
        {
            min1 = i;
            break;
        }
    }

    for (int i = 0; i < num; i++) //遍历全部根结点，找到权重最小的根结点
    {
        if ((p[i].parent == -1) && (p[i].weight < p[min1].weight))
        {
            min1 = i;
        }
    }

    for (int i = 0; i < num; i++) //找到第二个根结点
    {
        if ((p[i].parent == -1) && (i != min1))
        {
            min2 = i;
            break;
        }
    }

    for (int i = 0; i < num; i++) //遍历全部根结点，找到权重第二小的根结点
    {
        if ((p[i].parent == -1) && (p[i].weight < p[min2].weight) && (i != min1))
        {
            min2 = i;
        }
    }
}

---

创建哈夫曼树
思路：
（1）在前numLeafs + i个结点中寻找权重最小的结点，numLeafs + i为当前包含叶子结点和合并结点的个数。
（2）将找到的两个结点，合并结点，新结点为这两个结点的父结点。

void CreateHuffman(Node *p, int numLeafs)
{
    int PosMin1, PosMin2;
    InitWeight(p, numLeafs);

    for (int i = 0; i < numLeafs - 1; i++)
    {
        SearchMin(p, numLeafs + i, PosMin1, PosMin2); //权重最小的两个结点PosMin1和PosMin2

		//合并结点
        p[numLeafs + i].weight = p[PosMin1].weight + p[PosMin2].weight;
        p[numLeafs + i].lchild = PosMin1;
        p[numLeafs + i].rchild = PosMin2;
        p[PosMin1].parent = numLeafs + i;
        p[PosMin2].parent = numLeafs + i;
    }
}

---

---

编码转换

思路：
从每个叶结点向根结点遍历，因此是从下往上遍历，因此如果是左分支，则在编码串的最前端插入0，如果是右分支，则插入1。

void HuffmanCode(Node *p, const int num, string *codes)
{
    int parent;

    for (int i = 0; i < num; i++)
    {
        int j = i;
        while (p[j].parent != -1) // 从所有叶结点开始，向根结点遍历
        {
            parent = p[j].parent;

            if (p[parent].lchild == j) // 如果为左分支，则在codes[i]字符串最前处插入0
            {
                codes[i].insert(codes[i].begin(),'0');
            }
            else // 如果为右分支，则插入1
            {
                codes[i].insert(codes[i].begin(),'1');
            }

            j = parent;

        }
    }
}

---

主函数

#include 
#include 
#include 
using namespace std;

#define NUM (5)
int main(void)
{
    Node N[2*NUM - 1]; //定义结点数组

    CreateHuffman(N, NUM); //构建哈夫曼树

    string codes[NUM]; //定义编码串数组
    HuffmanCode(N, NUM, codes); //哈夫曼编码
    
    cout << "哈夫曼编码：" << endl;
    for (int i = 0; i < NUM; i++) //打印哈夫曼编码
    {
        cout << N[i].weight << setw(8) << codes[i] << endl;
    }

    return 0;
}

---

输出：

0 Weight: 6
1 Weight: 7
2 Weight: 3
3 Weight: 2
4 Weight: 8
---------------Finish !------------------
哈夫曼编码：
6      01
7      10
3     001
2     000
8      11

文件数据编码以及解码可以参考哈夫曼编码(文件编码与解码)