数据结构与算法基础-学习-18-哈夫曼编码

news/2024/11/17 6:33:38/

一、个人理解

在远程通讯中，需要把字符转成二进制的字符串进行传输，例如我们需要传输ABCD，我们可以用定长的字符串进行表示，例如:

  1. A:00

  1. B:01

  1. C:02

  1. D:03

这样可能就造成空间的浪费，我们多存储了一个0号位。那用变长呢，会怎么样，我们试试，例如：

  1. A:0

  1. B:00

  1. C:01

  1. D:1

如果接收到的二进制字符串为：0000101，在解码时是否就会出现歧义，可以是AAAADAD,也可以是ABCC，也可以是BBDC等等。

从而引入了哈夫曼编码，也称为最优前缀码。之前我们已经实现了哈夫曼树，可以参考文章链接《数据结构与算法基础-学习-17-二叉树之哈夫曼树》，从哈夫曼树这个中间结果，转换出我们想要的哈夫曼编码。

二、为什么哈夫曼编码得出二进制字符串最短呢？

  1. 在生成哈夫曼树之前，我们需要统计字符在数据中出现的概率，出现的概率越高，编码会越短。

  1. 之前介绍过的哈夫曼树的特点，权值越大的结点离根结点越近，也就是路径越短。

  1. 哈夫曼树规定走左子树就标记为0，走右子树就标记为1，从根结点到各个叶子节点的标记拼接起来，就是这个字符的哈夫曼编码。

三、结构体定义

typedef char** HaffmanCode;

四、函数实现

1、生成哈夫曼编码

（1）定义
Status CreateHaffmanCode(HaffmanTree HT, HaffmanCode* HC, HaffmanTreeLentype ArrayLen)
{JudgeAllNullPointer(HT);//Init HaffmanCode*HC          = (HaffmanCode)MyMalloc(sizeof(char*) * ArrayLen);char* TmpHC = (char*)MyMalloc(sizeof(char) * (ArrayLen - 1));//临时数组存放哈夫曼编码中间结果,长度n，编码最长需要n-1,所以分配n-1。HaffmanTreeLentype TmpHCLen = 0;HaffmanTreeLentype i,j;HaffmanTreeLentype TmpParentIndex;//上一个结点的父亲索引。HaffmanTreeLentype TmpIndex;//上一个结点的索引号。for(i = 1; i <= ArrayLen; i++){TmpParentIndex = HT[i].ParentIndex;TmpIndex       = i;while(HT[TmpParentIndex].ParentIndex != 0){if(HT[TmpParentIndex].LeftChildIndex == TmpIndex){TmpHC[TmpHCLen] = '0';TmpHCLen++;}else if (HT[TmpParentIndex].RightChildIndex == TmpIndex){TmpHC[TmpHCLen] = '1';TmpHCLen++;}else{Log("Internal Error : Perant LeftChildIndex and RightChildIndex != TmpIndex",Error);}TmpIndex       = TmpParentIndex;TmpParentIndex = HT[TmpParentIndex].ParentIndex;}//根节点判断if(HT[TmpParentIndex].LeftChildIndex == TmpIndex){TmpHC[TmpHCLen] = '0';TmpHCLen++;}else if(HT[TmpParentIndex].RightChildIndex == TmpIndex){TmpHC[TmpHCLen] = '1';TmpHCLen++;}else{Log("Internal Error : Root Node Perant LeftChildIndex and RightChildIndex != TmpIndex",Error);}//将TmpHC中的字符倒序写入HC中。(*HC)[i-1] = (char*)MyMalloc(sizeof(char) * (TmpHCLen + 1));//编码最长需要n,加上\0，所以分配n+1。for(j = TmpHCLen - 1; j >= 0; j--){(*HC)[i-1][TmpHCLen - 1 - j] = TmpHC[j];if(j == 0)//因为j是无符号长整型，j不能等于负数，当j=-1,退出循环，导致程序core掉，由此添加此判断，避免问题的发生。{break;}}(*HC)[i-1][TmpHCLen] = '\0';TmpHCLen             = 0;}free(TmpHC);TmpHC = NULL;Log("Create HaffmanCode     : OK\n",Info);return SuccessFlag;
}

