-
哈夫曼树的构建及其编码
2018-05-11 20:35:50常见应用:压缩,最基本的压缩编码的方法,使得总体的编码长度缩短,减少不必要的空间。什么可以称为哈夫曼树?公式判断:WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)Wi : 表示第i...哈夫曼树构建的步骤:① 给定n个权值{...常见应用:压缩,最基本的压缩编码的方法,使得总体的编码长度缩短,减少不必要的空间。
什么可以称为哈夫曼树?
公式判断:WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)
Wi : 表示第i个叶子的节点权值
Li:表示第i个叶子节点到根节点的路径长度
路径长度:通俗点,就是叶子节点到根节点的线段条数
带权路径WPL最小的二叉树就叫做哈夫曼树,也叫最优二叉树。
哈夫曼树构建的步骤:
① 给定n个权值{w1,w2,w3,...,wn}构建只有一个节点的二叉树,从而得到n棵二叉树的集合 F = {T1,T2,T3,...,Tn}
② 选取最小、次小的二叉树分别做左子树和右子树,构建成一棵新的二叉树
③ 删除最小,次小的二叉树,将新的二叉树加入F中
④ 重复② ③ ,知道只剩下一个二叉树为止
哈夫曼树的构建,编码的实现代码
//节点对象 public class Node { String data; //节点标识符 double weight; boolean flag; //标记是否被使用 Node leftChild; Node rightChild; Node parent; public Node(String data,double weight){ this.data = data; this.weight = weight; this.flag = false; this.leftChild = null; this.rightChild = null; this.parent = null; } public Node(String data, double weight, boolean flag, Node leftChild, Node rightChild, Node parent) { super(); this.data = data; this.weight = weight; this.flag = flag; this.leftChild = leftChild; this.rightChild = rightChild; this.parent = parent; } @Override public String toString() { return "Node [data=" + data + ", weight=" + weight + "]"; } }
/** * @author Robert */ public class HaffumaTree { public static final char BASE = 'A'; //哈夫曼树构建 public static Node[] createTree(double[] in){ int m = in.length*2 - 1; //第i层有n个叶子节点,那么总的节点最多有2n-1(可以理解为最后一层的节点-1,就是这棵树除这一层,之前层所有节点之和) Node[] nodes = new Node[m + 1]; //初始化结点数组 for(int i=0;i<in.length;i++) { nodes[i] = new Node(String.valueOf(BASE)+i,in[i]); } for(int i=in.length;i<m;i++) { Node firstMin = getMinWeight(nodes, i-1); //最小 firstMin.flag = true; Node secondMin = getMinWeight(nodes, i-1); //次小 secondMin.flag = true; nodes[i] = new Node(String.valueOf(i + BASE),firstMin.weight+secondMin.weight); //父节点构建 nodes[i].leftChild = firstMin; nodes[i].rightChild = secondMin; firstMin.parent = nodes[i]; secondMin.parent = nodes[i]; } return nodes; } //查找最小值,也可以使用先排序,然后直接选取前两个元素。 public static Node getMinWeight(Node[] nodes,int endIndex){ Node minNode = nodes[endIndex]; for(int i=0;i<endIndex;i++) { if(!nodes[i].flag && nodes[i].weight<minNode.weight){ minNode = nodes[i]; } } return minNode; } //哈弗曼编码,从叶子结点开始 public static int[][] haffumanCode(Node[] nodes,int n){ int[][] haffumanCode = new int[n][n]; for(int i=0;i<n;i++){ //不知道有多少位,所以选择逆向存储 int start = n-1; Node now = nodes[i]; Node pa = now.parent; for(;pa!=null;now=pa,pa=pa.parent){ if(pa.leftChild.equals(now)){ haffumanCode[i][start--] = 0; } else { haffumanCode[i][start--] = 1; } } //做结尾的标识,方便后续输出 haffumanCode[i][start--] = -1; } return haffumanCode; } public static void main(String[] args) { double[] w = {7,5,2,4}; //创建哈夫曼树 Node[] tree = createTree(w); //得到哈夫曼编码 int[][] code = haffumanCode(tree, w.length); System.out.println("=============="); for(int i=0;i<w.length;i++) { System.out.print(tree[i].data + ":"); for(int j=0;j<code[i].length;j++) { if(code[i][j] == -1) { for(int k=j+1;k<code[i].length;k++) { System.out.print(code[i][k]); } break; } } System.out.println(); } } }
总结
① 在现实生活中,有时候哈夫曼树未必比某些二叉树要有优势。
② 自己用List链表,快排方法构建出来的哈夫曼树,之后不知道怎么来求编码,无奈-.-!,最后还是回归到了数组。
能力有限,如果哪位同学知道,望告知一下。
-
哈夫曼(Huffman)树构建方法,编码方法
2018-11-03 13:11:34哈夫曼树是构建哈夫曼编码的一种方法,构造方式如下: 如有队列 {a, b, c, d, e, f, g} 其权值为 {05, 24, 08, 17, 34, 04,13} 求对应a~g的Huffman编码。 注意一点的是,在构建的时候要把...哈夫曼树是构建哈夫曼编码的一种方法,构造方式如下:
如有队列 {a, b, c, d, e, f, g}
其权值为 {05, 24, 08, 17, 34, 04,13}
求对应a~g的Huffman编码。
注意一点的是,在构建的时候要把 小的数放左子树,大的放右子树,然后再构建。最后的结构为
a:0011 (编码长度为4)
b:01 (编码长度为2)
c:000 (编码长度为3)
d:101 (编码长度为3)
e:11 (编码长度为2)
f:0010 (编码长度为4)
g:100 (编码长度为3)
e:11 (编码长度为2)
-
c++ 构建哈夫曼树
2020-05-08 18:55:09接下来介绍哈夫曼树的构造方法,假设给定n个字符及其对应的频率(出现次数),求出用哈夫曼编码后编码串的长度。 比如: 4 //字符个数 a 1 b 2 c 3 d 4 会返回19。(如果不知道怎么算请看上面链接的博客) c++构造 ...简介
哈夫曼树是一种用来对字符进行编码的数据结构,可以根据字符的使用频率来决定字符的二进制表示,使得转化后的二进制序列尽可能短。
哈夫曼树的具体介绍见此博客用漫画介绍哈弗曼树接下来介绍哈夫曼树的构造方法,假设给定n个字符及其对应的频率(出现次数),求出用哈夫曼编码后编码串的长度。
比如:4 //字符个数 a 1 b 2 c 3 d 4
会返回19。(如果不知道怎么算请看上面链接的博客)
c++构造
方法一
首先可以想到用优先队列,将包含频率信息的节点加入队列,然后每次从队列中拿出两个最小的节点a和b,求出频率和,构造新的节点,其左右子节点分别指向a和b,将新节点加入队列。重复此过程直至队列中只剩一个节点。
在上面的步骤中我们模拟哈夫曼树的构造过程,确确实实地构造出一棵树来,接下来只需要由这棵树的根节点开始遍历,找到每个叶子节点,将它们的值(即频率)和深度(即编码长度)的乘积加起来,就是我们要的结果。
时间复杂度:O(nlogn)
ps:这个代码没有释放指针,但是这不是要点,所以忽略了。#include<iostream> #include<queue> #include<unordered_map> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; struct Node { long long val; Node* left, *right; Node(long long val) { this->val = val; left = NULL; right = NULL; } }; struct cmp { bool operator()(const Node* a, const Node* b) const{ return a->val > b->val; } }; long long search(Node* root, long long level) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return root->val * level; return search(root->left, level + 1) + search(root->right, level + 1); } int main() { long long n; cin >> n; if (n == 0) { cout << 0; return 0; } long long arr[n]; char c; for (long long i = 0; i < n; ++i) { cin >> c >> arr[i]; } if (n == 1) { cout << arr[0]; return 0; } priority_queue<Node*, vector<Node*>, cmp> pq; for (long long i = 0; i < n; ++i) { //if (arr[i] <= 0) continue; Node* t = new Node(arr[i]); pq.push(t); } if (pq.size() == 1) { cout << pq.top()->val << endl; return 0; } Node* root; while(pq.size() > 1) { Node* a = pq.top(); pq.pop(); Node* b = pq.top(); pq.pop(); Node* sum = new Node(a->val + b->val); sum->left = a; sum->right = b; root = sum; pq.push(sum); } cout << search(root, 0) << endl; }
方法二
如果不想用优先队列,不想自己写比较函数,可以怎样写呢?
注意到一个规律:每次从队列中拿出最小的两个节点按值相加,得到的新节点的值是递增的,假设我们只用普通的数组来存储最初的节点,并且用另一个数组来存储新增的节点,再用两个指针分别指向两个数组的下标,通过一定的控制(从左边数组拿或从右边数组拿)可以实现。具体请看代码。#include<cstring> #include<algorithm> #include<vector> #include<iostream> using namespace std; int n; vector<long long> a[2]; int idx[2]; inline long long popleft(int i) { return a[i][idx[i]++]; } inline long long getmin() { if (idx[0] >= (int)a[0].size()) { return popleft(1); } if (idx[1] >= (int)a[1].size()) { return popleft(0); } if (a[0][idx[0]] < a[1][idx[1]]) { return popleft(0); } return popleft(1); } int main() { cin >> n; if (n == 0) { cout << 0 << endl; return 0; } long long t1, t2; char c; for (int i = 0; i < n; ++i) { cin >> c >> t2; a[0].push_back(t2); } if (n == 1) { cout << t2 << endl; return 0; } sort(a[0].begin(), a[0].end()); long long ans = 0; for (int i = 1; i < n; ++i) { t1 = getmin(); t2 = getmin(); ans += t1 + t2; a[1].push_back(t1 + t2); } cout << ans << endl; return 0; }
时间复杂度依然是O(nlogn)。
-
哈夫曼树的构建及哈夫曼编码的求解
2019-07-05 16:58:37构建最小生成树的方法:从权重中选择两个最小的,构成一棵树,并将新生成的权重加入之前的权重中HT【i】.weight中,直到构成一棵完整的二叉树。 话不多说,直接上代码。 #include "stdio.h" #include "stdlib.h" #...总体思路:先构建一棵最小生成树,然后左孩子给它标上‘0’,右孩子标上‘1’,然后从叶子节点追溯到根,存储到数组cd【】中。
构建最小生成树的方法:从权重中选择两个最小的,构成一棵树,并将新生成的权重加入之前的权重中HT【i】.weight中,直到构成一棵完整的二叉树。
话不多说,直接上代码。
#include "stdio.h" #include "stdlib.h" #include "string.h" typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树 typedef char ** HuffmanCode;//动态分配数组存储哈夫曼编码 //不能出现TH[1]->parent的结构 void Select(HuffmanTree HT,int j,int *s1,int *s2)//j为结点的个数,s1为最小值的下标,s2为次小值的下标 { int cmin = 100,min = 100; int k = 1; while(k <= j) { if((HT[k]).parent == 0) { if(HT[k].weight < min) { min = HT[k].weight; *s1 = k; } else if(HT[k].weight >= min&&HT[k].weight <= cmin) { cmin = HT[k].weight; *s2 = k; } } k++; } HT[*s1].parent = 0; HT[*s2].parent = 0; } //w用来存放n个字符的权值(w > 0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC void HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,int *w,int n)//HC使用三重指针的原因,将HC的值带出去 { HuffmanTree p; int s1,s2,m,i;//s1为最小数的下标,s2为次小数的下标 int start,c,f;//start字符最开始的下标,c为 char *cd;//用来存储哈夫曼编码 if(n <= 1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); for(p = HT,i = 1;i <= n;i++,w++)//给前n个结点赋初值,从1开始 { p[i].weight = *w; p[i].lchild = 0; p[i].rchild = 0; p[i].parent = 0; } //建一棵哈夫曼树 for(i = n + 1;i <= m;i++) { Select(HT,i - 1,&s1,&s2);//挑选出最小和次小元素,并用s1,s2带出 HT[s1].parent = i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; HT[i].parent = 0; } //求哈夫曼编码 (*HC) = (HuffmanCode)malloc((n + 1) * sizeof(char *));//分配n个字符编码的头指针向量 cd = (char *)malloc(n * sizeof(char));//分配求编码的工作空间 cd[n - 1] = '\0'; for(i = 1;i <= n;i++) { start = n - 1;//编码结束的位置 for(c = i,f = HT[i].parent;f != 0;c = f,f = HT[f].parent) //从叶子到根逆向求编码 { if(HT[f].lchild == c) cd[--start] = '0'; else cd[--start] = '1'; } (*HC)[i] = (char*)malloc((n-start) * sizeof(char));//为第i个字符编码分配空间 strcpy((*HC)[i],&cd[start]);//此处不能传cd,因为下标不一定从0开始 } free(cd); } int main() { int w[] = {15,25,45,5,10}; int n,i; HuffmanTree HT = NULL; HuffmanCode HC = NULL; n = sizeof(w)/sizeof(int); HuffmanCoding(HT,&HC,w,n); for(i = 1;i <= n;i++) { printf("%d的哈夫曼编码为:",w[i - 1]); printf("%s\n",HC[i]); } return 0; }
-
[数据结构] 哈夫曼树HuffmanTree、哈夫曼编码的c/c++语言实现
2020-04-11 18:46:55[数据结构] 哈夫曼树HuffmanTree、哈夫曼编码的c/c++语言实现什么是哈夫曼树先给出定义公式:举个例子:数学方法构建哈夫曼树构建方法描述例子第一步:先找出权值最小的两个结点第二步以这两个结点为叶子,构建一个... -
软考中级——构建哈夫曼树
2020-08-12 14:58:23这里有小伙伴不会构建哈夫曼树,我知道的方法有两个,这里把我认为简单的方法告诉大家: 如:5,29,7,8,14,23,3,11这些节点构建哈夫曼树。 一,排序,从小到大将所有节点排序 3,5,7,8,11,14,23,29 ... -
哈夫曼树
2019-07-28 23:02:57哈夫曼树的构建方法: 1)将所有结点放进集合 K ; 2)若集合 K 中剩余结点大于 2 个,则去除其中权值最小的两个结点,构造它们同时为某个新结点的左右子节点,该新结点是它们共同的双亲结点,设定它的权值为左右两... -
树——哈夫曼树
2020-02-02 16:17:50哈夫曼树: 带权节点,对应的带权路径最小的一种树构造方法 以图一为例:51+24+33+41+4*2=34 怎么构建一个哈夫曼树,它又有什么特性呢 特点二:每个元素都是叶节点,n个叶节点有一个n-1个父节点再加最大父节点... -
【数据结构】——哈夫曼树及哈夫曼编码
2020-06-15 22:32:02一、哈夫曼树(一)什么是哈夫曼树(二)哈夫曼树的构建(三)哈夫曼树的几个特点(四)java代码构建哈夫曼树二、哈夫曼树拓展:构建最优k叉树三、哈夫曼编码 一、哈夫曼树 (一)什么是哈夫曼树 哈夫曼树也叫最优树... -
哈夫曼树解码
2020-10-22 18:54:23以下为手动算出哈夫曼树并暴力构建树的方法 #include<stdio.h> #include<malloc.h> #include<stdlib.h> #include<string.h> typedef struct tree { char element; struct tree* left; ... -
HDU2527 构建哈夫曼树的灵巧运用
2012-11-07 18:50:14上课老师说了知道哈夫曼树叶子 不构图求二叉树的权 就是在构造哈夫曼树的时候运用构图的方法 把 每个结点的值加起来就是该数的权 证明 W=∑叶子权*该叶子层数 除了叶子的结点和就是这个树的权 构造一个树就知道... -
基于哈夫曼树的文本数据压缩
2019-12-27 11:41:15基于哈夫曼树的文本数据压缩 课题内容: 1、学习哈夫曼编码原理和哈夫曼树的构造方法; 2、针对序列(whatever is worth doing is worth doing ...在这里我们先了解一下哈夫曼树构建原理 思路1.掌握知识点,明确要解... -
哈夫曼树Huffmantree
2017-05-11 18:36:01实现哈夫曼树,首先要了解这些知识: 路径长度:一个节点到另一个节点的边数;...构建哈夫曼树的方法: 将权值最小的两个节点作为左右孩子,它们的权值之和即为双亲结点的权值,再从权值集合其他结点 -
链表之哈夫曼树
2019-12-23 21:59:29在学习了链表的基本使用方法后,我尝试使用链表构建了比较常见的一种树形结构: 哈夫曼树 这里不对哈夫曼树进行介绍,直接开始 首先是定义子节点 class node { public: char c; int num; node* left; //叶子... -
哈夫曼树及其Java实现
2019-07-11 16:31:50转载自:图文详解JAVA实现哈夫曼树 概念: ...它的构建方法很简单,依次选取权值最小的结点放在树的底部,将最小的两个连接构成一个新结点,需要注意的是构成的新结点的权值应该等于这两个结点的权值... -
哈夫曼树与哈夫曼编码
2018-01-05 10:12:00Huffman1952年发明的一种构建极小多余编码的方法。在计算机数据处理中,哈夫曼编码使用变长编码表对源符号进行编码,出现频率较高的源符号采用较短的编码,出现频率较低的符号采用较长的编码,使编码之后的字符串... -
三叉哈夫曼树的分析
2016-07-08 09:16:113、在2中的算法构建出三叉或者N叉哈夫曼树一定是最优的吗? 以上的问题我就不给予具体的answer,其实二叉哈夫曼树就应用了贪心算法,对于该算法不熟悉的同学赶紧去补补书 贪心算法无法保证全局最优,而是提供了... -
数据结构(C语言)实验七:哈夫曼树与哈夫曼编码
2021-02-15 11:57:00熟练掌握huffman树的构建方法以及huffman编码。 二、预备知识 1. 哈夫曼树的存储结构 typedef struct { unsigned int weight; unsigned int parent, lchild, rchild; }HTNode,*HuffmanTree; //动态分配数组... -
哈夫曼树及哈夫曼编码到底是怎么回事儿?
2020-06-14 18:47:19哈夫曼树: 给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl)达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(HuffmanTree),或霍夫曼树。 赫夫曼树是带权路径...当然构建方法有好多 -
数据结构_哈夫曼树定义、构造方法及实现(C/C++)
2020-03-02 22:45:33基本概念: 结点带权路径长度(Weight Path ...哈夫曼树的构建: 给定n个带权结点,将n个结点构成n棵二叉树的森林,每棵二叉树仅有一个根结点,没有左右子树。 从n个结点中选出两个根结点权值最小的树分别作为左右... -
哈夫曼树(Huffman)编码 压缩数据编程
2020-10-15 23:37:39网上有不少人介绍哈夫曼树的生成方法,但是对于实现方式却都只字不提,只是放了代码,这里简单介绍一下一个我自己编写的哈夫曼树的实现方式。 如果你完全不知道哈夫曼树的生成方式,那么本篇文章并不适合你阅读,... -
数据结构集中实践 哈夫曼树实验报告
2019-01-07 09:54:431.根据给出的字符以及这些字符的使用频率构建哈夫曼树。 2.根据哈夫曼树对字符进行哈夫曼编码,并保存这些编码。 三、实验原理、方法和手段 试构造出问题模型,并编程实现这一问题的求解。根据实验内容编程,... -
哈夫曼树数据机构的建立及哈夫曼编码与解码的C++实现
2016-06-08 21:46:48将一组无序数列建立最小堆,从最小堆中弹出两个最小的元素作为左右儿子其和为父节点构建一个树,将父节点加入最小堆,再次调用以上方法重复构建树,最终即可构建一棵哈夫曼树,哈夫曼树的特点有3个:1、 所有的序列... -
哈夫曼树与哈夫曼编码原理与代码
2020-07-09 17:02:04举一个例子:哈夫曼编码根据不同的字母(汉字)在文章中出现的频率不同构建不等长的编码,给出现频率最高的字最短的编码,给出现频率最低的字最长的编码,这样可以有效的节省空间,并且所有较短的编码都不是较长的... -
codeforces 700D 哈夫曼树 莫队
2016-08-19 20:52:10题意:给一个长度为n的数列a,q组询问,每组询问求将li到ri的区间中的数哈夫曼编码的长度。莫队,对于每一个询问处理该... 对于出现次数大于n√\sqrt{n} 的字符,用构建哈夫曼树的方法处理。时间复杂度O(nn√logn)O(n -
k叉树的性质_L3图论第03课 哈夫曼树
2020-12-21 14:54:16L3-图论-第03课 哈夫曼树哈夫曼编码❝1951年,哈夫曼在麻省理工学院(MIT)攻读博士学位,他和修读信息论课程的同学得选择是完成学期报告还是期末考试。导师罗伯特·法诺(Robert Fano)出的学期报告题目是:查找最有效... -
哈夫曼树学习笔记及1070 结绳 (25分)练习
2020-02-15 10:03:351.哈夫曼树的定义: 已知n个数,寻找一棵树使得树的所有叶子结点的权值恰好为这n个...2.构建方法: 在构建树的过程中,在已有结点中反复选择两个最小元素,合并,直至只剩下一个元素(根结点)。 3.经典问题–合并果...