哈夫曼编码证明

《哈夫曼编码证明》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、哈夫曼编码一、哈夫曼编码的过程提到哈夫曼编码，我们就不得不提起前缀码，前缀码的定义为：对于任意元素集合C的编码，C中任意一个元素的编码都不能成为C中其他元素编码的前缀。这一点对于编码是很容易理解的，因为如果不满足定义，我们在进行解码的时候就会出现歧义，例如下面的例1。编码：A：01，B：010，C：001，D：0010待解码：010010解法1：AD解法2：BB例1从例1中我们可以看出，如果我们在编码时不是前缀码，我们在解码时就会得出不同的解码，这是我们不希望看到的结果，因此我们在编码的时候通常是希望能够进行前缀码编码。那么如何得到前缀码呢？我们可以通过二叉树实现，使用二叉树的叶子

2、结点来表示不同元素的编码，因为任意一个叶子结点后面不可能再链接其他叶子结点，所以一定能够满足前缀码的定义，即可以使用二叉树来表示前缀码。010011A:00B:01C:10D:11例2既然我们已经发现使用二叉树可以用来进行编码，得到的编码一定是前缀码，那么使用二叉树编码是唯一的吗？其实并不然，我们通过控制二叉树的左右延伸，可以得到任意的0、1编码，例如我们给出任意一个前缀码，我们都可以使用二叉树表示。我们对ABCD重新进行编码，进而我们又能够得到例三中的二叉树编码形式。既然我们通过二叉树可以得到任意一种前缀码，那么他们之间又有什么不同呢？我们通过比较例2和例3试试来发现一些不同之处

3、。A编码长度B编码长度C编码长度D编码长度例2002012102112例30003001301211表1我们根据表1进行比较，可以发现，他们对于不同元素的编码是不同的，特别是长度不同。如果我们从存储角度来看，我们当然希望相同的ABCDA…元素集合尽量短，这样可以节省空间，这是与不同的编码方式有着很大的关系的，如果我们给出一个字符串：ABCD，然后使用例2和例3中两种编码方式，这会发现例1：00011011（共占8位），例2：000001011（共占9位），那么就是例1更占有优势，但是我们也一定发现了，这里ABCD都是仅仅出现了一次，所以这是不是也和出现频率有关呢？我们再给出一个字符

4、串：ABCDDD，然后使用例2和例3中两种编码方式，这会发现例1：000110111111（共占12位），例2：00000101111（共占11位），这时换成例2的编码方式更占有优势了。这时我们发现编码方式的选择是和元素出现的频率有很大关系的，那么还和其他因素有关系吗？我们发现我们也只能看出不同字符出现的频率，所以就只能从频率下手来研究编码方式的选择了，而最优前缀码就是哈夫曼编码。010D:110C:011A:000B:001例3到了这里我们终于要说到哈夫曼编码的过程了，我们先来了解哈夫曼编码是如何一步一步进行的，然后我们再来讨论其产生的编码为什么就能够时最优的呢？首先我们要先引入

5、几个概念：f：频率d:元素编码长度(结点的深度)?B:目标集合的位数=∑f（Xi）d（Xi）?=1其实这里B就是用来表示集合全部元素所占的位数，例如我们以ABCDDD为例，我们使用例3中的编码方式，可以得知：f（A）=1，d（A）=3,f（B）=1，d（B）=3,f（C）=1，d（C）=2,f（D）=3，d（D）=1,那么我们按照公式B=1*3+1*3+1*2+3*1=11。B反应的就是编码的好坏了，对于同一个集合，其B越小，其所占的位数就越小，这是反映编码好坏的一个重要标志，我们编码的目标也是尽可能的使B小。那么关键来了，怎么最小呢？哈夫曼告诉我们这样一种方式，分为以下几个步骤1

6、、将集合C中的所有元素进行频率统计，得到频率统计表2、将频率最小的两个元素Xi、Xj拿出来，组成一棵二叉树的左右孩子，同时将其双亲结点的频率定为：f(Xi)+f(Xj)。然后将双亲结点作为新的结点，加入频率表中，Xi、Xj从频率表中去除。3、重复2步骤直到频率表中只剩下最后一个。我们下面按照上述的步骤对ABCDDD进行哈夫曼编码：1、将集合C中的所有元素进行频率统计，得到频率统计表ABCDf11132、将频率最小的两个元素Xi、Xj拿出来，组成一棵二叉树的左右孩子，同时将其双亲结点的频率定为：f(Xi)+f(Xj)。然后将双亲结点作为新的结点，加入频率表中，Xi、Xj从频率表中去除

7、。F(A+B)=2A，f(A)=1B，f(B)=1新的频率表A+BCDf2133、重复2步骤直到频率表中只剩下最后一个。F(A+B+C)=3F(A+B)=2C，f(C)=1A，f(A)=1B，f(B)=1A+B+CDf33F(A+B+C+D)=6F(A+B+C)=3D，f(D)=3F(A+B)=2C，f(C)=1A，f(A)=1B，f(B)=1A+B+C+Df6这样我们就得到了一颗基于集合C{ABCDDD}的哈夫曼树，其实就是例3，我们在上面也发现例3的编码方式确实比