http://www.blueidea.com/bbs/newsdetail.asp?id=1819267&page=2&posts=&Daysprune=5&lp=1

無(wú)損數(shù)據(jù)壓縮是一件奇妙的事情，想一想，一串任意的數(shù)據(jù)能夠根據(jù)一定的規(guī)則轉(zhuǎn)換成只有原來(lái) 1/2 - 1/5 長(zhǎng)度的數(shù)據(jù)，并且能夠按照相應(yīng)的規(guī)則還原到原來(lái)的樣子，聽(tīng)起來(lái)真是很酷。
半年前，苦熬過(guò)初學(xué) vc 時(shí)那段艱難的學(xué)習(xí)曲線(xiàn)的我，對(duì) MFC、SDK 開(kāi)始失望和不滿(mǎn)，這些雖然不算易學(xué)，但和 DHTML 沒(méi)有實(shí)質(zhì)上的區(qū)別，都是調(diào)用微軟提供的各種各樣的函數(shù)，不需要你自己去創(chuàng)建一個(gè)窗口，多線(xiàn)程編程時(shí)，也不需要你自己去分配 CPU 時(shí)間。我也做過(guò)驅(qū)動(dòng)，同樣，有DDK（微軟驅(qū)動(dòng)開(kāi)發(fā)包），當(dāng)然，也有 DDK 的“參考手冊(cè)”，連一個(gè)最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)都不需要你自己做，一切都是函數(shù)、函數(shù)……
微軟的高級(jí)程序員編寫(xiě)了函數(shù)讓我們這些搞應(yīng)用的去調(diào)用，我不想在這里貶低搞應(yīng)用的人，正是這些應(yīng)用工程師連接起了科學(xué)和社會(huì)之間的橋梁，將來(lái)可以做銷(xiāo)售，做管理，用自己逐漸積累起來(lái)的智慧和經(jīng)驗(yàn)在社會(huì)上打拼。
但是，在技術(shù)上來(lái)說(shuō)，誠(chéng)實(shí)地說(shuō)，這并不高深，不是嗎？第一流的公司如微軟、Sybase、Oracle 等總是面向社會(huì)大眾的，這樣才能有巨大的市場(chǎng)。但是他們往往也是站在社會(huì)的最頂層的：操作系統(tǒng)、編譯器、數(shù)據(jù)庫(kù)都值得一代代的專(zhuān)家去不斷研究。這些帝國(guó)般的企業(yè)之所以偉大，恐怕不是“有經(jīng)驗(yàn)”、“能吃苦”這些中國(guó)特色的概念所能涵蓋的，艱深的技術(shù)體系、現(xiàn)代的管理哲學(xué)、強(qiáng)大的市場(chǎng)能力都是缺一不可的吧。我們既然有志于技術(shù)，并且正在起步階段，何必急不可耐地要轉(zhuǎn)去做“管理”，做“青年才俊”，那些所謂的“成功人士”的根底能有幾何，這樣子浮躁，胸中的規(guī)模和格局能有多大？

在我發(fā)現(xiàn)vc只是一個(gè)用途廣泛的編程工具，并不能代表“知識(shí)”、“技術(shù)”的時(shí)候，我有些失落，無(wú)所不能的不是我，而是 MFC、SDK、DDK，是微軟的工程師，他們做的，正是我想做的，或者說(shuō)，我也想成為那種層次的人，現(xiàn)在我知道了，他們是專(zhuān)家，但這不會(huì)是一個(gè)夢(mèng)，有一天我會(huì)做到的，為什么不能說(shuō)出我的想法呢。
那時(shí)公司做的系統(tǒng)里有一個(gè)壓縮模塊，領(lǐng)導(dǎo)找了一個(gè) zlib 庫(kù)，不讓我自己做壓縮算法，站在公司的立場(chǎng)上，我很理解，真的很理解，自己做算法要多久啊。但那時(shí)自己心中隱藏的一份倔強(qiáng)驅(qū)使我去尋找壓縮原理的資料，我完全沒(méi)有意識(shí)到，我即將打開(kāi)一扇大門(mén)，進(jìn)入一個(gè)神奇的“數(shù)據(jù)結(jié)構(gòu)”的世界。“計(jì)算機(jī)藝術(shù)”的第一線(xiàn)陽(yáng)光，居然也照到了我這樣一個(gè)平凡的人的身上。

