声明:百科词条人人可编辑,词条创建和修改均免费,绝不存在官方及代理商付费代编,请勿上当受骗。详情 H码指的是哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。 霍夫曼编码方案是由David A Huffman在1952年开发的。这个算法依据数据的出现频率来编码数据从而可达到数据压缩的目的。用于编码数据的数据结构是一棵加权的二进制树,又叫霍夫曼树。 2.霍夫曼树是加权的,在数据流中出现频繁的元素在树的顶部,而很少出现的元素沉到树的底部; 3.霍夫曼树的每一个左边的分支分配一个0(或1)值,而每一个右边的分支赋值为1(或O)。 为了构造一棵霍夫曼树,需对数据进行两步操作。首先,构造一个唯一数据元素集和它们的频率的列表。这个列表按频率的升值排列。就是说,出现频率最高的数据元素排在表的下部。然后,构造实际的霍夫曼树。选择频率最低的两个元素组成树的叶。两片叶的父节点是它们的频率之和。这棵树被插入到列表中(由父节点的值来决定插到列表中的位置),而刚才用于组成这棵树的两个叶子被从列表中移除。继续这个过程直到列表中只留下一个元素,它就是最终的霍夫曼树的父节点。 为了将霍夫曼树用于编码数据,必须建立一种能唯一确定树中的每一个值的方法。具体做法是把树的每一个左边分支赋值为0,而把每一个右边分支赋值为1。从树的根开始,找到每一个叶.把沿途经过的左、右分支的值按顺序排列,就可以用1和0的序列来唯一地标识树中的每一个元素了。 对于数据压缩最后要做的是,遍历原始数据的每一个元素,把与每一个数据元素相关的霍夫曼代码写到输出文件。因为起码大多数数据元素的霍夫曼表示比它们本来的表示位数要少,于是达到压缩的目的。为了此后解码的需要,原来的编码信息(霍夫曼树和所生成的数据表)也必须存储在输出文件中。 哈夫曼编码是依据符号出现的概率对符号进行编码,需要对原始数据扫描两遍。第一遍扫描要精确统计原始图像中每个灰度值出现的概率,第二遍是建立哈夫曼二叉树并进行编码,故数据压缩和还原速度较慢,但此法有效简单,且编码效率高,所以在一些图像压缩标准中被普遍采用。 (1)Huffman编码的构造顺序明确,但码不是唯一的。因为在为两个分支赋值时,可以是左支(或上支)为0,也可以是右支(或下支)为0,造成编码的不惟一。此外,当两个符号的概率相等时,谁前谁后也是随机的,构造出来的码字就不是惟一的。 (3)Huffman编码在概率分布很不均匀时能够具有显著的效果,而在信源分布均匀时,一般不使用Huffman编码。 (4)对信源进行Huffman编码后,形成了一个Huffman编码表。解码时,必须参照Huffman编码表才能正确译码。 理论研究表明,Huffman编码是一种接近压缩比上限的编码方法,因此它被广泛用于多种压缩算法之中。 (3)将最下面的两个最小出现概率进行合并相加,得到的结果作为新符号的出现概率。 (5)在合并运算时,概率大的符号用编码0表示,概率小的符号用编码1表示。 (6)记录概率为1处到当前信号源符号之间的0,l序列,从而得到每个符号的编码。 罗述谦,周果宏编著,医学图像处理与分析,科学出版社,2010.12,350-351 侯宏花编著,数字图像处理与分析,北京理工大学出版社,2011.09,第144页 明日科技,宋坤,刘锐宁等编著,Visual C++视频技术方案宝典,人民邮电出版社,2008.2,第381页 |