建站
咨詢
售后
建站咨詢
新聞中心
今天來給大家普及一下霍夫曼編碼(Huffman Coding)，一種用于無損數據壓縮的熵編碼算法，由美國計算機科學家大衛(wèi)·霍夫曼在 1952 年提出——這么專業(yè)的解釋，不用問，來自維基百科了。
站在用戶的角度思考問題，與客戶深入溝通，找到洪江網站設計與洪江網站推廣的解決方案，憑借多年的經驗，讓設計與互聯(lián)網技術結合，創(chuàng)造個性化、用戶體驗好的作品，建站類型包括：網站建設、成都網站建設、企業(yè)官網、英文網站、手機端網站、網站推廣、域名申請、網頁空間、企業(yè)郵箱。業(yè)務覆蓋洪江地區(qū)。
說實話，很早之前我就聽說過霍夫曼編碼，除了知道它通常用于 GZIP、BZIP2、PKZIP 這些常規(guī)的壓縮格式中，我還知道它通常用于壓縮重復率比較高的字符數據。
大家想啊，英文就 26 個字母進行的無限組合，重復率高得一逼啊!常用的漢字也不多，2500 個左右，別問我怎么知道的，我有問過搜索引擎的。
字符重復的頻率越高，霍夫曼編碼的工作效率就越高!
是時候，和大家一起來了解一下霍夫曼編碼的工作原理啦，畢竟一名優(yōu)秀的程序員要能做到知其然知其所以然——請允許我又用了一次這句快用臭了話。
假設下面的字符串要通過網絡發(fā)送。
大家應該知道，每個字符占 8 個比特，上面這串字符總共有 15 個字符，所以一共要占用 15*8=120 個比特。沒有疑問吧?有疑問的同學請不好意思下。
如果我們使用霍夫曼編碼的話，就可以將這串字符壓縮到一個更小的尺寸。怎么做到的呢?
霍夫曼編碼首先會使用字符的頻率創(chuàng)建一棵樹，然后通過這個樹的結構為每個字符生成一個特定的編碼，出現(xiàn)頻率高的字符使用較短的編碼，出現(xiàn)頻率低的則使用較長的編碼，這樣就會使編碼之后的字符串平均長度降低，從而達到數據無損壓縮的目的。
拿上面這串初始字符來一步步的說明下霍夫曼編碼的工作步驟。
第一步，計算字符串中每個字符的頻率。
B 出現(xiàn) 1 次，C 出現(xiàn) 6 次，A 出現(xiàn) 5 次，D 出現(xiàn) 3 次。
第二步，按照字符出現(xiàn)的頻率進行排序，組成一個隊列 Q。
出現(xiàn)頻率最低的在前面，出現(xiàn)頻率高的在后面。
第三步，把這些字符作為葉子節(jié)點開始構建一顆樹。首先創(chuàng)建一個空節(jié)點 z，將最小頻率的字符分配給 z 的左側，并將頻率排在第二位的分配給 z 的右側，然后將 z 賦值為兩個字符頻率的和。
B 的頻率最小，所以在左側，然后是頻率為 3 的 D，在右側;然后把它們的父節(jié)點的值設為 4，子節(jié)點的頻率之和。
然后從隊列 Q 中刪除 B 和 D，并將它們的和添加到隊列中，上圖中 * 表示的位置。緊接著，重新創(chuàng)建一個空的節(jié)點 z，并將 4 作為左側的節(jié)點，頻率為 5 的 A 作為右側的節(jié)點，4 與 5 的和作為父節(jié)點。
繼續(xù)按照之前的思路構建樹，直到所有的字符都出現(xiàn)在樹的節(jié)點中。
第四步，對于每個非葉子節(jié)點，將 0 分配給連接線的左側，1 分配給連接線的右側。此時，霍夫曼樹就構建完成了?；舴蚵鼧溆址Q為最優(yōu)二叉樹，是一種帶權路徑長度最短的二叉樹。
當樹構建完畢后，我們來統(tǒng)計一下要發(fā)送的比特數。
1)來看字符這一列。四個字符 A、B、C、D 共計 4*8=32 比特。每個英文字母均占用一個字節(jié)，即 8 個比特。
2)來看頻率這一列。A 5 次，B 1 次，C 6 次，D 3 次，一共 15 比特。
3)來看編碼這一列。A 的編碼為 11，對應霍夫曼樹上的 15→9→5，也就是說，從根節(jié)點走到葉子節(jié)點 A，需要經過 11 這條路徑;對應的 B 需要走過 100 這條路徑;對應的 D 需要走過 101 這條路徑;對應的 C 需要走過 0 這條路徑。
4)來看長度這一列。A 的編碼為 11，出現(xiàn)了 5 次，因此占用 10 個比特，即 1111111111;B 的編碼為 100，出現(xiàn)了 1 次，因此占用 3 個比特，即 100;C 的編碼為 0，出現(xiàn)了 6 次，因此占用 6 個比特，即 000000;D 的編碼為 101，出現(xiàn)了 3 次，因此占用 9 個比特，即 101101101。
哈夫曼編碼從本質上講，是將最寶貴的資源(最短的編碼)給出現(xiàn)概率最多的數據。在上面的例子中，C 出現(xiàn)的頻率最高，它的編碼為 0，就省下了不少空間。
結合生活中的一些情況想一下，也是這樣，我們把最常用的放在手邊，這樣就能提高效率，節(jié)約時間。所以，我有一個大膽的猜想，霍夫曼就是這樣發(fā)現(xiàn)編碼的最優(yōu)解的。
在沒有經過霍夫曼編碼之前，字符串“BCAADDDCCACACAC”的二進制為：
- 10000100100001101000001010000010100010001000100010001000100001101000011010000010100001101000001010000110100000101000011
也就是占了 120 比特。
編碼之后為：
- 0000001001011011011111111111
占了 28 比特。
但考慮到解碼，需要把霍夫曼樹的結構也傳遞過去，于是字符占用的 32 比特和頻率占用的 15 比特也需要傳遞過去。總體上，編碼后比特數為 32 + 15 + 28 = 75，比 120 比特少了 45 個，效率還是非常高的。
關于霍夫曼編碼的 Java 示例，我在這里也貼出來一下，供大家參考。
- class HuffmanNode {
- int item;
- char c;
- HuffmanNode left;
- HuffmanNode right;
- }
- class ImplementComparator implements Comparator
{ - public int compare(HuffmanNode x, HuffmanNode y) {
- return x.item - y.item;
- }
- }
- public class Huffman {
- public static void printCode(HuffmanNode root, String s) {
- if (root.left == null && root.right == null && Character.isLetter(root.c)) {
- System.out.println(root.c + " | " + s);
- return;
- }
- printCode(root.left, s + "0");
- printCode(root.right, s + "1");
- }
- public static void main(String[] args) {
- int n = 4;
- char[] charArray = { 'A', 'B', 'C', 'D' };
- int[] charfreq = { 5, 1, 6, 3 };
- PriorityQueue
q = new PriorityQueue (n, new ImplementComparator()); - for (int i = 0; i < n; i++) {
- HuffmanNode hn = new HuffmanNode();
- hn.c = charArray[i];
- hn.item = charfreq[i];
- hn.left = null;
- hn.right = null;
- q.add(hn);
- }
- HuffmanNode root = null;
- while (q.size() > 1) {
- HuffmanNode x = q.peek();
- q.poll();
- HuffmanNode y = q.peek();
- q.poll();
- HuffmanNode f = new HuffmanNode();
- f.item = x.item + y.item;
- f.c = '-';
- f.left = x;
- f.right = y;
- root = f;
- q.add(f);
- }
- System.out.println(" 字符 | 霍夫曼編碼 ");
- System.out.println("--------------------");
- printCode(root, "");
- }
- }
本例的輸出結果如下所示：
- 字符 | 霍夫曼編碼
- --------------------
- C | 0
- B | 100
- D | 101
- A | 11
給大家留個作業(yè)題吧，考慮一下霍夫曼編碼的時間復雜度，知道的同學可以在留言區(qū)給出答案哈。
搞定，我敢肯定辣條不用吃了——因為大家肯定都學會了。我是愛學習愛美貌的沉默王二，我們下期見，see you~
本文轉載自微信公眾號「沉默王二」，可以通過以下二維碼關注。轉載本文請聯(lián)系沉默王二公眾號。
文章題目：圖解霍夫曼編碼，教不會我吃一包辣條
本文網址：http://www.dlmjj.cn/article/cdjoods.html