上面說(shuō)到“計(jì)算機(jī)藝術(shù)”，或者進(jìn)一步細(xì)化說(shuō)“計(jì)算機(jī)編程藝術(shù)”，聽(tīng)起來(lái)很深?yuàn)W，很高雅，但是在將要進(jìn)入專(zhuān)業(yè)的壓縮算法的研究時(shí)，我要請(qǐng)大家做的第一件事情是：忘掉自己的年齡、學(xué)歷，忘掉自己的社會(huì)身份，忘掉編程語(yǔ)言，忘掉“面向?qū)ο蟆薄ⅰ叭龑蛹軜?gòu)”等一切術(shù)語(yǔ)。把自己當(dāng)作一個(gè)小孩，有一雙求知的眼睛，對(duì)世界充滿(mǎn)不倦的、單純的好奇，唯一的前提是一個(gè)正常的具有人類(lèi)理性思維能力的大腦。
下面就讓我們開(kāi)始一段神奇的壓縮算法之旅吧：


1. 原理部分：
　　有兩種形式的重復(fù)存在于計(jì)算機(jī)數(shù)據(jù)中，zip 就是對(duì)這兩種重復(fù)進(jìn)行了壓縮。
　　一種是短語(yǔ)形式的重復(fù)，即三個(gè)字節(jié)以上的重復(fù)，對(duì)于這種重復(fù)，zip用兩個(gè)數(shù)字：1.重復(fù)位置距當(dāng)前壓縮位置的距離；2.重復(fù)的長(zhǎng)度，來(lái)表示這個(gè)重復(fù)，假設(shè)這兩個(gè)數(shù)字各占一個(gè)字節(jié)，于是數(shù)據(jù)便得到了壓縮，這很容易理解。
　　一個(gè)字節(jié)有 0 - 255 共 256 種可能的取值，三個(gè)字節(jié)有 256 * 256 * 256 共一千六百多萬(wàn)種可能的情況，更長(zhǎng)的短語(yǔ)取值的可能情況以指數(shù)方式增長(zhǎng)，出現(xiàn)重復(fù)的概率似乎極低，實(shí)則不然，各種類(lèi)型的數(shù)據(jù)都有出現(xiàn)重復(fù)的傾向，一篇論文中，為數(shù)不多的術(shù)語(yǔ)傾向于重復(fù)出現(xiàn)；一篇小說(shuō)，人名和地名會(huì)重復(fù)出現(xiàn)；一張上下漸變的背景圖片，水平方向上的像素會(huì)重復(fù)出現(xiàn)；程序的源文件中，語(yǔ)法關(guān)鍵字會(huì)重復(fù)出現(xiàn)（我們寫(xiě)程序時(shí)，多少次前后copy、paste？），以幾十 K 為單位的非壓縮格式的數(shù)據(jù)中，傾向于大量出現(xiàn)短語(yǔ)式的重復(fù)。經(jīng)過(guò)上面提到的方式進(jìn)行壓縮后，短語(yǔ)式重復(fù)的傾向被完全破壞，所以在壓縮的結(jié)果上進(jìn)行第二次短語(yǔ)式壓縮一般是沒(méi)有效果的。
　　第二種重復(fù)為單字節(jié)的重復(fù)，一個(gè)字節(jié)只有256種可能的取值，所以這種重復(fù)是必然的。其中，某些字節(jié)出現(xiàn)次數(shù)可能較多，另一些則較少，在統(tǒng)計(jì)上有分布不均勻的傾向，這是容易理解的，比如一個(gè) ASCII 文本文件中，某些符號(hào)可能很少用到，而字母和數(shù)字則使用較多，各字母的使用頻率也是不一樣的，據(jù)說(shuō)字母 e 的使用概率最高；許多圖片呈現(xiàn)深色調(diào)或淺色調(diào)，深色（或淺色）的像素使用較多（這里順便提一下：png 圖片格式是一種無(wú)損壓縮，其核心算法就是 zip 算法，它和 zip 格式的文件的主要區(qū)別在于：作為一種圖片格式，它在文件頭處存放了圖片的大小、使用的顏色數(shù)等信息）；上面提到的短語(yǔ)式壓縮的結(jié)果也有這種傾向：重復(fù)傾向于出現(xiàn)在離當(dāng)前壓縮位置較近的地方，重復(fù)長(zhǎng)度傾向于比較短（20字節(jié)以?xún)?nèi)）。這樣，就有了壓縮的可能：給 256 種字節(jié)取值重新編碼，使出現(xiàn)較多的字節(jié)使用較短的編碼，出現(xiàn)較少的字節(jié)使用較長(zhǎng)的編碼，這樣一來(lái)，變短的字節(jié)相對(duì)于變長(zhǎng)的字節(jié)更多，文件的總長(zhǎng)度就會(huì)減少，并且，字節(jié)使用比例越不均勻，壓縮比例就越大。
　　在進(jìn)一步討論編碼的要求以及辦法前，先提一下：編碼式壓縮必須在短語(yǔ)式壓縮之后進(jìn)行，因?yàn)榫幋a式壓縮后，原先八位二進(jìn)制值的字節(jié)就被破壞了，這樣文件中短語(yǔ)式重復(fù)的傾向也會(huì)被破壞（除非先進(jìn)行解碼）。另外，短語(yǔ)式壓縮后的結(jié)果：那些剩下的未被匹配的單、雙字節(jié)和得到匹配的距離、長(zhǎng)度值仍然具有取值分布不均勻性，因此，兩種壓縮方式的順序不能變。
　　在編碼式壓縮后，以連續(xù)的八位作為一個(gè)字節(jié)，原先未壓縮文件中所具有的字節(jié)取值不均勻的傾向被徹底破壞，成為隨機(jī)性取值，根據(jù)統(tǒng)計(jì)學(xué)知識(shí)，隨機(jī)性取值具有均勻性的傾向（比如拋硬幣試驗(yàn)，拋一千次，正反面朝上的次數(shù)都接近于 500 次）。因此，編碼式壓縮后的結(jié)果無(wú)法再進(jìn)行編碼式壓縮。
　　短語(yǔ)式壓縮和編碼式壓縮是目前計(jì)算機(jī)科學(xué)界研究出的僅有的兩種無(wú)損壓縮方法，它們都無(wú)法重復(fù)進(jìn)行，所以，壓縮文件無(wú)法再次壓縮（實(shí)際上，能反復(fù)進(jìn)行的壓縮算法是不可想象的，因?yàn)樽罱K會(huì)壓縮到 0 字節(jié)）。
　　短語(yǔ)式重復(fù)的傾向和字節(jié)取值分布不均勻的傾向是可以壓縮的基礎(chǔ)，兩種壓縮的順序不能互換的原因也說(shuō)了，下面我們來(lái)看編碼式壓縮的要求及方法：

