(word 完整版)Matlab 函数实现哈夫曼编码算法
编写 Matlab 函数实现哈夫曼编码的算法
一、 设计目的和意义
在当今信息化时代,数字信号充斥着各个角落。在数字信号的处理和传输中,信源编码
是首先遇到的问题,一个信源编码的好坏优劣直接影响到了后面的处理和传输。如何无失真
地编码,如何使编码的效率最高,成为了大家研究的对象.
哈夫曼编码就是其中的一种,哈夫曼编码是一种变长的编码方案.它由最优二叉树既哈
夫曼树得到编码,码元内容为到根结点的路径中与父结点的左右子树的标识。所以哈夫曼在
编码在数字通信中有着重要的意义.可以根据信源符号的使用概率的高低来确定码元的长度.
既实现了信源的无失真地编码,又使得编码的效率最高.
二、 设计原理
哈夫曼编码(Huffman Coding)是一种编码方式,哈夫曼编码是可变字长编码(VLC)的
一种。uffman 于 1952 年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的
平均长 度最短的码字,有时称之为最佳编码,一般就叫作 Huffman 编码.
而哈夫曼编码的第一步工作就是构造哈夫曼树。哈夫曼二叉树的构造方法原则如下,假
设有 n 个权值,则构造出的哈夫曼树有 n 个叶子结点。 n 个权值分别设为 w1、w2、…、
wn,则哈夫曼树的构造规则为:
(1) 将 w1、w2、…,wn 看成是有 n 棵树的森林(每棵树仅有一个结点);
(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且
新树的根结点权值为其左、右子树根结点权值之和;
(3)从森林中删除选取的两棵树,并将新树加入森林;
(4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。