哈夫曼編碼證明

1、哈夫曼編碼一、哈夫曼編碼的過(guò)程提到哈夫曼編碼，我們就不得不提起前綴碼，前綴碼的定義為：對(duì)于任意元素集合C 的編碼，C 中任意一個(gè)元素的編碼都不能成為C 中其他元素編碼的前綴。這一點(diǎn)對(duì)于編碼是很容易理解的， 因?yàn)槿绻粷M足定義，我們?cè)谶M(jìn)行解碼的時(shí)候就會(huì)出現(xiàn)歧義，例如下面的例1。編碼： A： 01， B： 010 ，C： 001 ，D： 0010待解碼： 010010解法 1：AD解法 2：BB例 1從例 1 中我們可以看出，如果我們?cè)诰幋a時(shí)不是前綴碼，我們?cè)诮獯a時(shí)就會(huì)得出不同的解碼，這是我們不希望看到的結(jié)果，因此我們?cè)诰幋a的時(shí)候通常是希望能夠進(jìn)行前綴碼編碼。那么如何得到前綴碼呢？我們可以通過(guò)二叉

2、樹實(shí)現(xiàn)，使用二叉樹的葉子結(jié)點(diǎn)來(lái)表示不同元素的編碼，因?yàn)槿我庖粋€(gè)葉子結(jié)點(diǎn)后面不可能再鏈接其他葉子結(jié)點(diǎn)，所以一定能夠滿足前綴碼的定義，即可以使用二叉樹來(lái)表示前綴碼。010011A:00B:01C:10D:11例 2既然我們已經(jīng)發(fā)現(xiàn)使用二叉樹可以用來(lái)進(jìn)行編碼，得到的編碼一定是前綴碼，那么使用二叉樹編碼是唯一的嗎？其實(shí)并不然，我們通過(guò)控制二叉樹的左右延伸，可以得到任意的0、1 編碼，例如我們給出任意一個(gè)前綴碼，我們都可以使用二叉樹表示。我們對(duì)ABCD 重新進(jìn)行編碼， 進(jìn)而我們又能夠得到例三中的二叉樹編碼形式。既然我們通過(guò)二叉樹可以得到任意一種前綴碼，那么他們之間又有什么不同呢？我們通過(guò)比較例2 和例

3、3 試試來(lái)發(fā)現(xiàn)一些不同之處。A編碼長(zhǎng)度B編碼長(zhǎng)度C編碼長(zhǎng)度D編碼長(zhǎng)度例2002012102112例30003001301211表 1我們根據(jù)表1 進(jìn)行比較， 可以發(fā)現(xiàn)， 他們對(duì)于不同元素的編碼是不同的，特別是長(zhǎng)度不同。如果我們從存儲(chǔ)角度來(lái)看，我們當(dāng)然希望相同的ABCDA 元素集合盡量短，這樣可以節(jié)省空間，這是與不同的編碼方式有著很大的關(guān)系的，如果我們給出一個(gè)字符串：ABCD，然后使用例 2 和例 3 中兩種編碼方式， 這會(huì)發(fā)現(xiàn)例 1 ：00011011（共占 8 位），例 2：000001011（共占 9 位），那么就是例 1 更占有優(yōu)勢(shì)，但是我們也一定發(fā)現(xiàn)了，這里 ABCD 都是僅僅出現(xiàn)了一

4、次，所以這是不是也和出現(xiàn)頻率有關(guān)呢？我們?cè)俳o出一個(gè)字符串： ABCDDD ，然后使用例 2 和例 3 中兩種編碼方式， 這會(huì)發(fā)現(xiàn)例 1：000110111111（共占 12 位），例 2：00000101111（共占 11 位），這時(shí)換成例 2 的編碼方式更占有優(yōu)勢(shì)了。這時(shí)我們發(fā)現(xiàn)編碼方式的選擇是和元素出現(xiàn)的頻率有很大關(guān)系的，那么還和其他因素有關(guān)系嗎？我們發(fā)現(xiàn)我們也只能看出不同字符出現(xiàn)的頻率， 所以就只能從頻率下手來(lái)研究編碼方式的選擇了， 而最優(yōu)前綴碼就是哈夫曼編碼。010D:110C:011A:000B:001例 3到了這里我們終于要說(shuō)到哈夫曼編碼的過(guò)程了， 我們先來(lái)了解哈夫曼編碼是如何一步