壓縮文件無(wú)法再次壓縮是因?yàn)?#xff1a;
1. 短語(yǔ)式壓縮去掉了三個(gè)字節(jié)以上的重復(fù)，壓縮后的結(jié)果中包含的是未匹配的單雙字節(jié)，和匹配距離、長(zhǎng)度的組合。這個(gè)結(jié)果當(dāng)然仍然可能包含三個(gè)字節(jié)以上的重復(fù)，但是概率極低。因?yàn)槿齻€(gè)字節(jié)有 256 * 256 * 256 共一千六百多萬(wàn)種可能的情況。
所以只要把原始文件中“自然存在”的短語(yǔ)式重復(fù)傾向壓掉就可以了，一千六百萬(wàn)分之一的概率再去壓縮沒(méi)有必要。
2.編碼式壓縮利用各個(gè)單字節(jié)使用頻率不一樣的傾向，使定長(zhǎng)編碼變?yōu)椴欢ㄩL(zhǎng)編碼，給使用頻率高的字節(jié)更短的編碼，使用頻率低的字節(jié)更長(zhǎng)的編碼，起到壓縮的效果。如果把編碼式壓縮的“結(jié)果”按照8位作為1字節(jié)，重新統(tǒng)計(jì)各字節(jié)的使用頻率，應(yīng)該是大致相等的。因?yàn)樾碌淖止?jié)使用頻率是隨機(jī)的。相等的頻率再去變換字節(jié)長(zhǎng)短是沒(méi)有意義的，因?yàn)樽兌痰淖止?jié)沒(méi)有比變長(zhǎng)的字節(jié)更多。
所以壓掉了原始文件中“自然存在”的單字節(jié)使用頻率不均勻的傾向后，隨機(jī)的使用頻率再去壓縮也失去了意義。

