哈夫曼编码

哈夫曼编码,第1张



前言

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

字母ABCDE
普通编码000001010011100

那么一个长度为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。



哈夫曼编码

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

字母ABCDE
哈夫曼编码000001011011

普通编码所占用的空间大小: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

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

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/726757.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-26
下一篇 2022-04-26

发表评论

登录后才能评论

评论列表(0条)

保存