日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

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

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
原以為哈夫曼樹(shù)、哈夫曼編碼很難，結(jié)果……

哈夫曼樹(shù)介紹

大家好，我是bigsai。原以為哈夫曼樹(shù)、哈夫曼編碼很難，結(jié)果它很簡(jiǎn)單啊老鐵們!

創(chuàng)新互聯(lián)專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、秀山土家族苗族網(wǎng)絡(luò)推廣、小程序設(shè)計(jì)、秀山土家族苗族網(wǎng)絡(luò)營(yíng)銷、秀山土家族苗族企業(yè)策劃、秀山土家族苗族品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等，從售前售中售后，我們都將竭誠(chéng)為您服務(wù)，您的肯定，是我們最大的嘉獎(jiǎng)；創(chuàng)新互聯(lián)為所有大學(xué)生創(chuàng)業(yè)者提供秀山土家族苗族建站搭建服務(wù)，24小時(shí)服務(wù)熱線：18982081108，官方網(wǎng)址：www.cdcxhl.com

哈夫曼樹(shù)、哈夫曼編碼很多人可能聽(tīng)過(guò)，但是可能并沒(méi)有認(rèn)真學(xué)習(xí)了解，今天這篇就比較詳細(xì)的講一下哈夫曼樹(shù)。

首先哈夫曼樹(shù)是什么?

哈夫曼樹(shù)的定義：給定N個(gè)權(quán)值作為N個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹(shù)，若該樹(shù)的帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱為哈夫曼樹(shù)(Huffman Tree)，哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)。權(quán)值較大的結(jié)點(diǎn)離根較近。

那這個(gè)樹(shù)長(zhǎng)啥樣子呢?例如開(kāi)始2，3，6，8，9權(quán)值節(jié)點(diǎn)構(gòu)成的哈夫曼樹(shù)是這樣的：

從定義和圖上你也可以發(fā)現(xiàn)下面的規(guī)律：

  • 初始節(jié)點(diǎn)都在樹(shù)的葉子節(jié)點(diǎn)上
  • 權(quán)值大的節(jié)點(diǎn)離根更近
  • 每個(gè)非葉子節(jié)點(diǎn)都有兩個(gè)孩子(因?yàn)槲覀冏韵孪蛏蠘?gòu)造，兩個(gè)孩子構(gòu)成一個(gè)新樹(shù)的根節(jié)點(diǎn))

你可能會(huì)好奇這么一個(gè)哈夫曼樹(shù)是怎么構(gòu)造的，其實(shí)它是按照一個(gè)貪心思想和規(guī)則構(gòu)造，而構(gòu)造出來(lái)的這個(gè)樹(shù)的權(quán)值最小。這個(gè)規(guī)則下面會(huì)具體講解。

哈夫曼樹(shù)非常重要的一點(diǎn)：WPL(樹(shù)的所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和)。至于為什么按照哈夫曼樹(shù)方法構(gòu)造得到的權(quán)重最小,這里不進(jìn)行證明,但是你從局部來(lái)看(三個(gè)節(jié)點(diǎn))也要權(quán)值大的在上一層WPL才更低。

WPL計(jì)算方法: WPL=求和(Wi * Li)其中Wi是第i個(gè)節(jié)點(diǎn)的權(quán)值(value)。Li是第i個(gè)節(jié)點(diǎn)的長(zhǎng)(深)度.

例如上面 2，3，6，8，9權(quán)值節(jié)點(diǎn)構(gòu)成的哈夫曼樹(shù)的WPL計(jì)算為(設(shè)根為第0層)：

比如上述哈夫曼樹(shù)的WPL為：2*3+3*3+6*2+8*2+9*2=(2+3)*3+(6+8+9)*2=61.

既然了解了哈夫曼樹(shù)的一些概念和WPL的計(jì)算方式，下面看看哈夫曼樹(shù)的具體構(gòu)造方式吧!

哈夫曼樹(shù)構(gòu)造