首先，為了使用不定長(zhǎng)的編碼表示單個(gè)字符，編碼必須符合“前綴編碼”的要求，即較短的編碼決不能是較長(zhǎng)編碼的前綴，反過(guò)來(lái)說(shuō)就是，任何一個(gè)字符的編碼，都不是由另一個(gè)字符的編碼加上若干位 0 或 1 組成，否則解壓縮程序?qū)o(wú)法解碼。
看一下前綴編碼的一個(gè)最簡(jiǎn)單的例子：


符號(hào) 編碼
A 0
B 10
C 110
D 1110
E 11110

有了上面的碼表，你一定可以輕松地從下面這串二進(jìn)制流中分辨出真正的信息內(nèi)容了：

1110010101110110111100010 - DABBDCEAAB

要構(gòu)造符合這一要求的二進(jìn)制編碼體系，二叉樹(shù)是最理想的選擇。考察下面這棵二叉樹(shù)：

　　　　　　　　根(root)
　　　　　　 0　　|　　 1
　　　　 　 +-------+--------+
　　　　0　 |　1　　 0 　|　 1
　 　 +-----+------+　+----+----+
　 　 |　　　　　|　|　 　　 |
　 　 a　　 　　 |　d 　　　 e
　　　　　0　　|　　1
　　　　　+-----+-----+
　　　　　|　　　　 |
　　　　　b　　 　　c

要編碼的字符總是出現(xiàn)在樹(shù)葉上，假定從根向樹(shù)葉行走的過(guò)程中，左轉(zhuǎn)為0，右轉(zhuǎn)為1，則一個(gè)字符的編碼就是從根走到該字符所在樹(shù)葉的路徑。正因?yàn)樽址荒艹霈F(xiàn)在樹(shù)葉上，任何一個(gè)字符的路徑都不會(huì)是另一字符路徑的前綴路徑，符合要求的前綴編碼也就構(gòu)造成功了：

a - 00 b - 010 c - 011 d - 10 e - 11


接下來(lái)來(lái)看編碼式壓縮的過(guò)程：
為了簡(jiǎn)化問(wèn)題，假定一個(gè)文件中只出現(xiàn)了 a，b，c，d ，e四種字符，它們的出現(xiàn)次數(shù)分別是
a : 6次
b : 15次
c : 2次
d : 9次
e : 1次
如果用定長(zhǎng)的編碼方式為這四種字符編碼： a : 000 b : 001 c : 010 d : 011 e : 100
那么整個(gè)文件的長(zhǎng)度是 3*6 + 3*15 + 3*2 + 3*9 + 3*1 = 99

用二叉樹(shù)表示這四種編碼(其中葉子節(jié)點(diǎn)上的數(shù)字是其使用次數(shù)，非葉子節(jié)點(diǎn)上的數(shù)字是其左右孩子使用次數(shù)之和):

　　　　　　　　 　根
　　　　　　　　 　 |
　　　　　　+---------33---------+
　　　　　　|　　　　　　 　|
　　 +----32---+　　　　 +----1---+
　　 |　　　　|　 　　　|　　　 |
+-21-+ 　 +-11-+ 　 　+--1--+　　
|　　 | 　 |　　 | 　 　|　　 |
6　 15 　2　　9 　 　1　　　

（如果某個(gè)節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，可以去掉這個(gè)子節(jié)點(diǎn)。）

　　　　　　　　 根
　　　　　　　　　|
　 　 　　　 +------33------+
　　　　　　 |　　　　　|
　 　 +-----32----+ 　 　 1
　 　 |　　　 　 |
　 +--21--+ 　+--11--+
　 |　　　|　 |　　　|
　 6 　　15　2　 　 9

現(xiàn)在的編碼是： a : 000 b : 001 c : 010 d : 011 e : 1 仍然符合“前綴編碼”的要求。

