日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
圖解霍夫曼編碼，教不會(huì)我吃一包辣條

今天來(lái)給大家普及一下霍夫曼編碼(Huffman Coding)，一種用于無(wú)損數(shù)據(jù)壓縮的熵編碼算法，由美國(guó)計(jì)算機(jī)科學(xué)家大衛(wèi)·霍夫曼在 1952 年提出——這么專業(yè)的解釋，不用問(wèn)，來(lái)自維基百科了。

站在用戶的角度思考問(wèn)題，與客戶深入溝通，找到洪江網(wǎng)站設(shè)計(jì)與洪江網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類型包括：網(wǎng)站建設(shè)、成都網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、域名申請(qǐng)、網(wǎng)頁(yè)空間、企業(yè)郵箱。業(yè)務(wù)覆蓋洪江地區(qū)。

說(shuō)實(shí)話，很早之前我就聽(tīng)說(shuō)過(guò)霍夫曼編碼，除了知道它通常用于 GZIP、BZIP2、PKZIP 這些常規(guī)的壓縮格式中，我還知道它通常用于壓縮重復(fù)率比較高的字符數(shù)據(jù)。

大家想啊，英文就 26 個(gè)字母進(jìn)行的無(wú)限組合，重復(fù)率高得一逼啊!常用的漢字也不多，2500 個(gè)左右，別問(wèn)我怎么知道的，我有問(wèn)過(guò)搜索引擎的。

字符重復(fù)的頻率越高，霍夫曼編碼的工作效率就越高!

是時(shí)候，和大家一起來(lái)了解一下霍夫曼編碼的工作原理啦，畢竟一名優(yōu)秀的程序員要能做到知其然知其所以然——請(qǐng)?jiān)试S我又用了一次這句快用臭了話。

假設(shè)下面的字符串要通過(guò)網(wǎng)絡(luò)發(fā)送。

大家應(yīng)該知道，每個(gè)字符占 8 個(gè)比特，上面這串字符總共有 15 個(gè)字符，所以一共要占用 15*8=120 個(gè)比特。沒(méi)有疑問(wèn)吧?有疑問(wèn)的同學(xué)請(qǐng)不好意思下。

如果我們使用霍夫曼編碼的話，就可以將這串字符壓縮到一個(gè)更小的尺寸。怎么做到的呢?

霍夫曼編碼首先會(huì)使用字符的頻率創(chuàng)建一棵樹(shù)，然后通過(guò)這個(gè)樹(shù)的結(jié)構(gòu)為每個(gè)字符生成一個(gè)特定的編碼，出現(xiàn)頻率高的字符使用較短的編碼，出現(xiàn)頻率低的則使用較長(zhǎng)的編碼，這樣就會(huì)使編碼之后的字符串平均長(zhǎng)度降低，從而達(dá)到數(shù)據(jù)無(wú)損壓縮的目的。

拿上面這串初始字符來(lái)一步步的說(shuō)明下霍夫曼編碼的工作步驟。

第一步，計(jì)算字符串中每個(gè)字符的頻率。

B 出現(xiàn) 1 次，C 出現(xiàn) 6 次，A 出現(xiàn) 5 次，D 出現(xiàn) 3 次。

第二步，按照字符出現(xiàn)的頻率進(jìn)行排序，組成一個(gè)隊(duì)列 Q。

出現(xiàn)頻率最低的在前面，出現(xiàn)頻率高的在后面。

第三步，把這些字符作為葉子節(jié)點(diǎn)開(kāi)始構(gòu)建一顆樹(shù)。首先創(chuàng)建一個(gè)空節(jié)點(diǎn) z，將最小頻率的字符分配給 z 的左側(cè)，并將頻率排在第二位的分配給 z 的右側(cè)，然后將 z 賦值為兩個(gè)字符頻率的和。

B 的頻率最小，所以在左側(cè)，然后是頻率為 3 的 D，在右側(cè);然后把它們的父節(jié)點(diǎn)的值設(shè)為 4，子節(jié)點(diǎn)的頻率之和。

然后從隊(duì)列 Q 中刪除 B 和 D，并將它們的和添加到隊(duì)列中，上圖中 * 表示的位置。緊接著，重新創(chuàng)建一個(gè)空的節(jié)點(diǎn) z，并將 4 作為左側(cè)的節(jié)點(diǎn)，頻率為 5 的 A 作為右側(cè)的節(jié)點(diǎn)，4 與 5 的和作為父節(jié)點(diǎn)。

