精华内容
下载资源
问答
  • 用C++进行哈夫曼编码计算信源熵及编码效率 统计各种概率
  • 本来是想着慢慢找时间按顺序补上这些数据结构的内容,但前几天有朋友找我写一个计算哈夫曼编码的程序(课程作业吧,好像~哈哈哈),所以就先把哈夫曼树的东西写下来。 先来介绍一下哈夫曼编码吧 哈夫曼树,二叉树的...

    哈夫曼编码


    本来是想着慢慢找时间按顺序补上这些数据结构的内容,但前几天有朋友找我写一个计算出哈夫曼编码的程序(课程作业吧,好像~哈哈哈),所以就先把哈夫曼树的东西写下来。

    先来介绍一下哈夫曼编码吧
    哈夫曼树,二叉树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
    哈夫曼编码则是根据字符出现频率(权重分布),用最少的位数来表示。(字符出现多的,用较短编码;字符出现少的,用较长编码)
    举个例子:好比这个字符串“abcddddddd”,如果用相同长度的编码来表示,4个不同数字则选用2位(a->00,b->01,c->10,d->11),那也就是需要 10 * 2 = 20长度;
    而使用哈夫曼编码,则根据权重(a->010,b->011,c->00,d->1),也就是需要:3+3+2+1*7 = 15长度。
    在这个例子中相比平均编码则少了25%(当然这个例子比较夸张啦哈哈哈。权重分布一般不会这样,在这里主要是想说明哈夫曼编码能起到压缩编码长度的作用)
    但是在取哈夫曼编码的时候,要避开前缀(有可能某个数的编码刚好是另外某个数的编码前缀),所以可以通过下面的方法计算出来。

    一、基于建哈夫曼树的方法
    算法过程:
    ①将输入的数值,每一个数值,分别都建立成一棵树(只有根节点的树),就形成了森林。
    ②将森林排序( 按权重,从大到小排序,选用插入排序即可,因为之后的排序每一次都只插入一个数值,只需要移动少量即可)
    ③取出后两棵树n1、n2,新创建一个根节点,然后将n1、n2作为其左右孩子,从而构成一棵新树(由新建根节点+n1(lchild)+n2(rchild)组成),将这棵新树插入森林中。
    ④重复②③,直到森林中只剩下一棵树,此时该树就是所求哈夫曼树。
    ⑤遍历每一个叶子(每一个叶子就是输入数值),根据遍历路径(往lchild则 +‘1’,往rchild 则 + ‘0’),每一个叶子对应的数值+编码result,即是其哈夫曼编码。

    代码实现:C++

    #include <bits/stdc++.h>
    using namespace std;
    typedef struct tree_node {
    	int temp;				//存数值/对应字符
    	int weight;				//存权重
    	tree_node* lchild;
    	tree_node* rchild;
    	tree_node(int t = -1, int w = 0) {	//非叶子结点,temp都等于-1
    		temp = t;
    		weight = w;
    		lchild = NULL;
    		rchild = NULL;
    	}
    };
    class huffma {
    public:
    	huffma() {
    		tree = new tree_node;
    	}
    	void destory_tree(tree_node* ntree) {
    		if (ntree != NULL) {
    			tree_node* lc = ntree->lchild;
    			tree_node* rc = ntree->rchild;
    			delete ntree;
    			if (lc != NULL)destory_tree(lc);
    			if (rc != NULL)destory_tree(rc);
    		}
    	}
    	~huffma() {
    		destory_tree(tree);
    	}
    
    	void input(int* data, int len) {	//一开始是选用vector<int>,但是朋友说输入是需要数组,所以也就在这里转一下vector<int> 哈哈哈
    		vector<int>data_in(data, data + len);
    		make_trees(data_in);		//建树
    	}
    	void output() {	//输出
    		vector<int> a;
    		print_result(tree,a);			//输出编码
    	}
    private:
    	tree_node* tree;		//做根结点
    	vector<tree_node*> trees;		//森林
    
    	void sort_trees() {		//森林排序:插入排序
    		for (int i = 1; i < trees.size(); i++) {
    			tree_node* change = trees[i];
    			int j = i - 1;
    			while (change->weight > trees[j]->weight) {
    				trees[j + 1] = trees[j];
    				j--;
    				if (j == -1)break;
    			}
    			trees[j + 1] = change;
    		}
    	}
    
    	void built_it() {			//建树
    		int len = trees.size();
    		sort_trees();
    		while (len >= 3) {
    			tree_node* n1 = trees.back();
    			trees.pop_back();
    			tree_node* n2 = trees.back();
    			trees.pop_back();
    			tree_node* new_node = new tree_node(-1, n1->weight + n2->weight);//temp = -1,表示非叶子结点
    			new_node->lchild = n1;
    			new_node->rchild = n2;
    			trees.push_back(new_node);
    			sort_trees();
    			len = trees.size();
    		}		//剩下最后两棵,直接作为创建的根节点的左右孩子
    		tree_node* n1 = trees.back();
    		trees.pop_back();
    		tree_node* n2 = trees.back();
    		trees.pop_back();
    		tree->lchild = n1;
    		tree->rchild = n2;
    	}
    	void print_result(tree_node* p, vector<int> a) {		//递归,找出编码
    		if (p->temp != -1) {
    			cout << p->temp << "->";
    			for (int i = 0; i < a.size(); i++) cout << a[i];
    			cout << endl;
    		}
    		a.push_back(0);
    		if (p->lchild != NULL)print_result(p->lchild, a);
    		a.pop_back();
    		a.push_back(1);
    		if (p->rchild != NULL)print_result(p->rchild, a);
    		a.pop_back();
    
    	}
    	void make_trees(vector<int> data) {		//vector<int>存入森林,并built_it()
    		for (int i = 0; i < data.size(); i++) {
    			tree_node* new_tree = new tree_node(data[i], data[i]);
    			trees.push_back(new_tree);
    		}
    		built_it();
    	}
    };
    int main() {
    	huffma s;
    	int data[8] = { 2,5,6,8,13,19,25,36 };		//输入:元素表示:字符和权重(相同)
    	int len = sizeof(data) / sizeof(data[0]);
    	s.input(data, len);
    	s.output();
    	return 0;
    }
    

    二、不通过正常建树的方法
    算法过程:
    分别用两个数组in、out,来存下结点。
    用in数组存下输入值,模拟方法一中的森林。
    用out数组存下每次从in中取出来的结点。
    过程:
    ①将输入数组存入 数组in
    ②对 数组in 进行排序(从大到小,这样在后两位、插入时都不需要移太多位)
    ③取出 数组in 的后两位,分别对其.result 赋值0或1,存到 数组out中,新建一个元素(=两元素的权值合,并记录子元素的位置,也即由两位合成后,记录这两位在 数组out 中的位置),将新建的元素插入 数组in。
    ④重复②③,知道 数组in 为空。
    ⑤此时由后往前遍历 数组out,对每一位元素进行操作:根据该元素的记录位置,找到 数组out 中对应的元素,添加上该元素的赋值。(按照下图来说明比较容易)


    /*
    好吧,其实两个方法是同样的思路,但是前一种会去体系的建成一棵哈夫曼树后遍历找到哈夫曼编码,而后一种方法则是通过建立各元素之间的关系来找到哈夫曼编码。
    当然 ,第一个方法涉及各种指针,其中还没有去delete掉那部分不使用到的内存,造成内存泄漏,所以如果数量级大了可能就内存溢出了,所以还有待修改优化。
    至于第二种方法,其实就是运用了方法一的计算方法,但是没有建成一棵哈夫曼树,所以如果在其他有关树的操作时则会很麻烦。所以只是来算出这个哈夫曼编码而已哈哈哈。
    当然方法一比较直接,编程方法也比较简单。相比方法二则需要理清晰其间关系与操作顺序。在此建议:将整个过程想法写出,再编程。这是个好习惯!!!可以省去很多麻烦,特别是逻辑上的错误
    */
    代码实现:C++

    #include <bits/stdc++.h>
    using namespace std;
    typedef struct tree_node {
    	int temp;		//存元素:字符
    	int weight;		//权重
    	vector<int> result;		//存其result
    	vector<int> flag;		//存其两个合成的子元素的out数组位置
    	tree_node(int temp = -1, int weight = 0) {		//新建元素皆temp = -1
    		this->temp = temp;
    		this->weight = weight;
    	}
    };
    void node_sort(vector<tree_node>& data_in) {		//插入排序
    	for (int i = 1; i < data_in.size(); i++) {
    		tree_node change = data_in[i];
    		int j = i - 1;
    		while (change.weight > data_in[j].weight) {
    			data_in[j + 1] = data_in[j];
    			j--;
    			if (j == -1)break;
    		}
    		data_in[j + 1] = change;
    	}
    }
    void get_result(vector<tree_node>& data_out,int ing) {		//根据flag,去写对应out[]的result
    	if(data_out[ing].flag.size() > 0){
    		for(int i = 0;i< data_out[ing].result.size();i++){
    			data_out[data_out[ing].flag[0]].result.push_back(data_out[ing].result[i]);
    			data_out[data_out[ing].flag[1]].result.push_back(data_out[ing].result[i]);
    		}
    	}
    }
    void opperate(int* data, int len) {				//整个过程
    	vector<tree_node>data_in;		//数组in
    	vector<tree_node>data_out;		//数组out
    	for (int i = 0; i < len; i++) {		//读入输入
    		tree_node node = tree_node(data[i], data[i]);
    		data_in.push_back(node);
    	}
    	node_sort(data_in);			//排序
    	int k = 0;
    	while (data_in.size() > 1) {		//重复②,③
    		tree_node n1 = data_in.back();
    		data_in.pop_back();
    		n1.result.push_back(0);		//较小元素,则添加result    '0'
    		data_out.push_back(n1);
    		tree_node n2 = data_in.back();
    		data_in.pop_back();
    		n2.result.push_back(1);		//较大元素,则添加result    '1'
    		data_out.push_back(n2);
    		tree_node n3 = tree_node(-1, n1.weight + n2.weight);
    		n3.flag.push_back(k++);
    		n3.flag.push_back(k++);
    		data_in.push_back(n3);
    		node_sort(data_in);
    	}
    	//从后往前遍历
    	for (int i = data_out.size()-1; i >= 0; i--)get_result(data_out, i);
    	//依次输出out数组里(temp !=1 的元素) 
    	for (int i = 0; i < data_out.size(); i++) {
    		if (data_out[i].temp != -1) {
    			cout << data_out[i].temp << "->";
    			for (int j = data_out[i].result.size() - 1; j >= 0; j--)cout << data_out[i].result[j];
    			cout << endl;
    		}
    	}
    }
    int main() {
    	int data[8] = { 2,5,6,8,13,19,25,36 }; 		//输入:元素表示:字符和权重(相同)
    	int len = sizeof(data) / sizeof(data[0]);
    	opperate(data, len);
    	return 0;
    }
    

    两个程序运行结果分别如下:
    在这里插入图片描述
    (左为方法一,右为方法二。结果一致,但方法二的结果是从权重低的开始排起,所以在使用中,“对比”、“查找”等操作则会方便很多,从时间上来说,两个方法差别不大,测试了128个字符时,并没有多大的时间差别)

    可优化部分:
    选用插入排序,主要是考虑到后续插入时只插入一个,都是O(n),应该时间消耗不是很大。可能选用其他排序更优,但是有一点值得提的是,插入排序是稳定排序(稳定排序,当新建结点 与 输入元素 权重相同时,可以优先取新建结点,这样会使较深层叶子结点用少一丢丢的编码长度,当然我只是脑补一下这个结果,真实情况再来探讨,所以先保留为待优化空间)
    想来最终还是选择插入排序,因为在有序序列的单次插入时,最快的还是插入排序。
    在修改下一层的result时,总是用
    for(int i = 0;i< data_in.size();i++)data.push_back( data_in[i]),这里重复度很高。这里有很大的时间浪费在这里。每下一个结点就得重新复制一遍,所以这里有很大的优化空间。
    目前已经修改好(2020.12.23修改),修改主要是用同一个vector在每次左孩子递归前push_back(0),递归完左孩子再pop_back()掉,再push_back(1),这样改的结果就是很好的省去了一直重复复制vector的开销,但是不好的地方就是只能在过程中找出结果,并不能直接保存到每一个结点里。
    同时,此次修改还修改了关于析构函数方面,因为之前只想着树建完输出就整个程序结束了就全部释放了,所以没去考虑内存泄漏的事。现在补上析构函数~哈哈哈哈

    目前就这样吧。哈哈,有其他待优化空间或者其他好的优化方法或者其他更好的解决方法,都很愉快可以来分享~

    展开全文
  • 满意答案tyx4953068推荐...先设权w=(31,22,18,14,10,4,1),n=7,则m=13,按照哈夫曼算法可以构造一棵哈夫曼树如下:10040 6022 18 31 2914 1510 54 1末端结点为22,18,31,14,10,4,1,你自己把上面的加上线连成一棵...

    满意答案

    dcebd7a0de6265b6ccae5ead692f1eab.png

    tyx4953068

    推荐于 2017.11.26

    dcebd7a0de6265b6ccae5ead692f1eab.png

    采纳率:43%    等级:11

    已帮助:10064人

    太复杂了,楼主一会记得多给我点分!谢谢啦!

    先设权w=(31,22,18,14,10,4,1),n=7,则m=13,按照哈夫曼算法可以构造一棵哈夫曼树如下:

    100

    40 60

    22 18 31 29

    14 15

    10 5

    4 1

    末端结点为22,18,31,14,10,4,1,你自己把上面的加上线连成一棵二叉树就行,记得左分支标0,右分支标1(为了得出后面的哈夫曼编码HC)

    然后需要列出HT初态表和HT终态表,如下:

    HT初态表 HT终态表

    weight parent lchild rchild weight parent lchild rchild

    1 31 0 0 0 31 12 0 0

    2 22 0 0 0 22 11 0 0

    3 18 0 0 0 18 11 0 0

    4 14 0 0 0 14 10 0 0

    5 10 0 0 0 10 9 0 0

    6 4 0 0 0 4 8 0 0

    7 1 0 0 0 1 8 0 0

    8 - 0 0 0 5 9 6 7

    9 - 0 0 0 15 10 5 8

    10 - 0 0 0 29 12 4 9

    11 - 0 0 0 40 13 2 3

    12 - 0 0 0 60 13 1 10

    13 - 0 0 0 100 0 11 12

    最后得出哈夫曼编码HC:

    1——>10

    2——>00

    3——>01

    4——>110

    5——>1110

    6——>11110

    7——>11111

    平均码字长度为(0.31+0.22+0.18)×2+0.14×3+0.1×4

    +(0.04+0.01)×5=2.47

    编码效率为[(1-0.01)×3+0.01×2]/2.47=1.21

    解答完毕!

    补充:对于其中的编码效率问题本人有点淡忘,我选择的是用

    普通平均编码长度除上了哈夫曼平均编码长度得出,不知对否。

    辛苦半天,望楼主能赐我分数,不胜感激!

    注:提交后发现格式不太规整,对于哈夫曼树谁是谁的左孩子、右孩子比较容易分出(左右孩子结点相加可知父亲结点),对于HT初态表和HT终态表1列1列的看就行!其中数字第一列为序号,从第2列到第9列分别对应HT初态表的weight parent lchild rchild 和HT终态表的weight parent lchild rchild 。

    272分享举报

    展开全文
  • 这个代码是用C/C++实现哈夫曼编码并将编码输出。 文本为操作者输入,,对各字符进行频率统计,然后进行哈夫曼编码,并将编码结果输出,同时可求得平均码长。
  • 这是算法实验课上哈夫曼的代码,大家可以参照一下,在自己理解理解
  • Matlab 函数实现哈夫曼编码的算法 一 设计目的和意义 在当今信息化 代 数字信号充斥着各个角落 在数字信号的 理和 中信源 是首先遇到的 一个信源 的好坏 劣直接影响到了后面的 理和 如何无失真地 如何使 的效率最高 ...
  • 文章目录浅谈哈夫曼编码哈夫曼树哈夫曼树的构造哈夫曼树WPL值的计算哈夫曼编码引入哈夫曼编码哈夫曼编码的原理哈夫曼编码的编码压缩效率通过matlab代码实现哈夫曼编码思路及代码哈夫曼编码实例完整代码已上传到...

    文章目录

    浅谈哈夫曼编码

    哈夫曼树

    哈夫曼树的构造

    哈夫曼树WPL值的计算

    哈夫曼编码

    引入哈夫曼编码

    哈夫曼编码的原理

    哈夫曼编码的编码压缩效率

    通过matlab代码实现哈夫曼编码

    思路及代码

    哈夫曼编码实例

    完整代码已上传到[Github](https://github.com/cheunghonghui/Huffman_Coding)

    浅谈哈夫曼编码

    美国计算机科学家大卫·霍夫曼(David Albert Huffman)在1952年“种了”一棵树?——哈夫曼树。

    哈夫曼树

    哈夫曼树的构造

    霍夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。

    摘自维基百科——霍夫曼编码

    哈夫曼树WPL值的计算

    树的路径长度是从树根到每一结点的路径长度之和,记为WPL。

    WPL=(W1∗L1+W2∗L2+W3∗L3+...+Wn∗Ln)

    WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)WPL=(W1∗L1+W2∗L2+W3∗L3+...+Wn∗Ln)

    N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,…n)。

    举一栗子

    有这么一颗哈夫曼树:

    33c78cd6ecc67675bae97f1a9b16f799.png

    圆圈里面的数值为权值,连接的树干为路径,可计算其WPL:

    WPL=(0.5∗1+0.25∗2+0.125∗3+0.125∗3)=1.75

    WPL = (0.5*1+0.25*2+0.125*3+0.125*3)= 1.75WPL=(0.5∗1+0.25∗2+0.125∗3+0.125∗3)=1.75

    一个叶子结点出现频率越高,就让他分布在离根结点越近的地方,也就是根结点走到该节点经过的路径长度越短,这样所构成的树称为哈夫曼树,所得WLP也最小。

    哈夫曼编码

    引入哈夫曼编码

    有一组字符信息 “cbadd”,共有5个字符。

    用普通等长码的表示方法时,每个英文字母均占用一个字节,即8个比特。

    故共需要5*8 = 40位,显然这是一种较浪费内存的储存编码方式。

    有小伙伴提出,假若我们给他编上不等码,那岂不是能减少所占用的内存了嘛。

    这个idea?不错,那么我们应该要怎么编码呢。

    试试随意编码,令a:00 ,b:01 ,c:0 ,d:1

    字符

    随意编码

    a

    00

    b

    01

    c

    0

    d

    1

    “cbacd” 的编码为 “0010001”

    肉眼可见通过随意编码“cbadd”占用的内存为7位,这样子明显能减少编码所占用的内存。小伙伴们开始觉得,嗯,这个方法不错,以后就这样编码好嘞。

    可是细心的同学就会注意到,通过随意编码是能减少储存信息所占用的内存,可是在解码的过程中“0010001”可译为“ccdcccd”、’“cbcad”、“adacd”等多种结果,可见随意编码可能造成信息解码二义性甚至多义性的结果,所以这个方法需要改进。

    既想编码占用内存小,解码结果又唯一表示原信息,哈夫曼在哈夫曼树下冥思苦想,抬头的霎那间看见哈夫曼树那奇怪而有规律的二叉分枝,顿时有了灵感,想到了一种全新的编码方式,后来人们称之为哈夫曼编码。

    哈夫曼编码的原理

    设有一信源产生四种字符a、b、c、d,他们出现的概率分别为0.125,0.125,0.5,0.25。首先我们按照他们出现的概率从小到大依次排列,将最小的两个概率提取出来作为左右孩子节点(一般默认左孩子所在路径为“0”,右孩子所在路径为“1”)相加得到根结点。

    此后将跟节点数值加入到队列中重新排队,同样步骤将最小的两个概率提取出来作为孩子节点相加得到根结点,依次操作,直至队列中的概率元素全部清空。最后得到哈夫曼树,生成四种字符的哈夫曼编码。

    字符

    a

    b

    c

    d

    概率数值

    0.125

    0.125

    0.5

    0.25

    第一次排序

    1

    2

    4

    3

    概率数值

    0.25

    0.5

    0.25

    第二次排序

    1

    3

    2

    概率数值

    0.5

    0.5

    第三次排序

    1

    2

    为轻松了解哈夫曼树形成的整一个过程,我们来看图

    f324649cf6c1fade94637c40522f8fed.png

    首先将四个概率进行排序,a(0.125)和b(0.125)提取出来相加便成根节点1(0.25),将根节点(0.25)和剩下的c(0.5)、d(0.25)进行新一轮排序;

    取最小两值根节点1(0.25)和d(0.25)作为叶子结点相加得到根节点2(0.5);

    f4c8cadc8647bcf791cdb4c9bc037dcd.png

    最后队列剩下根节点2(0.5)和c(0.5)相加形成根节点3(1),形成哈夫曼树。

    于此,我们可以写出字符abcd的哈夫曼编码分别如下

    字符

    哈夫曼编码

    a

    000

    b

    001

    c

    1

    d

    01

    (哈夫曼编码结果不唯一,和左右孩子结点编码“0”、“1”有关,本博客默认左孩子结点为“0”,右孩子结点为“1”。)

    通过哈夫曼编码所占的内存为3+3+1*2+2=10位。

    哈夫曼编码的编码压缩效率

    编码压缩效率又称压缩比

    编码压缩效率=等长码所占内存/哈夫曼编码所占内存

    编码压缩效率 = 等长码所占内存/哈夫曼编码所占内存编码压缩效率=等长码所占内存/哈夫曼编码所占内存

    如上面所举例子,编码压缩效率:

    (5 * 8)/(3+3+1*2+2)= 4

    二者相比,使用哈夫曼编码能大大提高编码压缩效率。

    通过matlab代码实现哈夫曼编码

    思路及代码

    输入需要编码的文本信息

    inData = 'cbacd'; %输入文本

    对信息进行字符频率统计

    %%%字符频率统计

    uniqueCharacter=unique(inData);%计算有多少个不重复的字符串

    for i=1:length(uniqueCharacter)

    uniqueCharacter_num(i)=length(strfind(inData,uniqueCharacter(i))); %统计字符的数目

    uniqueCharacter_p(i) = uniqueCharacter_num(i)/length(inData)%不同字符出现的概率

    end

    uniqueCharacter %显示字符

    uniqueCharacter_num %显示个数

    uniqueCharacter_p %显示不同字符出现的概率

    进行哈夫曼编码

    %%创建哈夫曼树

    %对字符出现的概率按照从低到高排序

    p = uniqueCharacter_p

    [a,b]=sort(p); %对p概率矩阵进行排列

    m(1,:) = b;

    for i = 1:length(a)

    c(i) = uniqueCharacter(b(i));%更新字符队列的排序

    end

    q = sort(p); %更新概率顺序

    n = length(uniqueCharacter_p);

    for i = 2:n

    matrix(i-1,2) = c(1); %在matrix中记录左孩子

    matrix(i-1,3) = c(2); %在matrux中记录右孩子

    matrix(i-1,1) = double(i-1); %在matrix中记录根节点

    c(2) = double(i-1);%此处补充数值1,目的是为了以后排序该位置总排在最后,不被处理

    q(2) = q(1) + q(2); %更新根节点数值

    q(1) = 1;

    %对新的概率组合进行排序

    [a,b]=sort(q);

    [a1,b1] = sort(b);

    m(i,:)=b1; %%进行两次sort排记录记录概率对应的位置

    temp_c = c; %引入中间变量

    temp_q = q;

    for i = 1:length(a1)

    c(i) = temp_c(b(i));%更新字符队列的排序

    q(i) = temp_q(b(i));

    end

    end

    读取哈夫曼编码

    %读哈夫曼编码

    code = uniqueCharacter';

    for i = 1:n

    [temp_code,n] = Coding(matrix,uniqueCharacter(i));

    code(i,3:n+2) = temp_code

    end

    function [code,n] = Coding(matrix,character)

    [a,b] = size(matrix);

    for i = 1:a

    [row,col] = find(matrix(:,2:3)==character);

    character = matrix(row,1);

    if col == 1

    temp_code(i) = '0';

    else

    temp_code(i) = '1';

    end

    code(i) = temp_code(i);

    if row == a

    break

    end

    end

    %此刻需要将编码结果倒转

    temp_code = code;

    n = length(code);

    for i = 1:n

    code(i) = temp_code(length(code)-i+1) ;

    end

    end

    计算编码压缩效率

    e = (sum(uniqueCharacter_num)*8)/sum(len.*uniqueCharacter_num)

    哈夫曼编码实例

    完整代码已上传到Github

    请依据哈夫曼编码的方法对如下的字符进行编码,并计算产生的码流的编码压缩效率:

    练习一:“abcdaabbccaaabbbcfaaaabbbccdffeeeaaabbbcccdefabcde”

    e2308c3253deffd61b99f62232791ce2.png

    练习二:“i am a student i study iot subject in guangzhou university i like the subject and will work hard and do my best to achieve a high score in final examination”

    3909a241d2d0a8f987ddca886e28f2d6.png

    展开全文
  • 哈夫曼编码的c语言实现,代码中有注释。有编码和译码功能,能输出每个字符的Huffman码。可以输入一段Huffman码反应成文本,也可以输入一段文本翻译成Huffman码。计算了信源熵,编码效率,和平均编码长度。
  • 对26个英文字母(已知它们的概率分布)进行了哈夫曼编码,并计算编码效率。有助于大家理解哈夫曼编码以及信息论的相关知识哦。
  • 哈夫曼编码例题

    千次阅读 2020-05-18 20:57:28
    62题选a

    62题选a

     

    展开全文
  • 哈夫曼树与哈夫曼编码

    千次阅读 2020-04-07 17:59:55
    Huffman Tree,中文名是哈夫曼树或霍夫曼树,它是最优二叉树。 引入 如果有一篇文章,由若干个字符构成。每个ABC…Z都由7位编码,文章有1w个字符,那么有7w位进行编码。一个字节8位,首位是0。需要占用1W个字节。 ...
  • 1、信息论与编码课程大作业题 目: 二进制哈夫曼编码 学生姓名: 学 号: 2010020200 专业班级: 2010级电子信息班 2013年 5月 18日二进制哈夫曼编码1、二进制哈夫曼编码的原理及步骤1、1信源编码的计算设有N个码元...
  • 哈夫曼编码与压缩效率分析

    万次阅读 2017-07-09 17:51:10
    1、本实验中Huffman编码算法  (1)将文件以ASCII字符流的形式读入,统计每个符号的发生频率;  (2)将所有文件中出现过的字符按照频率从小到大的顺序排列;  (3)每一次选出最小的两个值,作为二叉树的两个叶子节点...
  • 哈夫曼编码练习题

    万次阅读 2020-04-21 19:37:04
    问题a 对于下面的数据构造一套哈弗曼编码: 字符 A B C D _ 出现概率 0.4 0.1 0.2 0.15 0.15
  • c语言的huffman编码及编码效率计算,采用两种编码方式,可选择
  • 举例理解哈夫曼树与哈夫曼编码

    万次阅读 2020-07-02 08:52:56
    举例理解哈夫曼树,C语言实现哈夫曼
  • 哈夫曼编码

    千次阅读 2020-12-21 17:08:34
    上一篇文章中提到数据结构:哈夫曼树,今天接着学习由哈夫曼提出编码方式,一种程序算法 简称:哈夫曼编码 在线转码工具:https://tool.lu/hexconvert/ 一、什么是哈夫曼编码? 与哈夫曼树一样,会不会有小伙伴对...
  • 哈夫曼编码是一种变长的字符编码方式,常用于对指定的字符集进行数据压缩,压缩率在 20%~90%。1. 问题描述现在有一个包含 5 个字符的字符表 {A,B,C,D,E},各字符出现的频率统计如表 1 所示。表 1:各字符出现的频率...
  • 5.1 Python图像处理之图像编码-哈夫曼编码 文章目录5.1 Python图像处理之图像编码-哈夫曼编码1 ...但是对于接近等概率分布的信源编码效率低。 设某信源产生有五种符号u1、u2、u3、u4和u5,对应概率P1=0.4,P2=0.1,P3=
  • 2 用于图像压缩,可根据图像的像素直方图来进行图像压缩,如PNG格式图像压缩使用的算法就包括哈夫曼编码,在编码过程中并未舍弃信息故哈夫曼编码是一种无损压缩方式。 3.哈夫曼解码 即给定由哈夫曼编码的结果10 11 ...
  • c++哈夫曼编码

    2020-04-14 16:12:13
    哈夫曼编码的基本步骤: (1)把概率最小的两个符号组成一个新的节点 (2)重复步骤,直到概率和为1 (3)总根节点开始到相应于每个符号的“树叶”,概率大的标“1”,概率小的标“0” (4)从根节点开始,对符号...
  • 香农编码 哈夫曼编码 费诺编码的比较

    万次阅读 多人点赞 2018-11-28 21:10:36
    香农编码 哈夫曼编码 费诺编码的比较 文章目录哈夫曼编码编码步骤例子优点缺点费诺编码编码步骤例子优点缺点香农编码编码步骤例子优点缺点参考 备注:本文除了例子与数据,其他内容均为整合网络资源。 哈夫曼编码 ...
  • 计算编码效率。 二、 算法描述 在计算机数据处理中,霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现几率的方法得到的,出现几率高的字母使用较短的...
  • 信息论与编码课程大作业题 目: 二进制哈夫曼编码学生姓名: 学 号: 2010020200 专业班级: 2010级电子信息班2013年 5月 18日二进制哈夫曼编码1、二进制哈夫曼编码的原理及步骤1、1信源编码的计算设有N个码元组成的...
  • 哈夫曼树&哈夫曼编码

    千次阅读 2018-06-11 20:38:38
    哈夫曼树也是最优二叉树,首先我们来看哈夫曼树的定义:给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。先再解释一下什么是带权...
  • 一.引例一般的学生成绩评定分为五个等级:优秀、良好、中等、及格、不及格,常见的代码描述如下:可以把上面的代码流程画成下面的树状流程图 由于大部分...如何能设计出这种效率最高的树结构?答案就是哈夫曼树。二...
  • 哈夫曼编码c实现.doc

    2021-05-20 13:24:04
    哈夫曼编码c实现.doc1中南大学信息论编码实验报告专业班级电子信息 1002指导老师赵颖2姓名付永军学号0909100707目录一.实验目的 3二、实验内容 .3三、实验原理 .41.1 使用 MATLAB 实现香农码编码。 41.2、使用 ...
  • Description本题中,读入n个字符所对应的权值,生成赫夫曼编码,并依次输出计算出的每一个赫夫曼编码。Input输入的第一行包含一个正整数n,表示共有n个字符需要编码。其中n不超过100。第二行中有n个用空格隔开的正...
  • 用C语言实现的哈夫曼编码 及信源熵的计算。源程序,无错误,直接运行。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,415
精华内容 1,366
关键字:

哈夫曼编码计算编码效率

友情链接: juanji.zip