赫夫曼樹 1 基本介紹 1) 給定 n 個權值作為 n 個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度(wpl)達到最小，稱這樣的二叉樹為 最優二叉樹，也稱為哈夫曼樹(Huffman Tree), 還有的書翻譯為霍夫曼樹， 2) 赫夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近 2 赫夫曼樹幾個重要概念和舉例說明 1) 路徑和路徑長度：在一棵樹中，從一個結點往下可以達到的孩子或孫子結點之間的通路，稱為路徑，通路 中分支的數目稱為路徑長度，若規定根結點的層數為 1，則從根結點到第 L 層結點的路徑長度為 L-1 2) 結點的權及帶權路徑長度：若將樹中結點賦給一個有著某種含義的數值，則這個數值稱為該結點的權，結 點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積 3) 樹的帶權路徑長度：樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為 WPL(weighted path length) ,權值越大的結點離根結點越近的二叉樹才是最優二叉樹， 4) WPL 最小的就是赫夫曼樹
3 赫夫曼樹創建思路圖解 給你一個數列 {13, 7, 8, 3, 29, 6, 1}，要求轉成一顆赫夫曼樹. ? 思路分析(示意圖)： {13, 7, 8, 3, 29, 6, 1} 構成赫夫曼樹的步驟： 1) 從小到大進行排序, 將每一個資料，每個資料都是一個節點 ， 每個節點可以看成是一顆最簡單的二叉樹 2) 取出根節點權值最小的兩顆二叉樹 3) 組成一顆新的二叉樹, 該新的二叉樹的根節點的權值是前面兩顆二叉樹根節點權值的和 4) 再將這顆新的二叉樹，以根節點的權值大小 再次排序， 不斷重復 1-2-3-4 的步驟，直到數列中，所有的數 據都被處理，就得到一顆赫夫曼樹 5) 圖解:
4 赫夫曼樹的代碼實作
package huffmanTree; import java.util.ArrayList; import java.util.Collections; public class HuffmanTree { public static void main(String[] args) { int[] arr = {13, 7, 8, 3, 29, 6, 1}; Node createHuffmanTree = createHuffmanTree(arr); preOrder(createHuffmanTree); } // 前序遍歷方法 public static void preOrder(Node root) { if(root != null) { root.preOrder(); } else { System.out.println("空樹！"); } } // 創建哈夫曼樹 public static Node createHuffmanTree(int[] arr) { // 1 遍歷arr陣列 // 2 將arr的每個元素構成一個Node // 3 將Node放入ArrayList ArrayList<Node> nodes = new ArrayList<Node>(); for (int value: arr) { nodes.add(new Node(value)); } while(nodes.size() > 1) { Collections.sort(nodes); // System.out.println(nodes.toString()); // 取出根節點權值最小的兩個二叉樹 Node leftNode = nodes.get(0); Node rightNode = nodes.get(1); // 構建新二叉樹 Node parent = new Node(leftNode.value + rightNode.value); parent.left = leftNode; parent.right = rightNode; // 洗掉處理過的節點 nodes.remove(leftNode); nodes.remove(rightNode); // parent加入List nodes.add(parent); // Collections.sort(nodes); // System.out.println(nodes.toString()); } // 回傳root return nodes.get(0); } } // 創建節點 class Node implements Comparable<Node>{ int value; Node left; Node right; public void preOrder() { System.out.println(this); if(this.left != null) { this.left.preOrder(); } if(this.right != null) { this.right.preOrder(); } } public Node(int value) { this.value =https://www.cnblogs.com/linzm14/p/ value; } @Override public String toString() { return "Node [value= "https://www.cnblogs.com/linzm14/p/+ value +"]"; } @Override public int compareTo(Node o) { return this.value - o.value; } }
赫夫曼編碼 1 基本介紹 1) 赫夫曼編碼也翻譯為 哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式, 屬于一種程式演算法 2) 赫夫曼編碼是赫哈夫曼樹在電訊通信中的經典的應用之一， 3) 赫夫曼編碼廣泛地用于資料檔案壓縮，其壓縮率通常在 20%～90%之間 4) 赫夫曼碼是可變字長編碼(VLC)的一種，Huffman 于 1952 年提出一種編碼方法，稱之為最佳編碼 2 原理剖析 ? 通信領域中資訊的處理方式 1-定長編碼
4) 根據赫夫曼樹，給各個字符,規定編碼 (前綴編碼)， 向左的路徑為 0 向右的路徑為 1 ， 編碼
如下:
o: 1000
u: 10010 d: 100110 y: 100111 i: 101
a : 110
k: 1110
e: 1111
j: 0000
v: 0001
l: 001
: 01
5) 按照上面的赫夫曼編碼，我們的"i like like like java do you like a java"
字串對應的編碼為 (注
意這里我們使用的無損壓縮)
10101001101111011110100110111101111010011011110111101000011000011100110011110000110
01111000100100100110111101111011100100001100001110 通過赫夫曼編碼處理 長度為 133
6） 長度為 ： 133
說明:
原來長度是 359 , 壓縮了 (359-133) / 359 = 62.9%
此編碼滿足前綴編碼, 即字符的編碼都不能是其他字符編碼的前綴，不會造成匹配的多義性
赫夫曼編碼是無損處理方案
注意事項
注意, 這個赫夫曼樹根據排序方法不同，也可能不太一樣，這樣對應的赫夫曼編碼也不完全一樣，但是 wpl 是
一樣的，都是最小的, 最后生成的赫夫曼編碼的長度是一樣，比如: 如果我們讓每次生成的新的二叉樹總是排在權
值相同的二叉樹的最后一個，則生成的二叉樹為:
3 最佳實踐-資料壓縮(創建赫夫曼樹) 將給出的一段文本，比如 "i like like like java do you like a java" ， 根據前面的講的赫夫曼編碼原理，對其進行數 據壓縮處理，形式如： "1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100 110111101111011100100001100001110 " 步驟 ：根據赫夫曼編碼壓縮資料的原理，需要創建 "i like like like java do you like a java" 對應的赫夫曼樹 思路：前面已經分析過了，而且我們已然講過了構建赫夫曼樹的具體實作， 代碼實作：
package com.lin.HuffmanCode_0314; import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; public class HuffmanCode { public static void main(String[] args) { String content = "i like like like java do you like a java"; byte[] contentBytes = content.getBytes(); System.out.println(contentBytes.length); // 40 List<Node> nodes = getNodes(contentBytes); System.out.println(nodes); // 創建哈夫曼樹 System.out.println("哈夫曼樹"); Node createHuffmanTree = createHuffmanTree(nodes); preOrder(createHuffmanTree); } /** * * @Description:生成赫夫曼樹對應的赫夫曼編碼<br> * 思路：將赫夫曼編碼存放在Map< * @author LinZM * @date 2021-3-14 21:09:30 * @version V1.8 */ // 前序遍歷 private static void preOrder(Node root){ if(root != null) { root.preOrder(); } else { System.out.println("空樹！"); } } /** * * @Description: * @author LinZM * @date 2021-3-14 20:45:23 * @version V1.8 * @param bytes接收位元組陣列 * @param */ private static List<Node> getNodes(byte[] bytes){ // 1 創建一個ArrayList ArrayList<Node> nodes= new ArrayList<Node>(); // 遍歷bytes，統計每一個byte出現的次數->map[key, value] Map<Byte, Integer> counts = new HashMap(); for(byte b: bytes) { Integer count = counts.get(b); // if(count == null) { // Map中還沒有這個字符資料, 第一次 counts.put(b, 1); } else { counts.put(b, count + 1); } } // 把每個鍵值對轉成一個Node物件， 并加入到nodes集合 for(Map.Entry<Byte, Integer> entry: counts.entrySet()) { nodes.add(new Node(entry.getKey(), entry.getValue())); } return nodes; } // 通過List創建赫夫曼樹 private static Node createHuffmanTree(List<Node> nodes) { while(nodes.size() > 1) { Collections.sort(nodes); Node leftNode = nodes.get(0); Node rightNode = nodes.get(1); Node parent = new Node(null, leftNode.weight + rightNode.weight); parent.left = leftNode; parent.right = rightNode; nodes.remove(leftNode); nodes.remove(rightNode); nodes.add(parent); } return nodes.get(0); } } class Node implements Comparable<Node>{ Byte data;// 存放資料本身 int weight; // 權值，字符出現的次數 Node left; Node right; public Node(Byte data, int weight) { this.data =https://www.cnblogs.com/linzm14/p/ data; this.weight = weight; } @Override public int compareTo(Node o) { // TODO Auto-generated method stub return this.weight - o.weight; } @Override public String toString() { return "Node [data = "https://www.cnblogs.com/linzm14/p/+ data +" weight= " + weight + "]"; } // 前序遍歷 public void preOrder() { System.out.println(this); if(this.left != null) { this.left.preOrder(); } if(this.right != null) { this.right.preOrder(); } } }
僅供參考，有錯誤還請指出！
有什么想法，評論區留言，互相指教指教，
覺得不錯的可以點一下右邊的推薦喲
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/270761.html
標籤：其他
上一篇：【資料結構與演算法】——鏈表（Linked List）
下一篇：演算法學習-整數反轉