初始給一個(gè)森林有n個(gè)節(jié)點(diǎn)。我們主要使用貪心的思想來(lái)完成哈夫曼樹(shù)的構(gòu)造：

  • 在n個(gè)節(jié)點(diǎn)找到兩個(gè)最小權(quán)值節(jié)點(diǎn)(根)，兩個(gè)為葉子結(jié)構(gòu)構(gòu)建一棵新樹(shù)(根節(jié)點(diǎn)權(quán)值為左右孩子權(quán)值和)
  • 先刪掉兩個(gè)最小節(jié)點(diǎn)(n-2)個(gè)，然后加入構(gòu)建的新節(jié)點(diǎn)(n-1)個(gè)
  • 重復(fù)上面操作，一直到所有節(jié)點(diǎn)都被處理

在具體實(shí)現(xiàn)上，找到最小兩個(gè)節(jié)點(diǎn)需要排序操作，我們來(lái)看看2，6，8，9，3權(quán)值節(jié)點(diǎn)構(gòu)成哈夫曼樹(shù)的過(guò)程。

初始時(shí)候各個(gè)節(jié)點(diǎn)獨(dú)立，先將其排序(這里使用優(yōu)先隊(duì)列)，然后選兩個(gè)最小節(jié)點(diǎn)(拋出)生成一個(gè)新的節(jié)點(diǎn)，再將其加入優(yōu)先隊(duì)列中，此次操作完成后優(yōu)先隊(duì)列中有5，6，8，9節(jié)點(diǎn)

重復(fù)上面操作，這次結(jié)束 隊(duì)列中有11，8，9節(jié)點(diǎn)(排序后8，9，11)

圖片如果隊(duì)列為空，那么返回節(jié)點(diǎn)，并且這個(gè)節(jié)點(diǎn)為整個(gè)哈夫曼樹(shù)根節(jié)點(diǎn)root。

否則繼續(xù)加入隊(duì)列進(jìn)行排序。重復(fù)上述操作，直到隊(duì)列為空。

在計(jì)算帶權(quán)路徑長(zhǎng)度WPL的時(shí)候，需要重新計(jì)算高度(從下往上)，因?yàn)楣蚵鼧?shù)是從下往上構(gòu)造的，并沒(méi)有以常量維護(hù)高度，可以構(gòu)造好然后計(jì)算高度。

