ACM大牛带你玩转算法与数据结构-课程资料

本笔记属于船说系列课程之一,课程链接:

哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep66799?csource=private_space_class_null&spm_id_from=333.999.0.0

你也可以选择购买『船说系列课程-年度会员』产品『船票』,畅享一年内无限制学习已上线的所有船说系列课程:船票购买入口https://www.bilibili.com/cheese/pages/packageCourseDetail?productId=598

做题网站OJ:HZOJ - Online Judge

Leetcode :力扣 (LeetCode) 全球极客挚爱的技术成长平台

编码

什么是编码:

编码方式:ASCII编码

数据传输量:800bit,一个字符占8bit位也就是1字节,那么100个就是800bit位

时间:8S

现在需要加快传输速率,对应ASCII编码有2^8种字符也就是128个

而我们现在只需要传26种字符,那我们现在只需要5位Bit位,业绩是32种状态,就可以表示完26种英文字母,所以我们现在就自定义一种编码方法只需要5位bit位,那么现在我们传输数据量只有500bit了,时间减少为5S了。

编码方式:自定义编码

数据传输量:500bit

时间:5S

这样你也可以理解为什么网速是一样的,但是有些软件的传输速录就是比一些软件的慢,也可以理解文件压缩是怎么来的了。

什么是定长编码和变长编码

比如上面的两种方式,自定义编码和ASCII编码都是定长编码,因为它们每种状态都需要一定的bit位,ASCII编码需要8bit位,自定义编码需要5bit位。

那么变长编码就好理解了,对应状态需要的bit位是不同的。

为什么会需要编码编码,因为每个字符用到的频率是不同的,对于频率高的字符我可以把这个字符对应需要的bit位自定义小一点,那对应的需要的bit位也减少了。

例如下面:

当前a会传输50个,b会传输20个,c会传输10个,d传输20个

如果我用定长编码来表示,那我就需要2个比特位来表示,也就是4种状态,如下表示:

a:00

b:01

c:10

d:11

那么我总传输bit量就是200个,速度还是100bit/s,那么我就需要2s

我如果用变长编码利表示如下:

a:1

b:011

c:010

d:00

那么我总传输bit量就是180bit,那么我就需要1.8s

这就是变成编码对于定长编码的优势,以及为什么要学习当前的哈夫曼编码。

如何衡量两套编码的优劣

平均编码长度:

平均编码长度是指根据某种编码方案对一组数据进行编码后,每个数据项所需的平均比特数。通常情况下,平均编码长度越短,表示编码效率越高,数据压缩效果越好。

比如上面ASCII编码表示形式是800bit位,传输字符数为100,那么平均编码长度就是800/100 = 8;

这个公式的意思就是:每种字符的编码长度*他出现的概率累加最后得到的结果就是平均编码长度。

如果现在用的ASCII编码,对应图片中进行计算:

8 * 0.5 + 8 * 0.2 + 8 * 0.1 + 8 * 0.2 = 8

如果用上面变长编码的表示方式计算:

1 * 0.5 + 3 * 0.2 + 3 * 0.1 + 2 * 0.2 = 1.8

哈夫曼编码:

有了上面的基础知识,那么我们现在就进行去设计最优变长编码,也就是哈夫曼编码:

首先,统计得到每一种字符的概率。每次将最低频率的两个节点合并成一颗子树,那么这两个节点的根节点等于两个节点个概率之和,下次处理的时候就对它们的根节点进行处理了那么通过n - 1轮的第二步,就可以得到一颗哈夫曼树。通过第二步的处理,出现概率最小的是不是叶子节点,那么他需要的编码长度是最长的,而概率越大的越靠近根节点,那他的编码长度是越小的。按照左0,右1的形式,将编码读取出来。

还是用上面的a,b,c,d进行举例:

第一步有了就可以略过,直接开始第二步:

将两个概率最小的节点合并成一颗子树,并且它们的根节点的概率等于两个节点之和:

继续第二步:

继续第二步,得到哈夫曼编码的结果:

然后通过左0右1进行读取:

a:0

b:10

c:110

d:111

注意:在设计编码过程中不能形成前缀关系。

比如,现在

a:1

b:10

c:110

传输一条数据是110

现在解码,这个110是c呢,还是ab呢,所以对应每个表示的字符不能形成前缀关系,也就是如果当前节点表示了一个字符,那它是没有子节点的

