演算法學習——哈夫曼編碼與字元文件壓縮
- 引言
世一大表示百分制轉換成五分制其實是有些麻煩的，天天坐辦公室的大爺們搞不定，需要同學們設計一個演算法，希望大家踴躍投稿。
這還不簡單，我很快便寫出了題圖上的演算法，還用C++實現了一遍：
double marksByHundred = 0;nint marksByFive = 0;nncout << "input your marks by hundred:" << endl;nnwhile( cin >> marksByHundred ){nn if ( marksByHundred < 0 ){n cout << "wrong input!!!" << endl; // 你才考負分！n }nn if ( marksByHundred <= 20 ){n marksByFive = 1;n }nn else if ( marksByHundred <= 40 ){n marksByFive = 2;n }nn else if ( marksByHundred <= 60 ){n marksByFive = 3;n }nn else if ( marksByHundred <= 80 ){n marksByFive = 4;n }nn else { n marksByFive = 5;n }nn cout << "your marks by five are: " << markByFive << endl;n}n
然而投往中心的稿件很快就被退了回來，世一大說，用你這種方法，和辦公室的老大爺們有什麼區別，我這才明白為什麼去年世一大自己的保研報名都截止了，成績卻還沒公示。
考慮一下實際情況，假如有10000名同學，成績大致分布如下：
按照題圖的演算法，10000名同學共需要判斷的次數為：
僅僅觀察這個式子也能夠發現這個數字可以變得更小，數字更小也就意味著可以進行更少的判斷，就可以給辦公室大爺們節省更多時間來豐富下班生活。
改變乘數的位置可以讓這個數字最小：
考慮實際的流程圖，這個式子並不能夠實現。
嘗試顛倒判斷次序後流程圖為：
可以看到顛倒判斷順序後我們為辦公室大爺們節省了近三分之一的時間，然而他們欲求不滿，想要用最少的時間做最多的工作。機智的我們考慮到分數在60-80間的人數是最多的，所以我們輸入的分數大概率是在60-80之間，那麼我們得到輸入後直接判斷是否在60-80之間，應該可以節省更多的時間，修改流程圖：
圖是變醜了，但判斷次數也變少了：
這次大爺們終於滿意了。
- 哈夫曼樹與哈夫曼編碼
首先引入二叉樹的一些概念：圖中連線的端點看作結點，結點向上連接著父結點，向下連接著子節點（崽），一些具有這種層次結構的結點連在一起便構成了一棵樹，如果在一棵樹中每個結點最多有2個崽，那麼這棵樹就叫做二叉樹。在上面的圖中除了葉子結點（沒有崽的結點）外每個結點都有2個崽。
那麼這個過程實際上可以看作是在構造一棵二叉樹，我們把人數放到相應的葉子結點上，這棵樹就成為了一棵帶權二叉樹：
要使判斷次數最少，也就是使得從樹根到每一個葉子結點的帶權路徑之和最小，而帶權路徑之和就是引言中列出的幾個算式，1、2、3、4代表從樹根到各個葉子結點的距離，100、900、2500、5000、1500代表葉子結點的權值。
剛才我們只是嘗試著優化了一下樹的結構，雖然大爺們已經滿意了，但是這是不是最優解呢？如果是最優解，那麼有沒有通用的方法可以構造出最優的二叉樹來？
故事回到1951年，MIT的哈夫曼同學正要面對令人頭疼的期末，老師告訴他，如果他能完成一個讓老師滿意的學期報告，就可以不用參加考試，和60年後的大家一樣討厭考試的哈夫曼同學果斷選擇了學期報告！報告的題目是「尋找最有效的二進位編碼」。不久後哈弗曼同學交上了一篇名為「可能是最好的二進位編碼」的報告，老師看完後皺了皺眉：「你這名字起的不好，得把「可能是」去掉。」同學們見狀紛紛稱讚道：「厲害了我的蛤！」
哈夫曼完全拋棄了前輩們採用固定位數的二進位編碼方法，大膽嘗試了不定長編碼。而編碼的方式，就是依據特定文件里不同字元出現的頻率不同來構造一棵二叉樹，使這棵樹葉子結點的帶權路徑之和最小。
和我們的例子對應起來，字元出現的頻率就是分數在某個區間內的學生人數，也就是葉子結點的權。每一個葉子結點代表一個字元，從樹根出發，沿著分支向下編碼，向左記為1，向右記為0。到達某個葉子結點時便可以生成一個二進位序列，這個序列就作為葉子結點所表示字元的編碼，例如下圖中五個字元的編碼分別為：
a:111ne:110ni:10no:01nu:00n
這種編碼還有一個名字叫做前綴碼，可能叫做非前綴碼更合適，因為它的含義是沒有任何一個字元的編碼是其他字元編碼的前綴，例如01是011的前綴，試想在解碼時在一連串的編碼里遇到了011，那麼是應該譯為01和1還是011？這就產生了歧義，而歧義正是不定長編碼需要避免的問題。
仔細觀察一下上圖，不難發現正是因為我們把字元都放在了葉子結點，編碼才具有了這種性質，如果把任何一個字元放到一個不是葉子結點的位置，例如把v放在u他爹的位置，那麼在遇到編碼00時就不知道是兩個v還是一個u了。
現在唯一的問題是如何使這種編碼最為有效，有效也就意味著用最少的編碼表示最多的字元。在上圖中葉子結點到樹根的距離就是編碼的長度，於是這棵樹中所有葉子結點的帶權路徑之和就代表了文件中所有編碼的長度之和。那麼我們要做的就是使帶權路徑之和最小，哈夫曼同學提出了一種簡單的演算法：
首先引入一些概念，一棵樹有且僅有一個根，而僅有一個根節點也可以成為一棵樹，許多棵樹放在一起就構成了森林。
哈夫曼同學告訴我們，先將所有的字元看作一棵一棵的樹，那麼一個文件里出現的字元種類就構成了一個森林，每棵樹的權值就是字元出現的頻率，從森林中拿出權值最小的兩棵樹，讓他們做一些不可描述的事情，成為一棵新的樹，新樹的權值是原來兩樹的權值之和，然後把這棵新樹再種回原來的森林，重複上面的過程，直到整個森林只剩下一棵樹，這棵樹就是我們要構造的最優二叉樹，也叫做哈夫曼樹，這棵樹對應的編碼，就稱為哈夫曼編碼。
假設五個字元的頻率分別為：
a:10次ne:5次ni:20次no:25次nu:30次n
得到的哈夫曼樹如下：
思考一下哈夫曼同學生成這棵樹的方法，實際上是在讓權值大的樹更靠近樹根，也就是讓出現頻率高的字元編碼更短，這就使帶權路徑之和取得了最小值。
回想一下剛才說到的帶權路徑之和也代表了文件中所有字元編碼的總長度，實際上就是整個文件的大小，於是這種編碼方式就給壓縮字元文件提供了一種思路：我們都知道計算機中的字元都用ASCⅡ碼錶示，而ASCⅡ碼是定長編碼，所有字元的編碼都是8位。在我們平常遇到的文件中可能並不是每一個字元都會出現，那麼這些編碼的位置就白白浪費了。在這種情況下我們可以事先統計一下文件中各個字元出現的頻率，然後按照上面構造哈夫曼樹的方法針對這個文件構造出一套哈夫曼編碼，並把編碼作為字典添加在文件中，這樣文件就得到了壓縮。
- 練習
提示：包括換行符和空格，字典大小可忽略不計。
Shes getting ready, ready for tonight.
Her friends are waiting but she still needs time.
Fixing her make up in the bathroom light.
Shes getting nervous and her heart beats fast.
She puts some perfume but not to much.
Maybe some lipstick but just the touch.
And then she thinks of you again.
As she hopes youll understand.
Shes wearing that black mascara, black mascara just for you.
Cause she wants you to know that she loves you.
Shes wearing that black mascara, black mascara just for you
Dont you realize she did it for you tonight?
The music is louder all the people dance.
And there youre standing talking to your friends
While she hopes for even just one glance.
Time is running hours passing by.
Why dont you see it? Dont you realize?
Shes waiting for you to come on by.
and tell her how pretty she looks tonight.
Shes wearing that black mascara, black mascara just for you.
Cause she wants you to know that she loves you.
Shes wearing that black mascara, black mascara just for you.
Dont you realize she did it for you tonight?
The pretty girl looks beautiful.
Why dont you turn around you fool.
She did it all because of you.
Shes wearing that black mascara, black mascara just for you.
Cause she wants you to know that she loves you.
Shes wearing that black mascara, black mascara just for you
Dont you realize she did it for you tonight?
推薦閱讀：
※最長公共子序列是否存在低於 O(n^2) 的演算法？
※如何將一個[10^3,10^15]上的整數儘可能多地表示成n個互不相同的因數乘積？
※程序員這一行業的知識有哪些本質性的東西？
※有隨著n規模增大，所用時間反而減小的演算法么？
※如何證明 a-b≤ a xor b ?