具體代碼實(shí)現(xiàn)(僅供參考)

 
 
 
 
    
  
  
  
  
  1. import java.util.ArrayDeque;
    2. 
  
  
  
  
  2. import java.util.ArrayList;
    3. 
  
  
  
  
  3. import java.util.Comparator;
    4. 
  
  
  
  
  4. import java.util.List;
    5. 
  
  
  
  
  5. import java.util.PriorityQueue;
    6. 
  
  
  
  
  6. import java.util.Queue;
    7. 
  
  
  
  
  7. 
  
  
  
  
  8. public class HuffmanTree {    
    9. 
  
  
  
  
  9.     public static class node
    10. 
  
  
  
  
  10.     {
    11. 
  
  
  
  
  11.         int value;
    12. 
  
  
  
  
  12.         node left;
    13. 
  
  
  
  
  13.         node right;
    14. 
  
  
  
  
  14.         int deep;//記錄深度
    15. 
  
  
  
  
  15.         public node(int value) {
    16. 
  
  
  
  
  16.             this.value=value;
    17. 
  
  
  
  
  17.             this.deep=0;
    18. 
  
  
  
  
  18.         }
    19. 
  
  
  
  
  19.         public node(node n1, node n2, int value) {
    20. 
  
  
  
  
  20.             this.left=n1;
    21. 
  
  
  
  
  21.             this.right=n2;
    22. 
  
  
  
  
  22.             this.value=value;
    23. 
  
  
  
  
  23.         }
    24. 
  
  
  
  
  24.     }
    25. 
  
  
  
  
  25.     private node root;//最后生成的根節(jié)點(diǎn)
    26. 
  
  
  
  
  26.     Listnodes;
    27. 
  
  
  
  
  27.     public HuffmanTree() {
    28. 
  
  
  
  
  28.         this.nodes=null;
    29. 
  
  
  
  
  29.     }
    30. 
  
  
  
  
  30.     public HuffmanTree(Listnodes)
    31. 
  
  
  
  
  31.     {
    32. 
  
  
  
  
  32.         this.nodes=nodes;
    33. 
  
  
  
  
  33.     }
    34. 
  
  
  
  
  34.     public void createTree() {
    35. 
  
  
  
  
  35.        Queueq1=new PriorityQueue(new Comparator() {
    36. 
  
  
  
  
  36.       public int compare(node o1, node o2) {
    37. 
  
  
  
  
  37.         return o1.value-o2.value;
    38. 
  
  
  
  
  38.       }});
    39. 
  
  
  
  
  39.        q1.addAll(nodes);
    40. 
  
  
  
  
  40.        while(!q1.isEmpty()){
    41. 
  
  
  
  
  41.            node n1=q1.poll();
    42. 
  
  
  
  
  42.            node n2=q1.poll();
    43. 
  
  
  
  
  43.           node parent=new node(n1,n2,n1.value+n2.value);
    44. 
  
  
  
  
  44.           if(q1.isEmpty()){
    45. 
  
  
  
  
  45.               root=parent;return;
    46. 
  
  
  
  
  46.           }
    47. 
  
  
  
  
  47.           q1.add(parent);
    48. 
  
  
  
  
  48.        }
    49. 
  
  
  
  
  49.     }
    50. 
  
  
  
  
  50.     public int getweight() {
    51. 
  
  
  
  
  51.         Queueq1=new ArrayDeque();
    52. 
  
  
  
  
  52.         q1.add(root);
    53. 
  
  
  
  
  53.         int weight=0;
    54. 
  
  
  
  
  54.         while (!q1.isEmpty()) {
    55. 
  
  
  
  
  55.             node va=q1.poll();
    56. 
  
  
  
  
  56.             if(va.left!=null){
    57. 
  
  
  
  
  57.                 va.left.deep=va.deep+1;va.right.deep=va.deep+1;
    58. 
  
  
  
  
  58.                 q1.add(va.left);q1.add(va.right);
    59. 
  
  
  
  
  59.             }
    60. 
  
  
  
  
  60.             else {
    61. 
  
  
  
  
  61.                 weight+=va.deep*va.value;
    62. 
  
  
  
  
  62.             }
    63. 
  
  
  
  
  63.         }
    64. 
  
  
  
  
  64.         return weight;
    65. 
  
  
  
  
  65.     }
    66. 
  
  
  
  
  66.     public static void main(String[] args) {
    67. 
  
  
  
  
  67.         Listlist=new ArrayList();
    68. 
  
  
  
  
  68.         list.add(new node(2));
    69. 
  
  
  
  
  69.         list.add(new node(3));
    70. 
  
  
  
  
  70.         list.add(new node(6));
    71. 
  
  
  
  
  71.         list.add(new node(8));list.add(new node(9));
    72. 
  
  
  
  
  72.         HuffmanTree tree=new HuffmanTree();
    73. 
  
  
  
  
  73.         tree.nodes=list;
    74. 
  
  
  
  
  74.         tree.createTree();
    75. 
  
  
  
  
  75.         System.out.println(tree.getweight());
    76. 
  
  
  
  
  76.     }
    77. 
  
  
  
  
  77. }
    78.

輸出結(jié)果:

 
 
 
 
    
  
  
  
  
  1. 61
    2.

哈夫曼編碼

除了哈夫曼樹(shù)你聽(tīng)過(guò)，哈夫曼編碼你可能也聽(tīng)過(guò)，但是不一定了解它是個(gè)什么玩意兒，哈夫曼編碼其實(shí)就是哈夫曼樹(shù)的一個(gè)非常重要的應(yīng)用，在這里就簡(jiǎn)單介紹原理并不詳細(xì)實(shí)現(xiàn)了。

哈夫曼編碼定義：哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長(zhǎng)編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來(lái)構(gòu)造異字頭的平均長(zhǎng)度最短的碼字，有時(shí)稱之為最佳編碼，一般就叫做Huffman編碼(有時(shí)也稱為霍夫曼編碼)。

