# 哈夫曼編碼和游程編碼 # 游程編碼和哈夫曼編碼 ## Huffman encode(哈夫曼編碼) Huffman 編碼的基本思想就是用短的編碼表示出現頻率高的字符，用長的編碼來表示出現頻率低的字符，這使得編碼之后的字符串的平均長度、長度的期望值降低，從而實現壓縮的目的。 因此 Huffman 編碼被廣泛地應用于無損壓縮領域。 Huffman 編碼的過程包含兩個主要部分： - 根據輸入字符構建 Huffman 樹 - 遍歷 Huffman 樹，并將樹的節點分配給字符 上面提到了他的基本原理就是`用短的編碼表示出現頻率高的字符，用長的編碼來表示出現頻率低的字符`, 因此首先要做的就是統計字符的出現頻率，然后根據統計的頻率來構建 Huffman 樹（又叫最優二叉樹）。  Huffman 樹就像是一個堆。真正執行編碼的時候，類似字典樹，節點不用來編碼，節點的路徑用來編碼. > 節點的值只是用來構建 Huffman 樹 eg: 我們統計的結果如下： characterfrequencya5b9c12d13e16f45- 將每個元素構造成一個節點，即只有一個元素的樹。并構建一個最小堆，包含所有的節點，該算法用了最小堆來作為優先隊列。 - `選取兩個權值最小的節點`，并添加一個權值為5+9=14的節點，作為他們的父節點。并`更新最小堆`，現在最小堆包含5個節點，其中4個樹還是原來的節點，權值為5和9的節點合并為一個。 結果是這樣的：  characterfrequencyencodinga51100b91101c12100d13101e16111f450## run-length encode(游程編碼) 游程編碼是一種比較簡單的壓縮算法，其基本思想是將重復且連續出現多次的字符使用（連續出現次數，某個字符）來描述。 比如一個字符串： ``` <pre class="calibre18">``` AAAAABBBBCCC ``` ``` 使用游程編碼可以將其描述為： ``` <pre class="calibre18">``` 5A4B3C ``` ``` 5A表示這個地方有5個連續的A，同理4B表示有4個連續的B，3C表示有3個連續的C，其它情況以此類推。 但是實際上情況可能會非常復雜， 如何提取子序列有時候沒有看的那么簡單，還是上面的例子，我們 有時候可以把`AAAAABBBBCCC`整體看成一個子序列， 更復雜的情況還有很多，這里不做擴展。 對文件進行壓縮比較適合的情況是文件內的二進制有大量的連續重復， 一個經典的例子就是具有大面積色塊的BMP圖像，BMP因為沒有壓縮， 所以看到的是什么樣子存儲的時候二進制就是什么樣子 > 這也是我們圖片傾向于純色的時候，壓縮會有很好的效果 > > 思考一個問題， 如果我們在CDN上存儲兩個圖片，這兩個圖片幾乎完全一樣，我們是否可以進行優化呢？ 這雖然是CDN廠商更應該關心的問題，但是這個問題對我們影響依然很大，值得思考 ## 總結 游程編碼和Huffman都是無損壓縮算法，即解壓縮過程不會損失原數據任何內容。 實際情況，我們先用游程編碼一遍，然后再用 Huffman 再次編碼一次。幾乎所有的無損壓縮格式都用到了它們，比如PNG，GIF，PDF，ZIP等。 對于有損壓縮，通常是去除了人類無法識別的顏色，聽力頻率范圍等。也就是說損失了原來的數據。 但由于人類無法識別這部分信息，因此很多情況下都是值得的。這種刪除了人類無法感知內容的編碼，我們稱之為“感知編碼”（也許是一個自創的新名詞），比如JPEG，MP3等。關于有損壓縮不是本文的討論范圍，感興趣的可以搜素相關資料。 實際上，視頻壓縮的原理也是類似，只不過視頻壓縮會用到一些額外的算法，比如“時間冗余”，即僅存儲變化的部分，對于不變的部分，存儲一次就夠了。 ## 相關題目 [900.rle-iterator](900.rle-iterator.html)