繼續(xù)按照之前的思路構(gòu)建樹(shù)，直到所有的字符都出現(xiàn)在樹(shù)的節(jié)點(diǎn)中。

第四步，對(duì)于每個(gè)非葉子節(jié)點(diǎn)，將 0 分配給連接線的左側(cè)，1 分配給連接線的右側(cè)。此時(shí)，霍夫曼樹(shù)就構(gòu)建完成了?；舴蚵鼧?shù)又稱為最優(yōu)二叉樹(shù)，是一種帶權(quán)路徑長(zhǎng)度最短的二叉樹(shù)。

當(dāng)樹(shù)構(gòu)建完畢后，我們來(lái)統(tǒng)計(jì)一下要發(fā)送的比特?cái)?shù)。

1)來(lái)看字符這一列。四個(gè)字符 A、B、C、D 共計(jì) 4*8=32 比特。每個(gè)英文字母均占用一個(gè)字節(jié)，即 8 個(gè)比特。

2)來(lái)看頻率這一列。A 5 次，B 1 次，C 6 次，D 3 次，一共 15 比特。

3)來(lái)看編碼這一列。A 的編碼為 11，對(duì)應(yīng)霍夫曼樹(shù)上的 15→9→5，也就是說(shuō)，從根節(jié)點(diǎn)走到葉子節(jié)點(diǎn) A，需要經(jīng)過(guò) 11 這條路徑;對(duì)應(yīng)的 B 需要走過(guò) 100 這條路徑;對(duì)應(yīng)的 D 需要走過(guò) 101 這條路徑;對(duì)應(yīng)的 C 需要走過(guò) 0 這條路徑。

4)來(lái)看長(zhǎng)度這一列。A 的編碼為 11，出現(xiàn)了 5 次，因此占用 10 個(gè)比特，即 1111111111;B 的編碼為 100，出現(xiàn)了 1 次，因此占用 3 個(gè)比特，即 100;C 的編碼為 0，出現(xiàn)了 6 次，因此占用 6 個(gè)比特，即 000000;D 的編碼為 101，出現(xiàn)了 3 次，因此占用 9 個(gè)比特，即 101101101。

哈夫曼編碼從本質(zhì)上講，是將最寶貴的資源(最短的編碼)給出現(xiàn)概率最多的數(shù)據(jù)。在上面的例子中，C 出現(xiàn)的頻率最高，它的編碼為 0，就省下了不少空間。

結(jié)合生活中的一些情況想一下，也是這樣，我們把最常用的放在手邊，這樣就能提高效率，節(jié)約時(shí)間。所以，我有一個(gè)大膽的猜想，霍夫曼就是這樣發(fā)現(xiàn)編碼的最優(yōu)解的。

在沒(méi)有經(jīng)過(guò)霍夫曼編碼之前，字符串“BCAADDDCCACACAC”的二進(jìn)制為：

 
 
 
 
    
  
  
  
  
  1. 10000100100001101000001010000010100010001000100010001000100001101000011010000010100001101000001010000110100000101000011
    2.

也就是占了 120 比特。

編碼之后為：

 
 
 
 
    
  
  
  
  
  1. 0000001001011011011111111111
    2.

占了 28 比特。

但考慮到解碼，需要把霍夫曼樹(shù)的結(jié)構(gòu)也傳遞過(guò)去，于是字符占用的 32 比特和頻率占用的 15 比特也需要傳遞過(guò)去。總體上，編碼后比特?cái)?shù)為 32 + 15 + 28 = 75，比 120 比特少了 45 個(gè)，效率還是非常高的。

關(guān)于霍夫曼編碼的 Java 示例，我在這里也貼出來(lái)一下，供大家參考。

 
 
 
 
    
  
  
  
  
  1. class HuffmanNode {
    2. 
  
  
  
  
  2.     int item;
    3. 
  
  
  
  
  3.     char c;
    4. 
  
  
  
  
  4.     HuffmanNode left;
    5. 
  
  
  
  
  5.     HuffmanNode right;
    6. 
  
  
  
  
  6. }
    7. 
  
  
  
  
  7. 
  
  
  
  
  8. class ImplementComparator implements Comparator {
    9. 
  
  
  
  
  9.     public int compare(HuffmanNode x, HuffmanNode y) {
    10. 
  
  
  
  
  10.         return x.item - y.item;
    11. 
  
  
  
  
  11.     }
    12. 
  
  
  
  
  12. }
    13. 
  
  
  
  
  13. 
  
  
  
  
  14. public class Huffman {
    15. 
  
  
  
  
  15.     public static void printCode(HuffmanNode root, String s) {
    16. 
  
  
  
  
  16.         if (root.left == null && root.right == null && Character.isLetter(root.c)) {
    17. 
  
  
  
  
  17. 
  
  
  
  
  18.             System.out.println(root.c + "   |  " + s);
    19. 
  
  
  
  
  19. 
  
  
  
  
  20.             return;
    21. 
  
  
  
  
  21.         }
    22. 
  
  
  
  
  22.         printCode(root.left, s + "0");
    23. 
  
  
  
  
  23.         printCode(root.right, s + "1");
    24. 
  
  
  
  
  24.     }
    25. 
  
  
  
  
  25. 
  
  
  
  
  26.     public static void main(String[] args) {
    27. 
  
  
  
  
  27.         int n = 4;
    28. 
  
  
  
  
  28.         char[] charArray = { 'A', 'B', 'C', 'D' };
    29. 
  
  
  
  
  29.         int[] charfreq = { 5, 1, 6, 3 };
    30. 
  
  
  
  
  30. 
  
  
  
  
  31.         PriorityQueue q = new PriorityQueue(n, new ImplementComparator());
    32. 
  
  
  
  
  32. 
  
  
  
  
  33.         for (int i = 0; i < n; i++) {
    34. 
  
  
  
  
  34.             HuffmanNode hn = new HuffmanNode();
    35. 
  
  
  
  
  35. 
  
  
  
  
  36.             hn.c = charArray[i];
    37. 
  
  
  
  
  37.             hn.item = charfreq[i];
    38. 
  
  
  
  
  38. 
  
  
  
  
  39.             hn.left = null;
    40. 
  
  
  
  
  40.             hn.right = null;
    41. 
  
  
  
  
  41. 
  
  
  
  
  42.             q.add(hn);
    43. 
  
  
  
  
  43.         }
    44. 
  
  
  
  
  44. 
  
  
  
  
  45.         HuffmanNode root = null;
    46. 
  
  
  
  
  46. 
  
  
  
  
  47.         while (q.size() > 1) {
    48. 
  
  
  
  
  48. 
  
  
  
  
  49.             HuffmanNode x = q.peek();
    50. 
  
  
  
  
  50.             q.poll();
    51. 
  
  
  
  
  51. 
  
  
  
  
  52.             HuffmanNode y = q.peek();
    53. 
  
  
  
  
  53.             q.poll();
    54. 
  
  
  
  
  54. 
  
  
  
  
  55.             HuffmanNode f = new HuffmanNode();
    56. 
  
  
  
  
  56. 
  
  
  
  
  57.             f.item = x.item + y.item;
    58. 
  
  
  
  
  58.             f.c = '-';
    59. 
  
  
  
  
  59.             f.left = x;
    60. 
  
  
  
  
  60.             f.right = y;
    61. 
  
  
  
  
  61.             root = f;
    62. 
  
  
  
  
  62. 
  
  
  
  
  63.             q.add(f);
    64. 
  
  
  
  
  64.         }
    65. 
  
  
  
  
  65.         System.out.println(" 字符 | 霍夫曼編碼 ");
    66. 
  
  
  
  
  66.         System.out.println("--------------------");
    67. 
  
  
  
  
  67.         printCode(root, "");
    68. 
  
  
  
  
  68.     }
    69. 
  
  
  
  
  69. }
    70.

本例的輸出結(jié)果如下所示：

 
 
 
 
    
  
  
  
  
  1. 字符 | 霍夫曼編碼 
    2. 
  
  
  
  
  2. --------------------
    3. 
  
  
  
  
  3. C   |  0
    4. 
  
  
  
  
  4. B   |  100
    5. 
  
  
  
  
  5. D   |  101
    6. 
  
  
  
  
  6. A   |  11
    7.

給大家留個(gè)作業(yè)題吧，考慮一下霍夫曼編碼的時(shí)間復(fù)雜度，知道的同學(xué)可以在留言區(qū)給出答案哈。

搞定，我敢肯定辣條不用吃了——因?yàn)榇蠹铱隙ǘ紝W(xué)會(huì)了。我是愛(ài)學(xué)習(xí)愛(ài)美貌的沉默王二，我們下期見(jiàn)，see you~

本文轉(zhuǎn)載自微信公眾號(hào)「沉默王二」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系沉默王二公眾號(hào)。


名稱欄目：圖解霍夫曼編碼，教不會(huì)我吃一包辣條
網(wǎng)頁(yè)地址：http://www.5511xx.com/article/cdjoods.html