第一步：如果發(fā)現(xiàn)下層節(jié)點(diǎn)的數(shù)字大于上層節(jié)點(diǎn)的數(shù)字，就交換它們的位置，并重新計(jì)算非葉子節(jié)點(diǎn)的值。
先交換11和1，由于11個(gè)字節(jié)縮短了一位，1個(gè)字節(jié)增長(zhǎng)了一位，總文件縮短了10位。

　　　　　　　　　　 根
　 　 　　　　　　　　|
　　　　　　 +----------33---------+
　　　　　　 |　　　　　　　　|
　　 +-----22----+　　　　　+----11----+
　　 | 　　 　　|　　　　　|　　　　 |
+--21--+　　　 1　 　 　　2　　　　 9
| 　 　 |
6　　 15

再交換15和1、6和2，最終得到這樣的樹(shù)：

　　　　　　　　　　 根
　　　　　 　　　　 　|
　　　　　　 +----------33---------+
　　　　　　 |　　　　　　　　|
　　 　 +-----18----+　　　 +----15----+
　　　 | 　　 　　|　　　 |　　　　 |
　　+--3--+ 　 　15　　　6　　　　 9
　　|　 　|
　　2　　 1

這時(shí)所有上層節(jié)點(diǎn)的數(shù)值都大于下層節(jié)點(diǎn)的數(shù)值，似乎無(wú)法再進(jìn)一步壓縮了。但是我們把每一層的最小的兩個(gè)節(jié)點(diǎn)結(jié)合起來(lái)，常會(huì)發(fā)現(xiàn)仍有壓縮余地。

第二步：把每一層的最小的兩個(gè)節(jié)點(diǎn)結(jié)合起來(lái)，重新計(jì)算相關(guān)節(jié)點(diǎn)的值。

在上面的樹(shù)中，第一、二、四三層都只有一或二個(gè)節(jié)點(diǎn)，無(wú)法重新組合，但第三層上有四個(gè)節(jié)點(diǎn)，我們把最小的3和6結(jié)合起來(lái)，并重新計(jì)算相關(guān)節(jié)點(diǎn)的值，成為下面這棵樹(shù)。

　　　　　　　　　　 根
　　　　　 　　　　 　|
　　　　　　 +----------33---------+
　　　　　　 | 　　　　　　　 |
　　　 +------9-----+　　　 +----24----+
　　　 |　 　　 　|　　　 |　　　　 |
　　 +--3--+　 　 6　　　15　　　　9
　　 |　　 |
　　2　　1

然后，再重復(fù)做第一步。
這時(shí)第二層的9小于第三層的15，于是可以互換，有9個(gè)字節(jié)增長(zhǎng)了一位，15個(gè)字節(jié)縮短了一位，文件總長(zhǎng)度又縮短了6位。然后重新計(jì)算相關(guān)節(jié)點(diǎn)的值。

　　　　　　　　　　 根
　　　　 　　　　　　 |
　　　　　　 +----------33---------+
　　　　　　 |　　　　　　　　|
　　　　　　 15　　　　 +----18----+　
　　　　　　　　　　　　|　　　　|
　　　　　　　　　+------9-----+　　 9
　　　　　　　　　|　 　　　 |
　 　　　　　 　+--3--+　　　6
　　 　　　　 　|　　 |
　　　　 　　　 2　　1

這時(shí)發(fā)現(xiàn)所有的上層節(jié)點(diǎn)都大于下層節(jié)點(diǎn)，每一層上最小的兩個(gè)節(jié)點(diǎn)被并在了一起，也不可能再產(chǎn)生比同層其他節(jié)點(diǎn)更小的父節(jié)點(diǎn)了。

這時(shí)整個(gè)文件的長(zhǎng)度是 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63

這時(shí)可以看出編碼式壓縮的一個(gè)基本前提：各節(jié)點(diǎn)之間的值要相差比較懸殊，以使某兩個(gè)節(jié)點(diǎn)的和小于同層或下層的另一個(gè)節(jié)點(diǎn)，這樣，交換節(jié)點(diǎn)才有利益。
所以歸根結(jié)底，原始文件中的字節(jié)使用頻率必須相差較大，否則將沒(méi)有兩個(gè)節(jié)點(diǎn)的頻率之和小于同層或下層其他節(jié)點(diǎn)的頻率，也就無(wú)法壓縮。反之，相差得越懸殊，兩個(gè)節(jié)點(diǎn)的頻率之和比同層或下層節(jié)點(diǎn)的頻率小得越多，交換節(jié)點(diǎn)之后的利益也越大。

