财政局门户网站建设方案,工程公司起名大全,哈尔滨哪里做网站好,wordpress默认链接#x1f49d;#x1f49d;#x1f49d;欢迎来到我的博客#xff0c;很高兴能够在这里和您见面#xff01;希望您在这里可以感受到一份轻松愉快的氛围#xff0c;不仅可以获得有趣的内容和知识#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学… 欢迎来到我的博客很高兴能够在这里和您见面希望您在这里可以感受到一份轻松愉快的氛围不仅可以获得有趣的内容和知识也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老导航 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂 非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。 ✨✨ 欢迎订阅本专栏 ✨✨ 博客目录 一.哈夫曼算法1.什么是编码?2.编码传输规则3.Huffman 编码 二.哈夫曼树1.什么 Huffman 树?2.哈夫曼树特点3.节点总数证明4.Huffman 树特点 三.常见方法1.内部 Node 节点2.构造方法3.编码4.解码5.完整代码 四.练习题1.连接棒材的最低费用-力扣 1167 题 一.哈夫曼算法
1.什么是编码?
简单说就是建立【字符】到【数字】的对应关系如下面大家熟知的 ASC II 编码表例如可以查表得知字符【a】对应的数字是十六进制数【0x61】
\000102030405060708090a0b0c0d0e0f0000000102030405060708090a0b0c0d0e0f0010101112131415161718191a1b1c1d1e1f002020!#$%’()*,-./00300123456789:;?0040ABCDEFGHIJKLMNO0050PQRSTUVWXYZ[\]^_0060abcdefghijklmno0070pqrstuvwxyz{|}~7f 注一些直接以十六进制数字标识的是那些不可打印字符 2.编码传输规则
传输时的编码
java 中每个 char 对应的数字会占用固定长度 2 个字节如果在传输中仍采用上述规则传递 abbccccccc 这 10 个字符 实际的字节为 006100620062006300630063006300630063006316 进制表示总共 20 个字节不经济
现在希望找到一种最节省字节的传输方式怎么办
假设传输的字符中只包含 abc 这 3 个字符有同学重新设计一张二进制编码表见下图
0 表示 a1 表示 b10 表示 c
现在还是传递 abbccccccc 这 10 个字符
实际的字节为 01110101010101010 二进制表示总共需要 17 bits也就是 2 个字节多一点行不行
不行因为解码会出现问题因为 10 会被错误的解码成 ba而不是 c
解码后结果为 abbbababababababa是错误的
怎么解决必须保证编码后的二进制数字要能区分它们的前缀prefix-free
用满二叉树结构编码可以确保前缀不重复 向左走 0向右走 1走到叶子字符累计起来的 0 和 1 就是该字符的二进制编码
再来试一遍
a 的编码 0b 的编码 10c 的编码 11
现在还是传递 abbccccccc 这 10 个字符
实际的字节为 0101011111111111111二进制表示总共需要 19 bits也是 2 个字节多一点并且解码没有问题了行不行
这回解码没问题了但并非最少字节因为 c 的出现频率高7 次a 的出现频率低1 次因此出现频率高的字符编码成短数字更经济
3.Huffman 编码
考察下面的树 00 表示 a01 表示 b1 表示 c
现在还是传递 abbccccccc 这 10 个字符
实际的字节为 000101 1111111 二进制表示总共需要 13 bits这棵树就称之为 Huffman 树根据 Huffman 树对字符和数字进行编解码就是 Huffman 编解码
二.哈夫曼树
1.什么 Huffman 树?
哈夫曼树英文名 huffman tree,它是一种的叶子节点带有权重的特殊二叉树也叫最优二叉树。
哈夫曼(Huffman)编码是上个世纪五十年代由哈夫曼教授研制开发的它借助了数据结构当中的树型结构在哈夫曼算法的支持下构造出一棵最优二叉树我们把这类树命名为哈夫曼树。
哈夫曼树是带权路径长度最短的树权值较大的节点离根较近。
2.哈夫曼树特点
哈夫曼树的特点 没有度为1的节点每个非叶子节点都是由两个最小值的节点构成 n 个叶子节点的哈夫曼树总共有2n-1个节点; 哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树 对同一组权值{w1w2…}存在不同构的两个哈夫曼树但是它们的总权值相等。 形成了这样的一颗哈夫曼树这也是二叉树的前序
3.节点总数证明
证明哈夫曼树中有 n 个叶子节点的树总共有 2n-1 个节点可以使用数学归纳法。以下是证明的步骤
步骤 1基础情况 当 n1 时只有一个叶子节点因此整棵哈夫曼树只有一个节点。这是一个基础情况。
步骤 2归纳假设 假设对于某个正整数 k当哈夫曼树有 k 个叶子节点时它总共有 2k-1 个节点。
步骤 3归纳证明 现在考虑有 k1 个叶子节点的情况。我们可以将这个问题分成两个部分
部分 1 从 k 个叶子节点构建一个哈夫曼树根据归纳假设这个树有 2k-1 个节点。
部分 2 现在我们添加一个额外的叶子节点构建一个新的哈夫曼树。在这个新树中我们需要添加一个新的内部节点作为新叶子节点和部分 1 中的树的根节点的父节点。这个新树总共有 2k 个叶子节点和 1 个额外的内部节点所以共有 2k1 个节点。
现在将部分 1 和部分 2 合并在一起我们得到了有 k1 个叶子节点的哈夫曼树总共有(2k-1) (2k1) 2k-1 2k1 2(k-12) 2k1-1 个节点。
这证明了对于 k1 个叶子节点的情况有 2k1-1 个节点即当 nk1 时也成立。
由于基础情况成立并且我们已经证明了当 nk1 时成立所以根据数学归纳法对于所有正整数 n有 n 个叶子节点的哈夫曼树总共有 2n-1 个节点。
4.Huffman 树特点
哈夫曼树Huffman Tree是一种用于数据压缩的树形数据结构它具有以下几个特点 最优编码哈夫曼树被设计用来实现最优的数据压缩编码这意味着它可以生成具有最小平均编码长度的编码方案以便在数据传输或存储时能够节省空间。 基于频率哈夫曼树的构建是基于数据中各个字符或符号的出现频率来进行的。频率高的字符被赋予较短的编码而频率低的字符被赋予较长的编码。 唯一性对于给定的数据集存在唯一的哈夫曼树。这意味着如果两个人使用相同的数据集和相同的构建规则来创建哈夫曼树它们将得到相同的树结构和编码。 前缀编码哈夫曼编码是一种前缀编码意味着没有一个字符的编码是另一个字符编码的前缀。这个特性确保在解码时不会产生歧义。 树形结构哈夫曼树是一种二叉树它由内部节点和叶子节点组成。叶子节点对应于数据集中的字符而内部节点是用于构建编码的辅助节点。 压缩率哈夫曼编码通常能够实现较高的压缩率尤其是对于具有不同频率分布的数据集。频率高的字符使用较短的编码从而实现更好的压缩效果。 动态性哈夫曼编码可以动态地根据数据集的特性进行调整以适应不同的数据。这使得它在各种应用中都具有灵活性。
总之哈夫曼树是一种用于数据压缩的有效工具其特点包括最优编码、基于频率、唯一性、前缀编码、树形结构、高压缩率和动态性。通过合理构建哈夫曼树可以实现高效的数据压缩和解压缩操作。
三.常见方法
1.内部 Node 节点
/*** Node代表字符节点*/
static class Node {/*** 字符*/Character ch;/*** 频次*/int freq;/*** 左子节点*/Node left;/*** 右子节点*/Node right;/*** 编码*/String code;public Node(Character ch) {this.ch ch;}public Node(int freq, Node left, Node right) {this.freq freq;this.left left;this.right right;}int freq() {return freq;}boolean isLeaf() {return left null;}Overridepublic String toString() {return Node{ ch ch , freq freq };}
}2.构造方法
public HuffmanTree(String str) {this.str str;// 功能1统计字符的频率char[] chars str.toCharArray();for (char c : chars) {Node node map.computeIfAbsent(c, Node::new);node.freq;}// 功能2: 构造树PriorityQueueNode queue new PriorityQueue(Comparator.comparingInt(Node::freq));queue.addAll(map.values());while (queue.size() 2) {Node x queue.poll();Node y queue.poll();int freq x.freq y.freq;queue.offer(new Node(freq, x, y));}root queue.poll();// 功能3计算每个字符的编码,int sum dfs(root, new StringBuilder());for (Node node : map.values()) {System.out.println(node node.code);}// 功能4字符串编码后占用 bitsSystem.out.println(总共会占用 bits: sum);
}private int dfs(Node node, StringBuilder code) {int sum 0;if (node.isLeaf()) {node.code code.toString();sum node.freq * code.length();} else {sum dfs(node.left, code.append(0));sum dfs(node.right, code.append(1));}if (code.length() 0) {code.deleteCharAt(code.length() - 1);}return sum;}3.编码
public String encode() {//abbcccccccchar[] chars str.toCharArray();StringBuilder sb new StringBuilder();for (char c : chars) {sb.append(map.get(c).code);}return sb.toString();
}4.解码
public String decode(String str) {/*从根节点寻找数字对应的字符数字是 0 向左走数字是 1 向右走如果没走到头每走一步数字的索引 i走到头就可以找到解码字符再将 node 重置为根节点a 00b 10c 1i0 0 0 1 0 1 1 1 1 1 1 1 1*/char[] chars str.toCharArray();int i 0;StringBuilder sb new StringBuilder();Node node root;// i 13 noderoot// 0001011111111while (i chars.length) {if (!node.isLeaf()) { // 非叶子if (chars[i] 0) { // 向左走node node.left;} else if (chars[i] 1) { // 向右走node node.right;}i;}if (node.isLeaf()) {sb.append(node.ch);node root;}}return sb.toString();
}5.完整代码
/*** Huffman 树的构建过程* 1. 将统计了出现频率的字符放入优先级队列* 2. 每次出队两个频次最低的元素给它俩找个爹* 3. 把爹重新放入队列重复 2~3* 4. 当队列只剩一个元素时Huffman 树构建完成** author : qinyingjie* date : 2023/9/26*/
public class HuffmanTree {/*** Node代表字符节点*/static class Node {/*** 字符*/Character ch;/*** 频次*/int freq;/*** 左子节点*/Node left;/*** 右子节点*/Node right;/*** 编码*/String code;public Node(Character ch) {this.ch ch;}public Node(int freq, Node left, Node right) {this.freq freq;this.left left;this.right right;}int freq() {return freq;}boolean isLeaf() {return left null;}Overridepublic String toString() {return Node{ ch ch , freq freq };}}String str;/*** 统计字符数量,key是字符,value是节点*/MapCharacter, Node map new HashMap();/*** 根节点*/Node root;public HuffmanTree(String str) {this.str str;// 功能1统计字符的频率char[] chars str.toCharArray();for (char c : chars) {Node node map.computeIfAbsent(c, Node::new);node.freq;}// 功能2: 构造树PriorityQueueNode queue new PriorityQueue(Comparator.comparingInt(Node::freq));queue.addAll(map.values());while (queue.size() 2) {Node x queue.poll();Node y queue.poll();int freq x.freq y.freq;queue.offer(new Node(freq, x, y));}root queue.poll();// 功能3计算每个字符的编码,int sum dfs(root, new StringBuilder());for (Node node : map.values()) {System.out.println(node node.code);}// 功能4字符串编码后占用 bitsSystem.out.println(总共会占用 bits: sum);}private int dfs(Node node, StringBuilder code) {int sum 0;if (node.isLeaf()) {node.code code.toString();sum node.freq * code.length();} else {sum dfs(node.left, code.append(0));sum dfs(node.right, code.append(1));}if (code.length() 0) {code.deleteCharAt(code.length() - 1);}return sum;}// 编码public String encode() {//abbcccccccchar[] chars str.toCharArray();StringBuilder sb new StringBuilder();for (char c : chars) {sb.append(map.get(c).code);}return sb.toString();}// 解码public String decode(String str) {/*从根节点寻找数字对应的字符数字是 0 向左走数字是 1 向右走如果没走到头每走一步数字的索引 i走到头就可以找到解码字符再将 node 重置为根节点a 00b 10c 1i0 0 0 1 0 1 1 1 1 1 1 1 1*/char[] chars str.toCharArray();int i 0;StringBuilder sb new StringBuilder();Node node root;// i 13 noderoot// 0001011111111while (i chars.length) {if (!node.isLeaf()) { // 非叶子if (chars[i] 0) { // 向左走node node.left;} else if (chars[i] 1) { // 向右走node node.right;}i;}if (node.isLeaf()) {sb.append(node.ch);node root;}}return sb.toString();}public static void main(String[] args) {HuffmanTree tree new HuffmanTree(abbccccccc);String encoded tree.encode();System.out.println(encoded);System.out.println(tree.decode(encoded));}
}四.练习题
1.连接棒材的最低费用-力扣 1167 题
题目编号题目标题算法思路1167Plus 题目连接棒材的最低费用Huffman 树、贪心 为了装修新房你需要加工一些长度为正整数的棒材 sticks。 如果要将长度分别为 X 和 Y 的两根棒材连接在一起你需要支付 X Y 的费用。 由于施工需要你必须将所有棒材连接成一根。 返回你把所有棒材 sticks 连成一根所需要的最低费用。注意你可以任意选择棒材连接的顺序。 示例 1
输入sticks [2,4,3]
输出14
解释先将 2 和 3 连接成 5花费 5再将 5 和 4 连接成 9总花费为 14。示例 2
输入sticks [1,8,3,5]
输出30提示
1 sticks.length 10^4
1 sticks[i] 10^4题解
/*** h3连接棒材的最低费用/h3* p为了装修新房你需要加工一些长度为正整数的棒材。如果要将长度分别为 X 和 Y 的两根棒材连接在一起你需要支付 X Y 的费用。 返回讲所有棒材连成一根所需要的最低费用。/p*/
public class Leetcode1167 {/*举例 棒材为 [1,8,3,5]如果以如下顺序连接(非最优)- 189- 9312- 12517总费用为 9121738如果以如下顺序连接(最优)- 134- 459- 8917总费用为 491730*/int connectSticks(int[] sticks) {PriorityQueueInteger queue new PriorityQueue();for (int stick : sticks) {queue.offer(stick);}int sum 0;while (queue.size() 2) {Integer x queue.poll();Integer y queue.poll();int c x y;sum c;queue.offer(c);}return sum;}public static void main(String[] args) {Leetcode1167 leetcode new Leetcode1167();System.out.println(leetcode.connectSticks(new int[]{1, 8, 3, 5})); // 30System.out.println(leetcode.connectSticks(new int[]{2, 4, 3})); // 14}
}觉得有用的话点个赞 呗。 ❤️❤️❤️本人水平有限如有纰漏欢迎各位大佬评论批评指正 如果觉得这篇文对你有帮助的话也请给个点赞、收藏下吧非常感谢! Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧
