2哈夫曼編碼介紹

　　哈夫曼編碼是20世紀(jì)50年代由哈夫曼教授研制開發(fā)的，它借助了數(shù)據(jù)結(jié)構(gòu)當(dāng)中的樹型結(jié)構(gòu)，在哈夫曼算法的支持下構(gòu)造出一棵最優(yōu)二叉樹，把這類樹命名為哈夫曼樹。因此，準(zhǔn)確地說，哈夫曼編碼是在哈夫曼樹的基礎(chǔ)之上構(gòu)造出來的一種編碼形式，它的本身有著非常廣泛的應(yīng)用。

　　2.1基本原理

　　數(shù)據(jù)能夠被壓縮的理論依據(jù)如下：

　　定義1對(duì)于給定的信源和碼符號(hào)集，若有一個(gè)惟一可譯碼，其平均碼長(zhǎng)L小于所有其他惟一可譯碼，則稱這種碼為緊致碼或最佳碼。

　　定理1哈夫曼編碼是緊致碼。

　　計(jì)算機(jī)文件是以字節(jié)為單位組成的，每個(gè)字節(jié)的取值為O～255.每個(gè)字節(jié)都看成字符，共256種字符。因此，每個(gè)字節(jié)都是以8個(gè)二進(jìn)制位的定長(zhǎng)編碼表示的。由于這種定長(zhǎng)碼也是惟一可譯碼，根據(jù)定理1有L≤8.

　　設(shè)某個(gè)文件有N個(gè)字節(jié)組成，則該文件總長(zhǎng)度為8N比特。如果對(duì)該文件進(jìn)行哈夫曼編碼，則該文件總長(zhǎng)度為L(zhǎng)N比特。由于L≤8，所以LN≤8。所以，只要文件滿足L<8，用哈夫曼編碼總可以對(duì)其壓縮。

　　哈夫曼編碼是一種變長(zhǎng)編碼，即通過使用較短的碼字來給出現(xiàn)概率較高的信源符號(hào)編碼，而出現(xiàn)概率較小的信源符號(hào)用較長(zhǎng)的碼字來編碼，從而使平均碼長(zhǎng)最短，達(dá)到最佳編碼的目的。由于哈夫曼編碼只能對(duì)概率已知的信源符號(hào)編碼，因此是一種統(tǒng)計(jì)編碼。

　　2.2 構(gòu)造哈夫曼編碼表

　　獲得一個(gè)文件的哈夫曼編碼表是該文件獲得壓縮與解壓的關(guān)鍵。設(shè)某個(gè)文件中含有q種字符S1，S2，…，Sq，并且統(tǒng)計(jì)出每種字符在文件中出現(xiàn)的概率分別為p(S1)，p(S2)，…，p(Sq)，則編碼的具體方法如下：

　　(1)將q個(gè)信源符號(hào)按概率大小遞減排列p(S1)≥p(S2)≥…≥p(Sq);

　　(2)用字符‘O’和‘1’分別代表概率最小的2個(gè)信源符號(hào)，并將這2個(gè)概率最小的信源符號(hào)合并成1個(gè)信源符號(hào)，從而得到只包含q-1個(gè)符號(hào)的新信源，稱為縮減信源S1;

　　(3)把縮減信源S1的符號(hào)仍按概率大小遞減次序排列，再將其最后兩個(gè)概率最小的信源符號(hào)分別用字符‘O’和‘1’表示，并且合并成一個(gè)符號(hào)，這樣又形成了q-2個(gè)信源符號(hào)的縮減信源S2;

　　(4)依次繼續(xù)下去，直至信源最后只剩下兩個(gè)信源符號(hào)為止，將這最后兩個(gè)信源符號(hào)分別用字符‘O’和‘1’表示;

　　(5)然后從最后一級(jí)縮減信源開始，進(jìn)行回推就得到每種字符所對(duì)應(yīng)的由字符‘O’和‘1’組成的字符串序列，不妨將其稱為偽碼字。

　　這樣，就為需要壓縮的文件建立了一個(gè)一一映射f：Si→ci=1，2，…，q。式中：Si代表不同的字符，ci代表對(duì)應(yīng)字符Si的偽碼字。

　　為了將偽碼字變成真正的碼字，又必須建立一個(gè)映射g：ci→ω，i=1，2，…，q。式中：ci代表不同的字符，(ωi代表對(duì)應(yīng)字符ci的碼字。該映射g 的功能是將由字符串組成的偽碼字變成二進(jìn)制數(shù)，比如g(010110)=(010110)2=(22)10。從而g[f(Si)]，i=1，2，…，q，就是構(gòu)造的哈夫曼編碼表。

　　2.3 文件壓縮過程

　　每從文件中讀出一個(gè)字符char，用查哈夫曼編碼表的方式得到對(duì)應(yīng)的碼字，然后用這個(gè)碼字替換相應(yīng)的字符g[f(char)]。當(dāng)文件中的所有字符都經(jīng)過了碼字替換，則得到一個(gè)比原文件要小的壓縮文件。文件之所以能夠被壓縮，是因?yàn)槊總€(gè)字符都占8個(gè)二進(jìn)制位的空間。然而，通過碼字替換相應(yīng)的字符后，有的碼字比相應(yīng)的字符的碼長(zhǎng)要短，有的碼字比相應(yīng)的字符的碼長(zhǎng)要長(zhǎng)，但文件在被壓縮后總的長(zhǎng)度比原來要短。

　　2.4 文件解壓過程

　　文件的解壓過程是文件的壓縮過程的逆過程，即將一個(gè)壓縮文件還原成它的本來面目。因?yàn)橐粋€(gè)壓縮文件是不能夠直接使用的，只有被解壓后才能使用。一個(gè)被壓縮的文件如果不能被解壓，則這種壓縮是毫無意義的。

　　哈夫曼編碼是即時(shí)碼，只要得到碼字c，則經(jīng)查哈夫曼編碼表得到相應(yīng)字符f-1(g-1(c))，用這個(gè)字符替換相應(yīng)的碼字就是還原的過程。因此，每從壓縮文件中讀出一個(gè)碼字，就從哈夫曼編碼表查得相應(yīng)的字符替換，當(dāng)文件中所有的碼字被替換掉，這個(gè)解壓過程也就完成了。