对于为什么哈夫曼编码证明是最优的,可以看咱们的课程内容。

下面是代码实现:

#include

#include

#include

typedef struct Node {

//ch表示当前节点的字符

char ch;

//这里用频次表示频率

int freq;

struct Node *lchild, *rchild;

} Node;

Node *getNewNode(int freq, char ch) {

Node *p = (Node *)malloc(sizeof(Node));

p->ch = ch;

p->freq = freq;

p->lchild = p->rchild = NULL;

return p;

}

void clear(Node *root) {

if (!root) return ;

clear(root->lchild);

clear(root->rchild);

free(root);

return ;

}

void swap_node(Node **node_arr, int i, int j) {

Node *temp = node_arr[i];

node_arr[i] = node_arr[j];

node_arr[j] = temp;

return ;

}

//将最小值的位置进行找到并返回

int find_min_node(Node **node_arr, int n) {

int ind = 0;

for (int j = 0; j <= n; j++) {

if (node_arr[ind]->freq > node_arr[j]->freq) ind = j;

}

return ind;

}

Node *buildHaffmanTree(Node **node_arr, int n) {

//这里的循环表示n - 1次构建第二步

for (int i = 1; i < n; i++) {

//找到当前指针数组种第一小的freq值,也就是频率

int min_ind1 = find_min_node(node_arr, n - i);

//第一次将第一最小的放在数组最后一位

swap_node(node_arr, min_ind1, n - i);

//找到当前指针数组种第二小的freq值, 第一小的位置是当前最后的位置,已经被排除

int min_ind2 = find_min_node(node_arr, n - i - 1);

//n - i位置就是最小的,所以把第二小元素的位置放在n - i - 1,也就是当前倒数第二个位置

swap_node(node_arr, min_ind2, n - i - 1);

//然后得到它们的频率和

int freq = node_arr[n - i]->freq + node_arr[n - i - 1]->freq;

//创建新的节点

Node *node = getNewNode(freq, 0);

//进行将两个节点接在新节点上

node->lchild = node_arr[n - i - 1];

node->rchild = node_arr[n - i];

//最后将新创建的节点放在倒数第二个数组的位置

//下次循环就不会用到当前循环的最后一个位置了

node_arr[n - i - 1] = node;

}

return node_arr[0];

}

#define MAX_CHAR_NUM 128

char *char_code[MAX_CHAR_NUM] = {0};

void extractHaffmanCode(Node *root, char *buff, int k) {

buff[k] = 0;

//当没有子节点时说明当前位置有字符,需要进行操作,并回溯

if (!root->lchild && !root->rchild) {

char_code[root->ch] = strdup(buff);

return ;

}

//设置当前为遍历左子树那么当前位置就应该为0

buff[k] = '0';

extractHaffmanCode(root->lchild, buff, k + 1);

//设置当前为遍历右子树那么当前位置就应该为1

buff[k] = '1';

extractHaffmanCode(root->rchild, buff, k + 1);

return ;

}

int main() {

//n表示读入多少种字符

char s[10];

int n, freq;

scanf("%d", &n);

Node **node_arr = (Node **)malloc(sizeof(Node *) * n);

//将每个字符的数据进行节点化

for (int i = 0; i < n; i++) {

scanf("%s%d", s, &freq);

node_arr[i] = getNewNode(freq, s[0]);

}

//最终将节点进行哈夫曼编码

Node *root = buildHaffmanTree(node_arr, n);

char buff[1000];

//将转换的哈夫曼编码进行输出打印看到效果

extractHaffmanCode(root, buff, 0);

for (int i = 0; i < MAX_CHAR_NUM; i++) {

if (!char_code[i]) continue;

printf("%c : %s\n", i, char_code[i]);

}

return 0;

}

对于构建哈夫曼树的过程:

先将当前数组遍历的位置从0到n - i中的最小值放在n-i的位置上

然后再从0到n - i - 1中的最小值找到并放在n - i - 1的位置上

然后将这两个节点的概率和创建一个新节点,并且将这两个节点接在新节点上,

并把新节点放在新节点上。

那么下次循环遍历的位置就是0到n - i - 1了,如果i加一了,遍历就还是0到n - i

这个过程理解起来就像数组通过循环在减小一样。

Copyright © 2088 国际足联世界杯_巴西世界杯 - sdophx.com All Rights Reserved.
友情链接
点击进入首页