在這個(gè)例子中，經(jīng)過(guò)上面兩步不斷重復(fù)，得到了最優(yōu)的二叉樹(shù)，但不能保證在所有情況下，都能通過(guò)這兩步的重復(fù)得到最優(yōu)二叉樹(shù)，下面來(lái)看另一個(gè)例子：

　　　　　　　　　　　　　　　　　　　　　　　　　根
　　　　　　　　　　　　　　　　　　　　　　　　　｜
　　　　　　　　　　　　　　＋－－－－－－－－－１９－－－－－－－－＋
　　　　　　　　　　　　　　｜　　　　　　　　　　　　　　　　　　　｜
　　　　　　＋－－－－－－１２－－－－－－＋　　　　　　　　　　　　７
　　　　　　｜　　　　　　　　　　　　　　｜
　　＋－－－５－－－＋　　　　　　＋－－－７－－－＋
　　｜　　　　　　　｜　　　　　　｜　　　　　　　｜
＋－２－＋　　　＋－３－＋　　＋－３－＋　　　＋－４－＋
｜　　　｜　　　｜　　　｜　　｜　　　｜　　　｜　　　｜
１　　　１　　　１　　　２　　１　　　２　　　２　　　２

這個(gè)例子中，所有上層節(jié)點(diǎn)都大于等于下層節(jié)點(diǎn)，每一層最小的兩個(gè)節(jié)點(diǎn)結(jié)合在了一起，但仍然可以進(jìn)一步優(yōu)化：


　　　　　　　　　　　　　　　　　　　　　　　　　根
　　　　　　　　　　　　　　　　　　　　　　　　　｜
　　　　　　　　　　　　　　＋－－－－－－－－－１９－－－－－－－－＋
　　　　　　　　　　　　　　｜　　　　　　　　　　　　　　　　　　　｜
　　　　　　＋－－－－－－１２－－－－－－＋　　　　　　　　　　　　７
　　　　　　｜　　　　　　　　　　　　　　｜
　　＋－－－４－－－＋　　　　　　＋－－－８－－－＋
　　｜　　　　　　　｜　　　　　　｜　　　　　　　｜
＋－２－＋　　　＋－２－＋　　＋－４－＋　　　＋－４－＋
｜　　　｜　　　｜　　　｜　　｜　　　｜　　　｜　　　｜
１　　　１　　　１　　　１　　２　　　２　　　２　　　２

通過(guò)最低一層的第４第５個(gè)節(jié)點(diǎn)對(duì)換，第３層的８大于第２層的７。
到這里，我們得出這樣一個(gè)結(jié)論：一棵最優(yōu)二叉編碼樹(shù)（所有上層節(jié)點(diǎn)都無(wú)法和下層節(jié)點(diǎn)交換），必須符合這樣兩個(gè)條件：
１．所有上層節(jié)點(diǎn)都大于等于下層節(jié)點(diǎn)。
２．某節(jié)點(diǎn)，設(shè)其較大的子節(jié)點(diǎn)為ｍ，較小的子節(jié)點(diǎn)為ｎ，ｍ下的任一層的所有節(jié)點(diǎn)都應(yīng)大于等于ｎ下的該層的所有節(jié)點(diǎn)。

當(dāng)符合這兩個(gè)條件時(shí)，任一層都無(wú)法產(chǎn)生更小的節(jié)點(diǎn)去和下層節(jié)點(diǎn)交換，也無(wú)法產(chǎn)生更大的節(jié)點(diǎn)去和上層節(jié)點(diǎn)交換。

上面的兩個(gè)例子是比較簡(jiǎn)單的，實(shí)際的文件中，一個(gè)字節(jié)有256種可能的取值，所以二叉樹(shù)的葉子節(jié)點(diǎn)多達(dá)256個(gè)，需要不斷的調(diào)整樹(shù)形，最終的樹(shù)形可能非常復(fù)雜，有一種非常精巧的算法可以快速地建起一棵最優(yōu)二叉樹(shù)，這種算法由D.Huffman（戴·霍夫曼）提出，下面我們先來(lái)介紹霍夫曼算法的步驟，然后再來(lái)證明通過(guò)這么簡(jiǎn)單的步驟得出的樹(shù)形確實(shí)是一棵最優(yōu)二叉樹(shù)。