哈夫曼編碼的目的是為了減少存儲(chǔ)體積，以一個(gè)連續(xù)的字符串為例，拋開(kāi)編程語(yǔ)言中實(shí)際存儲(chǔ)，就拿

aaaaaaaaaabbbbbcccdde

這個(gè)字符串來(lái)說(shuō)，在計(jì)算機(jī)中如果每個(gè)字符都是定長(zhǎng)存儲(chǔ)(假設(shè)長(zhǎng)為4的二進(jìn)制存儲(chǔ))，計(jì)算機(jī)只知道0和1的二進(jìn)制，假設(shè)

 
 
 
 
    
  
  
  
  
  1. a:0001
    2. 
  
  
  
  
  2. b:0010
    3. 
  
  
  
  
  3. c:0011
    4. 
  
  
  
  
  4. d:0100
    5. 
  
  
  
  
  5. e:0101
    6.

那么上面字符串可以用二進(jìn)制存儲(chǔ)是這樣的

000100010001000100010001……0101

如果每個(gè)字符編碼等長(zhǎng)，那么就沒(méi)有存儲(chǔ)空間優(yōu)化可言，都是單個(gè)字符長(zhǎng)度 * 字符個(gè)數(shù)。但是如果每個(gè)字符編碼不等長(zhǎng)，那么設(shè)計(jì)的開(kāi)放性就很強(qiáng)了。

比如一個(gè)字符串a(chǎn)aaaabb

如果設(shè)計(jì)a為01，b設(shè)計(jì)為1。那么二進(jìn)制就為：010101010111

如果設(shè)計(jì)a為1，b設(shè)計(jì)為01。那么二進(jìn)制就為：111110101

如果設(shè)計(jì)a為1，b設(shè)計(jì)為0。那么二進(jìn)制就為：1111100

你看，在計(jì)算機(jī)的01二進(jìn)制世界中，明顯第二種比第一種優(yōu)先，第三種又比第二種優(yōu)先。所以，設(shè)計(jì)編碼要考慮讓出現(xiàn)多的盡量更短，出現(xiàn)少的稍微長(zhǎng)點(diǎn)沒(méi)關(guān)系。

但是，你需要考慮的一個(gè)問(wèn)題是，二進(jìn)制開(kāi)始0，1，01，10，11這個(gè)順序 ，如果來(lái)了001它到底是0，0，1還是0，01呢?所以編碼不等長(zhǎng)的時(shí)候你要考慮到這個(gè)編碼要有唯一性不能出現(xiàn)歧義。這個(gè)怎么搞呢?

簡(jiǎn)單啊，計(jì)算機(jī)只知道01二進(jìn)制，而二叉樹(shù)剛好有左右兩個(gè)節(jié)點(diǎn)，至于一個(gè)字符它如果是對(duì)應(yīng)葉子節(jié)點(diǎn)，那么就可以直接確定，也就是這個(gè)數(shù)值如果映射成一個(gè)二叉樹(shù)字符不能存在非葉子節(jié)點(diǎn)上。

所以，哈夫曼編碼具體流程就很清晰了，先統(tǒng)計(jì)字符出現(xiàn)的次數(shù)，然后將這個(gè)次數(shù)當(dāng)成權(quán)值按照上面介紹的方法構(gòu)造一棵哈夫曼樹(shù)，然后樹(shù)的根不存，往左為0往右為1每個(gè)葉子節(jié)點(diǎn)得到的二進(jìn)制數(shù)字就是它的編碼，這樣頻率高的字符在上面更短在整個(gè)二進(jìn)制存儲(chǔ)中也更節(jié)省空間。

結(jié)語(yǔ)

哈夫曼樹(shù)還是比較容易理解，主要構(gòu)造利用貪心算法的思想去從下往上構(gòu)建，哈夫曼編碼相信看了你也有所收獲，有興趣可以自己實(shí)現(xiàn)一下哈夫曼編碼的代碼(編碼、解碼)。本人水平有限，如果有錯(cuò)誤還希望大佬指正!


分享題目：原以為哈夫曼樹(shù)、哈夫曼編碼很難，結(jié)果……
文章URL：http://www.dlmjj.cn/article/cdodopd.html