1. 首頁 > 生活百科 > >

數據結構與算法【Java】08---樹結構的實際應用( 四 )

生活百科


文章插圖

  • 通信領域中信息的處理方式 3-赫夫曼編碼
1、傳輸的 字符串i like like like java do you like a java
2、d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各個字符對應的個數
3、按照上面字符出現的次數構建一顆赫夫曼樹, 次數作為權值構成赫夫曼樹的步驟：
  • 從小到大進行排序, 將每一個數據，每個數據都是一個節點 ， 每個節點可以看成是一顆最簡單的二叉樹
  • 取出根節點權值最小的兩顆二叉樹
  • 組成一顆新的二叉樹, 該新的二叉樹的根節點的權值是前面兩顆二叉樹根節點權值的和
  • 再將這顆新的二叉樹，以根節點的權值大小 再次排序，不斷重復 1-2-3-4 的步驟 ， 直到數列中，所有的數據都被處理，就得到一顆赫夫曼樹

數據結構與算法【Java】08---樹結構的實際應用

文章插圖
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" 字符串對應的編碼為 (注意這里我們使用的無損壓縮)
1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110
通過赫夫曼編碼處理 長度為 133,且不會有多義性
6、長度為 ： 133說明:原來長度是359 , 壓縮了 (359-133) / 359 = 62.9%
此編碼滿足前綴編碼, 即字符的編碼都不能是其他字符編碼的前綴 。不會造成匹配的多義性赫夫曼編碼是無損處理方案（可以完全恢復）
注：這個赫夫曼樹根據 排序方法不同，也可能不太一樣，這樣對應的 赫夫曼編碼也不完全一樣 ， 但是 wpl 是一樣的，都是最小的, 最后生成的赫夫曼編碼的長度是一樣，比如: 如果我們讓每次生成的新的二叉樹總是排在權值相同的二叉樹的最后一個，則生成的二叉樹如下圖，但是編碼長度是不會變的，還是133
數據結構與算法【Java】08---樹結構的實際應用

文章插圖
3.3、創建赫夫曼樹（數據壓縮）將給出的一段文本 ， 比如"i like like like java do you like a java"，根據前面的講的赫夫曼編碼原理，對其進行數據 壓 縮 處 理，形 式 如"1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100 110111101111011100100001100001110"
功能： 根據赫夫曼編碼壓縮數據的原理，需要創建 "i like like like java do you like a java" 對應的赫夫曼樹
思路:
(1) Node { data (存放數據)，weight (權值)， left和 right }(2) 得到 "i like like like java do you like a java"對應的 byte[] 數組(3)編寫一個方法，將準備構建赫夫曼樹的Node 節點放到 List, 形式 [Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......],體現 d:1 y:1 u:1 j:2v:2o:2l:4k:4e:4 i:5a:5:9(4) 可以通過List 創建對應的赫夫曼樹
代碼實現
import java.util.*;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);//40List<Node> nodes = getNodes(contentBytes);System.out.println("nodes="+nodes);//測試創建的二叉樹System.out.println("創建赫夫曼樹：");Node huffmanTreeRoot = createHuffmanTree(nodes);System.out.println("前序遍歷：");huffmanTreeRoot.preOrder();}//前序遍歷的方法public static void preOrder(Node root){if (root != null){root.preOrder();}else {System.out.println("赫夫曼樹為空");}}/**** @param bytes 接收字節數組* @return 返回的就是 List 形式[Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......],*/private static List<Node> getNodes(byte[] bytes){//1.創建一個ArrayListArrayList<Node> nodes = new ArrayList<>();//遍歷bytes,存儲每一個byte出現的次數=》map[key,value]HashMap<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集合//遍歷mapfor (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);//創建一棵新的二叉樹，它的根節點沒有data，只有權值Node parent = new Node(null, leftNode.weight+ rightNode.weight);parent.left = leftNode;parent.right = rightNode;//將已經處理的兩棵二叉樹從nodes刪除nodes.remove(leftNode);nodes.remove(rightNode);//將新的二叉樹加入到nodesnodes.add(parent);}//nodes 最后的節點就是赫夫曼樹的根節點return nodes.get(0);}}//創建Node,帶數據和權值class Node implements Comparable<Node>{Byte data;//存放數據本身a===>97 ascii碼int weight;//權值，表示字符出現的次數Node left;Node right;public Node(Byte data, int weight) {this.data = https://www.huyubaike.com/biancheng/data;this.weight = weight;}@Overridepublic int compareTo(Node o) {//從小到大排序return this.weight-o.weight;}public String toString() {return"Node [data = "https://www.huyubaike.com/biancheng/+ data +" weight=" + weight + "]";}//前序遍歷public void preOrder() {System.out.println(this);if(this.left != null) {this.left.preOrder();}if(this.right != null) {this.right.preOrder();}}}

推薦閱讀