摘要: 霍夫曼編碼是一種被廣泛應(yīng)用而且非常有效的數(shù)據(jù)壓縮技術(shù)，根據(jù)待壓縮數(shù)據(jù)的特征，一個(gè)可壓縮掉20%~90%。這里考慮的數(shù)據(jù)指的是字符串序列。要理解霍夫曼編碼，先要理解霍夫曼樹(shù)，即最優(yōu)二叉樹(shù)，是一類帶權(quán)路徑長(zhǎng)度最短的樹(shù)。
路徑是指從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的通路，路徑上的分支數(shù)目稱為路徑長(zhǎng)度。
樹(shù)的路徑長(zhǎng)度是從樹(shù)根到每一個(gè)葉子之間的路徑長(zhǎng)度之和。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為從該結(jié)點(diǎn)到樹(shù)根之間的路徑長(zhǎng)度與該結(jié)點(diǎn)權(quán)的乘積，樹(shù)的帶權(quán)路徑長(zhǎng)度為樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和.
霍夫曼樹(shù)是指所有葉子結(jié)點(diǎn)的二叉樹(shù)中帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù).
當(dāng)給定了n個(gè)葉子結(jié)點(diǎn)的權(quán)值后，構(gòu)造出的最優(yōu)二叉樹(shù)的結(jié)點(diǎn)數(shù)目m就確定了，即m=2n-1,所以可用一維結(jié)構(gòu)樹(shù)組來(lái)存儲(chǔ)最優(yōu)二叉樹(shù)
閱讀全文