（2）参数

参数名

说明

HT

传入参数类型为HaffmanTree 的哈夫曼树。

HC

传入参数类型为HaffmanCode*的哈夫曼编码数组指针。

ArrayLen

传入参数类型为HaffmanTreeLentype的权值数组长度。

（3）实现思路

A,B,C,D,E对应的权值如下：

HaffmanTreeLentype WeightArray[]  = {2,4,2,3,3};

生成哈夫曼树如下：

2023-3--[Info]--HaffmanTree            :
[ Index | Weight | ParentIndex | LeftChildIndex | RightChildIndex ]
[ 0     | 0      | 0           | 0              | 0               ]
[ 1     | 2      | 6           | 0              | 0               ]
[ 2     | 4      | 8           | 0              | 0               ]
[ 3     | 2      | 6           | 0              | 0               ]
[ 4     | 3      | 7           | 0              | 0               ]
[ 5     | 3      | 7           | 0              | 0               ]
[ 6     | 4      | 8           | 1              | 3               ]
[ 7     | 6      | 9           | 4              | 5               ]
[ 8     | 8      | 9           | 6              | 2               ]
[ 9     | 14     | 0           | 7              | 8               ]

图示如下：

从根节点开始遍历到每个叶子结点算出哈夫曼编码比较困难，我们反其道而行之，从叶子结点开始遍历到根节点，但我们算出的结果是一个倒序的，我们需要一个临时数组来存储倒序编码，最后再正序填写回哈夫曼编码数组中即可。

例如我们来算一个A，父亲是权值4，走左子树为0，0写入临时数组,

char TmpHC[] = {'0'};

再往上走，父亲是权值8，走左子树为0，0写入临时数组，

char TmpHC[] = {'0','0'};

再往上走，父亲是权值14，走右子树为1，1写入临时数组，

char TmpHC[] = {'0','0','1'};

倒序写回哈夫曼编码数组就是100。其他的大家自己可以算一下，是不是这样，至于和老师讲的可能有不一样的地方，例如最后形成的编码，只是由于数组中选出两个最小的值，哪个是左子树索引，哪个是右子树索引，不一样导致，但不影响编码。最终得出的哈夫曼编码如下：

2023-3--[Info]--HaffmanCode            :
[ Index | Code    ]
[ 1     | 100     ]
[ 2     | 11      ]
[ 3     | 101     ]
[ 4     | 00      ]
[ 5     | 01      ]

2、销毁哈夫曼编码

（1）定义
Status DestoryHaffmanCode(HaffmanCode HC,HaffmanTreeLentype ArrayLen)
{JudgeAllNullPointer(HC);HaffmanTreeLentype i;for(i = 0; i < ArrayLen; i++){free(HC[i]);HC[i] = NULL;}free(HC);HC = NULL;Log("Destory HaffmanCode    : OK\n",Info);return SuccessFlag;
}

（2）参数

参数名

说明

HC

传入参数类型为HaffmanCode*的哈夫曼编码数组指针。

ArrayLen

传入参数类型为HaffmanTreeLentype的权值数组长度。

四、虚机测试

