哈夫曼编码

x33g5p2x  于2022-04-21 转载在 其他  
字(0.5k)|赞(0)|评价(0)|浏览(515)

概念

哈夫曼编码是一种字符编码方式,是可变长编码的一种,1952年提出,依据字符在文件中出现的频率来建立一个用0,1串表示各字符,使平均每个字符的码长最短的最优表现形式。

应用于图像压缩和大容量存储

为了正确解码,可变长编码必须满足,二元前缀码的性质任何字符的代码都不能作为其他字符代码的前缀
非前缀码的例子
a:001, b:00,c:010,d:01

解码的歧义,例如字符串0100001
解码1:01,00,001 d, b, a
解码2:010,00,01 c,b,d

前缀码的二叉树及权值

哈夫曼编码的设计思想

  • 以字符的使用频率做权构建一棵哈夫曼树,然后利用哈夫曼树对字符进行编码,称为哈夫曼编码
  • 具体是将所要编码的字符作为叶子节点,该字符在文件中的使用频率作为叶子节点的的权值,以自底向上的方式、通过执行n-1次的“合并”运算后构造出最终所要求的树,即哈夫曼树,它的核心思想是让权值大的叶子离根最近
  • 采用的贪心策略:每次从树的集合中取出双亲为0且权值最小的两棵树作为左、右子树,构造一棵新树,新树根节点的权值为其左右孩子节点权值之和,将新树插入到树的集合中

实例

对下图 a、b、c、d、e、f 六个字符进行哈夫曼编码

第一次:

下一步:

下一步:

下一步:

下一步:

一共2n-1个节点,合并了n-1次

最终结果:

伪代码

相关文章

微信公众号

最新文章

更多