5、一步進(jìn)行的，然后我們?cè)賮?lái)討論其產(chǎn)生的編碼為什么就能夠時(shí)最優(yōu)的呢？首先我們要先引入幾個(gè)概念：f：頻率d: 元素編碼長(zhǎng)度 (結(jié)點(diǎn)的深度 )?B: 目標(biāo)集合的位數(shù) = f （Xi ） d （Xi）?=1其實(shí)這里 B 就是用來(lái)表示集合全部元素所占的位數(shù)，例如我們以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 反應(yīng)的就是編碼的好壞了，對(duì)于同一個(gè)集合，其 B

6、 越小，其所占的位數(shù)就越小，這是反映編碼好壞的一個(gè)重要標(biāo)志，我們編碼的目標(biāo)也是盡可能的使B 小。那么關(guān)鍵來(lái)了，怎么最小呢？哈夫曼告訴我們這樣一種方式，分為以下幾個(gè)步驟1、 將集合 C 中的所有元素進(jìn)行頻率統(tǒng)計(jì)，得到頻率統(tǒng)計(jì)表2、 將頻率最小的兩個(gè)元素Xi 、 Xj 拿出來(lái)，組成一棵二叉樹的左右孩子，同時(shí)將其雙親結(jié)點(diǎn)的頻率定為：f(Xi )+ f( Xj )。然后將雙親結(jié)點(diǎn)作為新的結(jié)點(diǎn)，加入頻率表中，Xi 、Xj 從頻率表中去除。3、 重復(fù) 2 步驟直到頻率表中只剩下最后一個(gè)。我們下面按照上述的步驟對(duì)ABCDDD 進(jìn)行哈夫曼編碼：1、將集合C 中的所有元素進(jìn)行頻率統(tǒng)計(jì)，得到頻率統(tǒng)計(jì)表ABCDf1

7、1132、 將頻率最小的兩個(gè)元素Xi 、 Xj 拿出來(lái)，組成一棵二叉樹的左右孩子，同時(shí)將其雙親結(jié)點(diǎn)的頻率定為： f(Xi )+ f( Xj )。然后將雙親結(jié)點(diǎn)作為新的結(jié)點(diǎn)，加入頻率表中， Xi 、 Xj 從頻率表中去除。F(A+B) = 2A， f(A)=1B， f(B)=1新的頻率表A+BCDf2133、 重復(fù) 2 步驟直到頻率表中只剩下最后一個(gè)。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，

8、f(B)=1A+B+C+Df6這樣我們就得到了一顆基于集合C ABCDDD 的哈夫曼樹， 其實(shí)就是例3，我們?cè)谏厦嬉舶l(fā)現(xiàn)例 3 的編碼方式確實(shí)比例2 的編碼方式要占優(yōu)勢(shì)，但是我們可能會(huì)有疑問(wèn)，這難道就一定是最優(yōu)的嗎？首先我們要先明確，這樣得到的哈夫曼編碼一定是最優(yōu)編碼的一種，為什么是一種呢， 因?yàn)槲覀冊(cè)谶x取最小頻率是有可能出現(xiàn)想念同頻率的，因此是可能得到不同的哈夫曼樹的，比如ABCCDD,我們?cè)诘玫紽(A+B)=2 時(shí)，我們即可已選擇(A+B) 、C 或 (A+B) 、 D或 C、D，這就可能得到不同的樹 ,如下圖的情形 1、2、3，我們可以分別計(jì)算他們的 B/n（平均每個(gè)元素所占的位數(shù)）值。

9、B/n情形 1(3*1+3*1+2*2+2*1)/ (1+1+2+2) =2情形 2(3*1+3*1+2*2+2*1)/ (1+1+2+2) =2情形 3(2*1+2*1+2*2+2*2)/ (1+1+2+2) =2我們也不難發(fā)現(xiàn)， B/n 值都是相同的，但構(gòu)建的哈夫曼樹并不相同，即編碼不同，所以說(shuō)是最優(yōu)編碼中的一種。既然我們已經(jīng)明確了哈夫曼編碼一定是最優(yōu)編碼的一種， 那么下面我們就需要試著證明其正確性。F(A+B+C+D) = 6F(A+B+C) = 4D， f(D)=2F(A+B) = 2C， f(C)=2A， f(A)=1B， f(B)=1情形 1F(A+B+C+D) = 6F(A+B+

10、D) = 4D， f(C)=2F(A+B) = 2C， f(D)=2A， f(A)=1B， f(B)=1情形 2F(A+B+C+D) = 6F(C+D) = 4F(A+B) = 2A ，f(A)=1B，f(B)=1C， f(C)=2D，f(D)=2情形 3二、哈夫曼編碼正確性的證明哈夫曼編碼確實(shí)形成了一顆二叉樹，我們稱為哈夫曼樹，我們通過(guò)上述例2和例 3兩種編碼方式的比較，也發(fā)現(xiàn)哈夫曼編碼確是有最優(yōu)前綴碼的可能，我們下面就來(lái)證明一下。首先我們先明確兩個(gè)引理：引理 1：對(duì)于集合 C X1、X2 、 .、Xk ，設(shè)其總頻率為n ，假設(shè)其中 f（ X1）、f（ X2 ）最小，則存在一顆最優(yōu)前綴碼的二

