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

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

新聞中心

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

哈夫曼樹介紹

大家好，我是bigsai。原以為哈夫曼樹、哈夫曼編碼很難，結果它很簡單啊老鐵們!

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

哈夫曼樹、哈夫曼編碼很多人可能聽過，但是可能并沒有認真學習了解，今天這篇就比較詳細的講一下哈夫曼樹。

首先哈夫曼樹是什么?

哈夫曼樹的定義：給定N個權值作為N個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman Tree)，哈夫曼樹是帶權路徑長度最短的樹。權值較大的結點離根較近。

那這個樹長啥樣子呢?例如開始2，3，6，8，9權值節(jié)點構成的哈夫曼樹是這樣的：

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

  • 初始節(jié)點都在樹的葉子節(jié)點上
  • 權值大的節(jié)點離根更近
  • 每個非葉子節(jié)點都有兩個孩子(因為我們自下向上構造，兩個孩子構成一個新樹的根節(jié)點)

你可能會好奇這么一個哈夫曼樹是怎么構造的，其實它是按照一個貪心思想和規(guī)則構造，而構造出來的這個樹的權值最小。這個規(guī)則下面會具體講解。

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

WPL計算方法: WPL=求和(Wi * Li)其中Wi是第i個節(jié)點的權值(value)。Li是第i個節(jié)點的長(深)度.

例如上面 2，3，6，8，9權值節(jié)點構成的哈夫曼樹的WPL計算為(設根為第0層)：

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

既然了解了哈夫曼樹的一些概念和WPL的計算方式，下面看看哈夫曼樹的具體構造方式吧!

哈夫曼樹構造

初始給一個森林有n個節(jié)點。我們主要使用貪心的思想來完成哈夫曼樹的構造：

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

在具體實現(xiàn)上，找到最小兩個節(jié)點需要排序操作，我們來看看2，6，8，9，3權值節(jié)點構成哈夫曼樹的過程。

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

重復上面操作，這次結束 隊列中有11，8，9節(jié)點(排序后8，9，11)

圖片如果隊列為空，那么返回節(jié)點，并且這個節(jié)點為整個哈夫曼樹根節(jié)點root。

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

在計算帶權路徑長度WPL的時候，需要重新計算高度(從下往上)，因為哈夫曼樹是從下往上構造的，并沒有以常量維護高度，可以構造好然后計算高度。

具體代碼實現(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é)點
    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.

輸出結果:

 
 
 
 
    
  
  
  
  
  1. 61
    2.

哈夫曼編碼

除了哈夫曼樹你聽過，哈夫曼編碼你可能也聽過，但是不一定了解它是個什么玩意兒，哈夫曼編碼其實就是哈夫曼樹的一個非常重要的應用，在這里就簡單介紹原理并不詳細實現(xiàn)了。

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

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

aaaaaaaaaabbbbbcccdde

這個字符串來說，在計算機中如果每個字符都是定長存儲(假設長為4的二進制存儲)，計算機只知道0和1的二進制，假設

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

那么上面字符串可以用二進制存儲是這樣的

000100010001000100010001……0101

如果每個字符編碼等長，那么就沒有存儲空間優(yōu)化可言，都是單個字符長度 * 字符個數(shù)。但是如果每個字符編碼不等長，那么設計的開放性就很強了。

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

如果設計a為01，b設計為1。那么二進制就為：010101010111

如果設計a為1，b設計為01。那么二進制就為：111110101

如果設計a為1，b設計為0。那么二進制就為：1111100

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

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

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

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

結語

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


當前名稱：原以為哈夫曼樹、哈夫曼編碼很難，結果……
網(wǎng)頁地址：http://www.5511xx.com/article/cdodopd.html