[gbase@czg2 Tree]$ make
gcc -Wall -g ../Log/Log.c BinaryTree.c HaffmanTree.c main.c -o TestBinaryTree -I ../Log/
[gbase@czg2 Tree]$ ./TestBinaryTree 
2023-3--[Info]--Init Global Array      : OK
2023-3--[Info]--Init Binary Tree       : OK
2023-3--[Info]--New Binary Search Tree : OK
2023-3--[Info]--PreOrderTraverse       : [6 ,3 ,2 ,1 ,5 ,8 ,7 ], CurSize : 7
2023-3--[Info]--InOrderTraverse        : [1 ,2 ,3 ,5 ,6 ,7 ,8 ], CurSize : 7
2023-3--[Info]--PostOrderTraverse      : [1 ,2 ,5 ,3 ,7 ,8 ,6 ], CurSize : 7
2023-3--[Info]--PreOrderTraverseNoRcs  : [6 ,3 ,2 ,1 ,5 ,8 ,7 ], CurSize : 7
2023-3--[Info]--InOrderTraverseNoRcs   : [1 ,2 ,3 ,5 ,6 ,7 ,8 ], CurSize : 7
2023-3--[Info]--PostOrderTraverseNoRcs : [1 ,2 ,5 ,3 ,7 ,8 ,6 ], CurSize : 7
2023-3--[Info]--LevelOrderBinaryTree   : [6 ,3 ,8 ,2 ,5 ,7 ,1 ], CurSize : 7
2023-3--[Info]--SqQueue Data           :
Data           : [1 ,2 ,3 ,0 ,0 ,4 ,5 ,0 ,6 ,0 ,0 ,7 ,0 ,0 ,0 ]
FrontIndex     : 0
RearIndex      : 15
SqQueueLen     : 15
2023-3--[Info]--Init Binary Tree       : OK
2023-3--[Info]--PreOrderTraverse       : [1 ,2 ,3 ,4 ,5 ,6 ,7 ], CurSize : 7
2023-3--[Info]--InOrderTraverse        : [3 ,2 ,5 ,6 ,4 ,7 ,1 ], CurSize : 7
2023-3--[Info]--PostOrderTraverse      : [3 ,6 ,5 ,7 ,4 ,2 ,1 ], CurSize : 7
2023-3--[Info]--PreOrderTraverseNoRcs  : [1 ,2 ,3 ,4 ,5 ,6 ,7 ], CurSize : 7
2023-3--[Info]--InOrderTraverseNoRcs   : [3 ,2 ,5 ,6 ,4 ,7 ,1 ], CurSize : 7
2023-3--[Info]--PostOrderTraverseNoRcs : [3 ,6 ,5 ,7 ,4 ,2 ,1 ], CurSize : 7
2023-3--[Info]--LevelOrderBinaryTree   : [1 ,2 ,3 ,4 ,5 ,7 ,6 ], CurSize : 7
2023-3--[Info]--Init Binary Tree       : OK
2023-3--[Info]--Copy Tree              : OK
2023-3--[Info]--PreOrderTraverse       : [1 ,2 ,3 ,4 ,5 ,6 ,7 ], CurSize : 7
2023-3--[Info]--InOrderTraverse        : [3 ,2 ,5 ,6 ,4 ,7 ,1 ], CurSize : 7
2023-3--[Info]--PostOrderTraverse      : [3 ,6 ,5 ,7 ,4 ,2 ,1 ], CurSize : 7
2023-3--[Info]--Tree Depth             : 4
2023-3--[Info]--Tree Depth             : 5
2023-3--[Info]--Tree Depth             : 5
2023-3--[Info]--Tree Node Num          : 7
2023-3--[Info]--Tree Node Num          : 7
2023-3--[Info]--Tree Node Num          : 7
2023-3--[Info]--Tree Leaves Node Num   : 3
2023-3--[Info]--Tree Leaves Node Num   : 3
2023-3--[Info]--Tree Leaves Node Num   : 3
2023-3--[Info]--Create HaffmanTree     : OK
2023-3--[Info]--HaffmanTree            :
[ Index | Weight | ParentIndex | LeftChildIndex | RightChildIndex ]
[ 0     | 0      | 0           | 0              | 0               ]
[ 1     | 2      | 6           | 0              | 0               ]
[ 2     | 4      | 8           | 0              | 0               ]
[ 3     | 2      | 6           | 0              | 0               ]
[ 4     | 3      | 7           | 0              | 0               ]
[ 5     | 3      | 7           | 0              | 0               ]
[ 6     | 4      | 8           | 1              | 3               ]
[ 7     | 6      | 9           | 4              | 5               ]
[ 8     | 8      | 9           | 6              | 2               ]
[ 9     | 14     | 0           | 7              | 8               ]
2023-3--[Info]--Create HaffmanCode     : OK
2023-3--[Info]--HaffmanCode            :
[ Index | Code    ]
[ 1     | 100     ]
[ 2     | 11      ]
[ 3     | 101     ]
[ 4     | 00      ]
[ 5     | 01      ]
2023-3--[Info]--Destory HaffmanCode    : OK
2023-3--[Info]--Destory HaffmanTree    : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK

http://www.ppmy.cn/news/35652.html

相关文章

“蓝桥杯”递推和递归（一）——取数位

“蓝桥杯”递推和递归（一）——取数位

1. 算法简介 递推和递归虽然叫法不同&#xff0c;但它们的基本思想是一致的&#xff0c;在很多程序中&#xff0c;这两种算法可以通用&#xff0c;不同的是递推法效率更高&#xff0c;递归法更方便阅读。 &#xff08;1&#xff09;递推法 递推法是一种重要的数学方法&#…
阅读更多...
安全多方计算之八：Mix-Match

安全多方计算之八：Mix-Match

Mix-Match1. 混合网络基于ElGamal加密方案的混合网络2. PET协议3. Mix-Match协议4. 百万富翁问题的Mix-Match解决方案M.Jakobsson和A.Juels提出了基于Mix-Match的安全多方计算协议构造方法&#xff0c;该类协议包括Mix与Match两个阶段&#xff1a; Mix阶段&#xff1a;通过构造…
阅读更多...
计算机视觉知识点（一）——交并比（IoU）及其若干改进

计算机视觉知识点（一）——交并比（IoU）及其若干改进

交并比&#xff08;IoU&#xff09;前言IoU公式及示意图IoU Loss缺点GIoU Loss公式及示意图缺点DIoU公式及示意图CIoU前言 目标检测是一个常见的计算机视觉任务&#xff0c;在目标检测任务中&#xff0c;交并比作为评判检测框的标准具有很重要的意义&#xff0c;在实际的应用中…
阅读更多...
AI真的快让我们失业了，从ChatGPT到Midjourney

AI真的快让我们失业了，从ChatGPT到Midjourney

参考文章&#xff1a; https://mp.weixin.qq.com/s/3RdHPPhYgDfB6KY6Y9Sk2A跟AI有关的新闻&#xff0c;一个接着一个。前一天你还和往常一样进入梦乡&#xff0c;第二天醒来就能被新的AI新闻“炸弹”震得心惊。 以ChatGPT为代表的AI语言模型&#xff0c;以Midjourney为代表的…
阅读更多...
node-HTTP协议

node-HTTP协议

文章目录一. 概念二. 请求报文的组成三.HTTP请求行四.HTTP请求头五.HTTP的请求体六.响应报文的组成七.创建HTTP服务八.获取HTTP请求报文九.HTTP设置响应十.GET和POST请求的区别一. 概念 HTTP协议. 中文叫超文本传输协议; 是一种基于TCP/IP的应用层通信协议; 这个协议详细规定了…
阅读更多...
如何使用MSF复现MS17-010漏洞？

如何使用MSF复现MS17-010漏洞？

MSF概述 Metasploit Framework(MSF)是一款开源安全漏洞检测工具&#xff0c;附带数千个已知的软件漏洞&#xff0c;并保持持续更新。Metasploit可以用来信息收集、漏洞探测、漏洞利用等渗透测试的全流程&#xff0c;被安全社区冠以“可以黑掉整个宇宙”之名。刚开始的Metasplo…
阅读更多...
WPF 常用控件

WPF 常用控件

WPF六种常用控件&#xff1a;布局控件、内容控件、带标题内容控件、条目控件、带标题条目控件和特殊内容控件(如:TextBox,TextBlock,Image等)。实例链接&#xff1a;WPF常用控件实例Window(窗体)Winodw窗体派生自ContentControl&#xff0c;有一个Content属性&#xff0c;里面可…
阅读更多...
用于人工智能研究的开源Python微电网模拟器pymgrid（入门篇）

用于人工智能研究的开源Python微电网模拟器pymgrid（入门篇）

pymgrid是一个开源Python库&#xff0c;用于模拟微型电网的三级控制&#xff0c;允许用户创建或自行选择的微电网。并可以使用自定义的算法或pymgrid中包含的控制算法之一来控制这些微电网&#xff08;基于规则的控制和模型预测控制&#xff09;。 pymgrid还提供了与OpenAI Gy…
阅读更多...
最新文章

Copyright @ 2022~2023