11、叉樹，其中X1、 X2 為兄弟結(jié)點(diǎn)。證明：假設(shè)不存在一顆最優(yōu)前綴碼的二叉樹，其中X1、 X2 為兄弟結(jié)點(diǎn)，我們?cè)O(shè)任意一顆最優(yōu)前綴碼的二叉樹為T，則我們通過(guò)交換，將X1、X2 分別與 Xi 、Xj (為深度最大的兄弟節(jié)點(diǎn))?1),其中假設(shè) ij) 進(jìn)行交換，得到新的二叉樹T1。則( ?、 ?的存在性證明詳情見(jiàn)附錄B(T)=f( X3 )*d( X3 )+f( X4 )*d( X4 )+ +f(Xi-1)*d( Xi-1 )+f( Xi+1 )* d( Xi+1)+ +f(Xj-1 )*d(Xj-1 )+ f(Xj+1)* d(Xj+1 )+ +f(Xk )* d(Xk )+ f(?)*d( ?)

12、+f( ?)*d( ?)+ f( ?)*d( ?)+?f( ?)*? d( ?)?B(T1)=f( X3 )* d( X3 )+ f(X4 )*d( X4 )+ +f(Xi-1)* d(Xi-1 )+f( Xi+1 )* d( Xi+1)+ +f( Xj-1 )*d( Xj-1)+ f(Xj+1)* d(Xj+1 )+ +f(Xk )* d(Xk )+ f( ?)*d( ?)+?f( ?)*d( ?)+? f( ?)*?d1( ?)+ f( ?)* d1( ?)所以 B(T)-B(T1)= f(X1 )* d(X1)-f(X1 )* d(Xi )+f(X2)*d(X2 )- f(X2 )* d

13、(Xj )+ f(Xi )* d(Xi )- f(Xi )*d(X1 )+ f(Xj )* d(Xj )- f(Xj )* d(X2 ) =f(X1 )*( d(X1 )- d(Xi )+f( X2 )*(d(X2)- d(Xj )+f( Xi )*( d(Xi )-d(X1)+ f(Xj )*(d(Xj )- d(X2 ) = (f( ?)- f( ?)*( d( ?)- d(?)+(f( ?)- f( ?)*( d( ? )- d( ?)?我們得知 (f(X1)= f( Xi )， (f(X2 )= f( Xj )， d(X1) =d(Xi )， d(X2 ) =0 ，即 B(T)=B(T

14、1), 所以如果等號(hào)成立，則T1 也為最優(yōu)前綴碼的二叉樹，即存在一顆最優(yōu)前綴碼的二叉樹，其中X1、X2為兄弟結(jié)點(diǎn)，則假設(shè)不成立；如果大于號(hào)成立，則 T1 為比 T 更優(yōu)的前綴碼的二叉樹，即 T 不是最優(yōu)前綴碼的二叉樹， 則假設(shè)不成立。綜上所述：一定存在一顆最優(yōu)前綴碼的二叉樹，其中X1 、 X2為兄弟結(jié)點(diǎn)。引理 2：對(duì)于集合 C X1、X2、 .、Xk ，假設(shè)存在一顆最優(yōu)前綴碼的二叉樹，設(shè)為 T，其總頻率為 n ，其中存在一對(duì)兄弟結(jié)點(diǎn)分別為?、 ?，設(shè)其父節(jié)點(diǎn)為 ? 。我們從 T 上去掉?+?Xi 、 Xj ，形成新的二叉樹T1，則 B(T) = B(T1)+f( ?)+ f( ?)。證明：B(

15、T) = f( X1 )* d( X1)+ f( X2 )* d( X2 )+f( X3 )* d( X3)+ f( X4 )* d( X4 )+ +f(Xi-1)* d( Xi-1)+f( Xi+1 )*d(Xi+1 )+ +f(Xj-1)* d(Xj-1)+ f( Xj+1 )* d(Xj+1 )+ +f(Xk )* d(Xk )+ f(?)*? d( ?)+? f( ?)*?d( ?)?B(T1) = f( X1)* d( X1 )+ f( X2 )* d( X2)+f( X3)* d( X3)+ f( X4 )* d( X4)+ +f(Xi-1)* d( Xi-1)+f( Xi+1 )

16、*d(Xi+1)+ +f(X)* d( Xj-1)+ f( X)* d( Xj+1)+ +f(X )* d( X)+ f( ? )*d( ? )j-1j+1kk?+?+?所以 B(T)-B(T1) =f(Xi )*d(Xi )+ f(Xj )* d(Xj )- f(Xi+j)*d( Xi+j ) = (f(Xi )* d(Xi )+ f(Xj )* d(Xj )-(f(Xi )+ (f( Xj )*d( Xi+j )因?yàn)?d(Xi ) = d( Xj ) = d( Xi+j )+1所以 B(T)-B(T1) = f( Xi )* d( Xi )+ f( Xj )* d( Xi )-(f( Xi

17、 )+ (f( Xj )*(d(Xi )-1) = f(Xi )* d( Xi )+ f( Xj )*d(Xi )-f( Xi )*d(Xi )-f( Xj )*d( Xi )+f( Xi )+f( Xj ) = f( Xi )+f( Xj )所以 B(T) = B(T1)+f( Xi )+ f( Xj )，得證。引理現(xiàn)在證明完了， 我們開始對(duì)哈夫曼編碼的正確性進(jìn)行證明。 我們采用第一類歸納法和反證法進(jìn)行證明。1、 當(dāng)集合 C 的規(guī)模為2 時(shí)，使用哈夫曼編碼得到的編碼是最優(yōu)的。證明：當(dāng)集合 CX1 、X2 的規(guī)模為2 時(shí)，使用哈夫曼編碼得到是一棵樹的左右孩子，此時(shí) X1： 0， X2： 1.。

18、我們可以發(fā)現(xiàn)這一定是最優(yōu)的。2、 我們假設(shè)當(dāng)規(guī)模為k(k2) 時(shí)，使用哈夫曼編碼得到的編碼是最優(yōu)的。3、 當(dāng)集合 C X1、X2、 .、 Xk 、 Xk+1 規(guī)模為 k+1 時(shí) ，我們根據(jù)哈夫曼編碼得到二叉樹 T，我們?nèi)∑渲蓄l率最小的兩個(gè)元素，假設(shè)為 X1、X2，此時(shí)我們將 X1、X2去掉，使用他們的父節(jié)點(diǎn)為X1+2 來(lái)進(jìn)行代替， 得到新的集合C1 X1+2 、X3 、 .、Xk 、Xk+1 和新的二叉樹T1(因?yàn)楣蚵幋a是先選中X1、X2后，遞歸進(jìn)行的， 所以 T1 也是哈夫曼編碼得到的)，由 2 中假設(shè)可知，集合C1 根據(jù)哈夫曼編碼得出的一定是最優(yōu)前綴碼的二叉樹T1，即T1 是最優(yōu)前綴碼的二叉樹，我們?cè)賹1 、 X2 添加至 T1 得到T，我們來(lái)證明T 為最優(yōu)前綴碼的二叉樹。證明： 假設(shè)存在比 T 更優(yōu)的前綴碼的二叉樹T2，即 B(T)B(T2) 。因?yàn)?X1、X2為頻率最低的元素， 所以根據(jù)引理 1，此時(shí) X1 、X2 一定為兄弟結(jié)點(diǎn)， 我們將其從 T2 中去掉，并設(shè)其父結(jié)點(diǎn)為 X/ ，得到 T3。1+2根據(jù)引理 2，B(T3)= B(T2) - f( X1)- f( X2)2)時(shí)，使用哈夫曼編碼得到的編碼是最優(yōu)時(shí)，可以推出集合C X1、 X2 、 .、Xk 、Xk+1 規(guī)模為 k+1 時(shí) ，我們根據(jù)哈夫曼編碼得