H264压缩中有个重要的算法，熵编码，熵编码分为两种cavlc（哈夫曼编码也叫变长编码）和cabac（算术编码），这些都是无损压缩编码
要弄懂哈夫曼编码之前先了解一下哈夫曼树
一 概述
给定n个权值作为n个叶子节点，构造一颗二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。
树的带权路径长度(Weighted Path Length of Tree,简记为WPL)
结点的权：在一些应用中,赋予树中结点的一个有某种意义的实数.
结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积.
树的带权路径长度(Weighted Path Length of Tree)：定义为树中所有叶结点的带权路径长度之和
二 哈夫曼树构建方法
- 将整个数据排好序
- 每次取两个最小的数构成两个叶子，计算出根值，存入数据中。
- 删除两个叶子值
- 得到新的数据重复步骤1
三 构建过程
huffman.png
四 哈夫曼编码
得到哈夫曼树之后，哈夫曼编码就容易了
做子树记为0，右子树记为1
所以A,B,C,D的哈夫曼编码分别为
111,10,110,0
五 哈夫曼解码
解码先构建一颗哈夫曼树，一般是编码后的数据对应的表也会存起来，供解码时候查询。
网友评论