Huffman(哈夫曼)编码(贪心)(笔记)

news/2024/11/8 13:14:30/

最优编码问题:

给出n个字符的频率ci,给每个字符赋予一个01编码串,使得任意一个字符的编码不是另一个字符的前缀(这个称为前缀码),而且编码后的总长度(每个字符的频率与编码长度乘积的总和)尽量小

分析:

在解决这个问题之前,首先来看一个结论:

任何一个前缀码都可以表示成每个非叶结点恰好有两个子节点的二叉树(满二叉树)。且每个非叶结点与左子节点的边上写1,与右子节点的边上写0。每个叶子对应一个字符,编码为从根到该叶子的路径上的01序列。

(很悲惨的是,我没有相应的图放在这里)

为了证明在一般情况下,都可以用这样的二叉树来表示最优前缀码,需要证明两个结论。

结论1:n个叶子的二叉树的每个叶子一定对应一个前缀码。如果编码a为编码b的前缀,则a所对应的结点一定为b所对应结点的祖先。而两个叶子结点不会有祖先候带关系

结论2:最优前缀码一定可以写成二叉树。逐个字符构造即可。每拿到一个编码,都可以构造出从根到叶子的一条路径,沿着已有结点走,构建不存在的结点。这样得到的二叉树不可能有单子节点,因为如果存在,只要用这个子节点代替父节点,得到的仍然是前缀码,且总长度更短

接下来的问题就变为:如何构造一棵最优的编码树。

Huffman算法:把每一个字符看作一个单节点子树放在一个树集合中,每颗子树的权值等于对应字符的频率。每次取权值最小的两颗子树合并成一颗新树,并重新放到集合中。新树的权值等于两颗子树权值之和。

下面分两步证明算法的正确性:

结论1:设x和y是频率最小的两个字符,则存在前缀码使得x和y具有相同码长,且仅有最后一位编码不同。换句话说,第一步贪心法选择保留最优解

证明:假设深度最大的结点为a,则a一定有一个兄弟b。不妨设f(x)<=f(y),f(a)<=f(b),则f(x)<=f(a),f(y)<=f(b)。如果x不是a,则交换x和a;如果y不是b,则交换y和b。这样得到的新编码树不会比原来的差(f()代表该字符的权值,本题为频率)

结论2:设T是加权字符集C的最优编码树,x和y是树T中的两个叶子,且互为兄弟结点,z是他们的父节点。若把z看出具有频率f(z)=f(x)+f(y)的字符,则树是字符集的一颗最优编码树。换句话说,原问题的最优解包含子问题的最优解

证明:设T'的编码长度为L,其中字符{x, y}的深度为h,则把字符{x, y}拆成两个后,长度变为L - (f(x) + f(y)) * h + (f(x) + f(y)) * (h + 1) = L + f(x) + f(y)。因此T'必须是C '的最优编码树,T才是C的最优编码树。

结论1通常称为贪心选择性质,结论2通常称为最优子结构性质。根据这两个结论,Huffman算法正确。在程序实现上,可以先按照频率把所有字符排序成表P,然后创建一个新结点队列Q,在每次合并两个结点后把新结点放到队列Q中,由于后合并的频率和一定比先合并的频率和大,因此Q内的元素是有序的,类似有序表的合并过程,每次只需要检查P和Q的首元素即可找到频率最小的元素,时间复杂度为O(n)。算上排序,总时间复杂度为O(nlogn)

(以上摘自《算法竞赛入门经典(第2版)》


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

相关文章

1.每日SQL----2024/11/7

题目&#xff1a; 计算用户次日留存率,即用户第二天继续登录的概率 表&#xff1a; iddevice_iddate121382024-05-03232142024-05-09332142024-06-15465432024-08-13523152024-08-13623152024-08-14723152024-08-15832142024-05-09932142024-08-151065432024-08-131123152024-…

ChatGPT的多面手:日常办公、论文写作与深度学习的结合

ChatGPT&#xff0c;由OpenAI精心打造的大型语言模型&#xff0c;依托于先进的人工神经网络技术&#xff0c;展现了在理解和生成自然语言文本方面的强大能力。该模型的核心设计宗旨是通过对话式交互&#xff0c;为用户带来前所未有的体验&#xff0c;无论是提供信息、答疑解惑&…

k8s图形化显示(KRM)

在master节点 kubectl get po -n kube-system 这个命令会列出 kube-system 命名空间中的所有 Pod 的状态和相关信息&#xff0c;比如名称、状态、重启次数等。 systemctl status kubelet #查看kubelet状态 yum install git #下载git命令 git clone https://gitee.com/duk…

网络安全知识见闻终章 ?

安全知识没有终点&#xff01;&#xff01;&#xff01; 一、软件和硬件设备的类型 1.软件程序的类型 2.硬件设备的类型 二、网络类型、协议、设备、安全 1.网络类型 2.网络协议 常见的网络协议 3、网络设备 a. 网络设备的分类 b. 网络设备的功能 4.网络安全 三、w…

HTML5和CSS3 介绍

HTML5 (HyperText Markup Language 5) 定义 HTML5 是 HTML 的第五个主要版本&#xff0c;它是对前一版本&#xff08;HTML4 和 XHTML&#xff09;的重大改进。HTML5 引入了许多新特性&#xff0c;旨在简化网页开发&#xff0c;提高用户体验&#xff0c;并支持更丰富的多媒体和…

Cesium使用flyToBoundingSphere实现倾斜相机视角观察物体

之前有一篇文章介绍如何使用Cesium倾斜相机视角观察物体&#xff0c;后面发现了一个API viewer.camera.flyToBoundingSphere&#xff0c;能直接实现我想要的效果。 所以我封装了一个函数&#xff0c;通过使用 Cesium.Camera.flyToBoundingSphere API&#xff0c;自动调整相机的…

实现自动化数据抓取:使用Node.js操控鼠标点击与位置坐标

在当今信息爆炸的时代&#xff0c;自动化数据抓取技术&#xff08;也称为“网络爬虫”&#xff09;对于数据分析与信息挖掘具有重要的作用。本文将介绍如何利用Node.js实现自动化数据抓取&#xff0c;并通过控制鼠标点击与位置坐标的方式&#xff0c;采集页面上指定的新闻数据。…

Jenkins找不到maven构建项目

有的可能没有出现maven这个选项 解决办法&#xff1a;需要安装Maven项目插件 输入​Maven Integration plugin​