霍夫曼算法的步驟是這樣的：

·從各個(gè)節(jié)點(diǎn)中找出最小的兩個(gè)節(jié)點(diǎn)，給它們建一個(gè)父節(jié)點(diǎn)，值為這兩個(gè)節(jié)點(diǎn)之和。
·然后從節(jié)點(diǎn)序列中去除這兩個(gè)節(jié)點(diǎn)，加入它們的父節(jié)點(diǎn)到序列中。

重復(fù)上面兩個(gè)步驟，直到節(jié)點(diǎn)序列中只剩下唯一一個(gè)節(jié)點(diǎn)。這時(shí)一棵最優(yōu)二叉樹(shù)就已經(jīng)建成了，它的根就是剩下的這個(gè)節(jié)點(diǎn)。

仍以上面的例子來(lái)看霍夫曼樹(shù)的建立過(guò)程。
最初的節(jié)點(diǎn)序列是這樣的：
a(6) 　b(15) 　c(2) 　d(9) 　e(1)

把最小的c和e結(jié)合起來(lái)
　　　　　　　　　　　　 　　 　 　| (3)
a(6) 　　b(15) 　　d(9)　　　+------+------+
　　　　　　　　　　　　　　|　　 　　　|
　　　　　　　　　　　　　　c　　　　　e

不斷重復(fù)，最終得到的樹(shù)是這樣的：

　　 　　　 根
　 　 　　　 |
　 　+-----33-----+
　　　|　　　　　|
　　　15　　 +----18----+　　　
　　　　　　 | 　 　 　 |
　　　　　　 9　 +------9-----+
　 　　 　　　　　|　　 　 　 |
　　　　　　　　 6 　　 　+--3--+
　　 　　　　　　　　　 　|　　 |
　　　　 　　　 　　　　　2　　1

這時(shí)各個(gè)字符的編碼長(zhǎng)度和前面我們說(shuō)過(guò)的方法得到的編碼長(zhǎng)度是相同的，因而文件的總長(zhǎng)度也是相同的： 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63

考察霍夫曼樹(shù)的建立過(guò)程中的每一步的節(jié)點(diǎn)序列的變化：

6 　15　2　9　1
6　 15　9　3
15　9　 9
15　18
33

下面我們用逆推法來(lái)證明對(duì)于各種不同的節(jié)點(diǎn)序列，用霍夫曼算法建立起來(lái)的樹(shù)總是一棵最優(yōu)二叉樹(shù)：

對(duì)霍夫曼樹(shù)的建立過(guò)程運(yùn)用逆推法：
當(dāng)這個(gè)過(guò)程中的節(jié)點(diǎn)序列只有兩個(gè)節(jié)點(diǎn)時(shí)（比如前例中的15和18），肯定是一棵最優(yōu)二叉樹(shù)，一個(gè)編碼為0，另一個(gè)編碼為1，無(wú)法再進(jìn)一步優(yōu)化。
然后往前步進(jìn)，節(jié)點(diǎn)序列中不斷地減少一個(gè)節(jié)點(diǎn)，增加兩個(gè)節(jié)點(diǎn)，在步進(jìn)過(guò)程中將始終保持是一棵最優(yōu)二叉樹(shù)，這是因?yàn)?#xff1a;
1.按照霍夫曼樹(shù)的建立過(guò)程，新增的兩個(gè)節(jié)點(diǎn)是當(dāng)前節(jié)點(diǎn)序列中最小的兩個(gè)，其他的任何兩個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)都大于（或等于）這兩個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，只要前一步是最優(yōu)二叉樹(shù)，其他的任何兩個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)就一定都處在它們的父節(jié)點(diǎn)的上層或同層，所以這兩個(gè)節(jié)點(diǎn)一定處在當(dāng)前二叉樹(shù)的最低一層。
2.這兩個(gè)新增的節(jié)點(diǎn)是最小的，所以無(wú)法和其他上層節(jié)點(diǎn)對(duì)換。符合我們前面說(shuō)的最優(yōu)二叉樹(shù)的第一個(gè)條件。
3.只要前一步是最優(yōu)二叉樹(shù)，由于這兩個(gè)新增的節(jié)點(diǎn)是最小的，即使同層有其他節(jié)點(diǎn)，也無(wú)法和同層其他節(jié)點(diǎn)重新結(jié)合，產(chǎn)生比它們的父節(jié)點(diǎn)更小的上層節(jié)點(diǎn)來(lái)和同層的其他節(jié)點(diǎn)對(duì)換。它們的父節(jié)點(diǎn)小于其他節(jié)點(diǎn)的父節(jié)點(diǎn)，它們又小于其他所有節(jié)點(diǎn)，只要前一步符合最優(yōu)二叉樹(shù)的第二個(gè)條件，到這一步仍將符合。

