算法設(shè)計與分析 課件 6.5.2-貪心法應(yīng)用-哈夫曼編碼-算法正確性證明

信息工程大學(xué)算法設(shè)計與分析貪心法--哈夫曼算法的正確性證明國家級實(shí)驗教學(xué)示范中心計算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版定理：Huffman算法對任意規(guī)模為n（n2）的字符集C都能得到關(guān)于C的最優(yōu)前綴碼的二叉樹。

該定理的證明需要兩個引理。則T與T’的WPL之差為其中dT(i)為i在T中的層數(shù)（i到根的距離）,引理1成立。引理1：設(shè)C是字符集，

c

C,f(c)為頻率，x,y

C,f(x),f(y)頻率最小，那么存在最優(yōu)二元前綴碼使得x,y的編碼長度相等，且僅在最后一位不同。f(x)

f(a)f(y)

f(b)a與x交換b與y交換

TT’yabxTbxyaT’證明:設(shè)T是C的最優(yōu)前綴樹，且a和b是具有最大深度的兩個兄弟字符:引理2：設(shè)T是最優(yōu)二元前綴碼所對應(yīng)的二叉樹，

x,y

T,x,y是樹葉兄弟，z是x,y的父親，令T’=T

{x,y},且令z的頻率f(z)=f(x)+f(y)，T’是對應(yīng)于二元前綴碼C’=(C

{x,y})

{z}的二叉樹，那么WPL(T)=WPL

(T’)+f(x)+f(y)。bczT’0011f(c)f(b)f(x)+f(y)bcxyT000111f(x)f(c)f(y)f(b)z定理：Huffman算法對任意規(guī)模為n（n2）的字符集C都能得到關(guān)于C的最優(yōu)前綴碼的二叉樹。

歸納基礎(chǔ)

n=2，字符集C={x1,x2}，Huffman算法得到的編碼是0和1，是最優(yōu)前綴碼。歸納步驟

假設(shè)Huffman算法對于規(guī)模為k的字符集能得到最優(yōu)前綴碼。考慮規(guī)模為k+1的字符集C={x1,x2,...,xk+1},其中x1,x2

C是頻率最小的兩個字符。

令

C’=(C－{x1,x2})

{z}，

f(z)=f(x1)+f(x2)根據(jù)歸納假設(shè)，Huffman算法得到一棵關(guān)于字符集C’、頻率f(z)和f(xi)（i=3,4,...,k+1）的最優(yōu)前綴碼的二叉樹T’。把x1和x2作為z的兒子附加到T’上，得到樹T，那么T是關(guān)于字符集C=(C’－{z})

{x1,x2}的最優(yōu)前綴碼的二叉樹。

zT’x2x1T

zx1T*x2T*‘

z如若不然，存在更優(yōu)的樹T*。根據(jù)引理1，其最深層樹葉是x1,

x2，且WPL(T*)<WPL(T)。去掉T*中的x1和x2，根據(jù)引理2，所得二叉樹T*’滿足WPL(T*’)＝WPL(T*)－(f(x1)+f(x2))<WPL(T)－