這樣一步步逆推下去，在這個(gè)過(guò)程中霍夫曼樹(shù)每一步都始終保持著是一棵最優(yōu)二叉樹(shù)。

由于每一步都從節(jié)點(diǎn)序列中刪除兩個(gè)節(jié)點(diǎn)，新增一個(gè)節(jié)點(diǎn)，霍夫曼樹(shù)的建立過(guò)程共需 (原始節(jié)點(diǎn)數(shù) - 1) 步，所以霍夫曼算法不失為一種精巧的編碼式壓縮算法。


附：對(duì)于 huffman 樹(shù)，《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》中有完全不同的證明，大意是這樣的：
１．二叉編碼樹(shù)的內(nèi)部節(jié)點(diǎn)（非葉子節(jié)點(diǎn)）數(shù)等于外部節(jié)點(diǎn)（葉子節(jié)點(diǎn)）數(shù)減１。
２．二叉編碼樹(shù)的外部節(jié)點(diǎn)的加權(quán)路徑長(zhǎng)度（值乘以路徑長(zhǎng)度）之和，等于所有內(nèi)部節(jié)點(diǎn)值之和。（這兩條都可以通過(guò)對(duì)節(jié)點(diǎn)數(shù)運(yùn)用數(shù)學(xué)歸納法來(lái)證明，留給大家做練習(xí)。）
３．對(duì) huffman 樹(shù)的建立過(guò)程運(yùn)用逆推，當(dāng)只有一個(gè)內(nèi)部節(jié)點(diǎn)時(shí)，肯定是一棵最優(yōu)二叉樹(shù)。
４．往前步進(jìn)，新增兩個(gè)最小的外部節(jié)點(diǎn)，它們結(jié)合在一起產(chǎn)生一個(gè)新的內(nèi)部節(jié)點(diǎn)，當(dāng)且僅當(dāng)原先的內(nèi)部節(jié)點(diǎn)集合是極小化的，加入這個(gè)新的內(nèi)部節(jié)點(diǎn)后仍是極小化的。（因?yàn)樽钚〉膬蓚€(gè)節(jié)點(diǎn)結(jié)合在一起，并處于最低層，相對(duì)于它們分別和其他同層或上層節(jié)點(diǎn)結(jié)合在一起，至少不會(huì)增加加權(quán)路徑長(zhǎng)度。）
５．隨著內(nèi)部節(jié)點(diǎn)數(shù)逐個(gè)增加，內(nèi)部節(jié)點(diǎn)集合總維持極小化。




２．實(shí)現(xiàn)部分
　　如果世界上從沒(méi)有一個(gè)壓縮程序，我們看了前面的壓縮原理，將有信心一定能作出一個(gè)可以壓縮大多數(shù)格式、內(nèi)容的數(shù)據(jù)的程序，當(dāng)我們著手要做這樣一個(gè)程序的時(shí)候，會(huì)發(fā)現(xiàn)有很多的難題需要我們?nèi)ヒ粋€(gè)個(gè)解決，下面將逐個(gè)描述這些難題，并詳細(xì)分析 zip 算法是如何解決這些難題的，其中很多問(wèn)題帶有普遍意義，比如查找匹配，比如數(shù)組排序等等，這些都是說(shuō)不盡的話(huà)題，讓我們深入其中，做一番思考。

待續(xù)。。。。

總結(jié)

以上是生活随笔為你收集整理的zip 的压缩原理与实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。