1. 首頁 > 生活百科 > >

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

生活百科

3.5、數據壓縮小結將3.3與3.4中編寫的所有方法封裝成一個方法
//使用一個方法，將前面的方法封裝起來，便于我們的調用/** * @param bytes 原始的字符串對應的字節數組 * @return 是經過 赫夫曼編碼處理后的字節數組(壓縮后的數組) */private static byte[] huffmanZip(byte[] bytes){List<Node> nodes = getNodes(bytes);//根據nodes創建的赫夫曼樹Node huffmanTreeRoot = createHuffmanTree(nodes);//生成對應的赫夫曼編碼（根據赫夫曼樹）Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);//根據生成的赫夫曼編碼來對原始的字節數組進行壓縮byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);return huffmanCodeBytes;}

數據壓縮的所有代碼
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("原始的content字符串長度為："+contentBytes.length);//40byte[] huffmanCodesBytes = huffmanZip(contentBytes);System.out.println("對content字符串壓縮后的結果是："+Arrays.toString(huffmanCodesBytes));System.out.println("長度為："+huffmanCodesBytes.length);//17}//使用一個方法 ， 將前面的方法封裝起來，便于我們的調用/*** @param bytes 原始的字符串對應的字節數組* @return 是經過 赫夫曼編碼處理后的字節數組(壓縮后的數組)*/private static byte[] huffmanZip(byte[] bytes){List<Node> nodes = getNodes(bytes);//根據nodes創建的赫夫曼樹Node huffmanTreeRoot = createHuffmanTree(nodes);//生成對應的赫夫曼編碼（根據赫夫曼樹）Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);//根據生成的赫夫曼編碼來對原始的字節數組進行壓縮byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);return huffmanCodeBytes;}//編寫一個方法，將字符串對應的byte[] 數組，通過生成的赫夫曼編碼表，返回一個赫夫曼編碼 壓縮后的byte[]/**** @param bytes 這是原始的字符串對應的 byte[]* @param huffmanCodes 生成的赫夫曼編碼map* @return 返回赫夫曼編碼處理后的 byte[]* 舉例： String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();* 返回的是 字符串 "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100"* => 對應的 byte[] huffmanCodeBytes ， 即 8位對應一個 byte,放入到 huffmanCodeBytes* huffmanCodeBytes[0] =10101000(補碼) => byte[推導10101000=> 10101000 - 1 => 10100111(反碼)=> 11011000（原碼）= -88 ]* huffmanCodeBytes[1] = -88*/private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {//1.利用 huffmanCodes 將bytes 轉成赫夫曼編碼對應的字符串StringBuilder stringBuilder = new StringBuilder();//遍歷bytes 數組for(byte b: bytes) {stringBuilder.append(huffmanCodes.get(b));}//System.out.println("測試 stringBuilder~~~=" + stringBuilder.toString());//將 "1010100010111111110..." 轉成 byte[]//統計返回byte[] huffmanCodeBytes 長度//一句話 int len = (stringBuilder.length() + 7) / 8;int len;if(stringBuilder.length() % 8 == 0) {len = stringBuilder.length() / 8;} else {len = stringBuilder.length() / 8 + 1;}//創建 存儲壓縮后的 byte數組byte[] huffmanCodeBytes = new byte[len];int index = 0;//記錄是第幾個bytefor (int i = 0; i < stringBuilder.length(); i += 8) { //因為是每8位對應一個byte,所以步長 +8String strByte;if(i+8 > stringBuilder.length()) {//不夠8位strByte = stringBuilder.substring(i);}else{strByte = stringBuilder.substring(i, i + 8);}//將strByte 轉成一個byte,放入到 huffmanCodeByteshuffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);index++;}return huffmanCodeBytes;}//生成赫夫曼樹對應的赫夫曼編碼//思路://1. 將赫夫曼編碼表存放在 Map<Byte,String> 形式//生成的赫夫曼編碼表{32（空格）=01, 97（a）=100, 100(...)=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}static Map<Byte, String> huffmanCodes = new HashMap<Byte,String>();//2. 在生成赫夫曼編碼表示，需要去拼接路徑, 定義一個StringBuilder 存儲某個葉子結點的路徑static StringBuilder stringBuilder = new StringBuilder();//為了調用方便 ， 我們重載 getCodesprivate static Map<Byte, String> getCodes(Node root) {if(root == null) {return null;}//處理root的左子樹getCodes(root.left, "0", stringBuilder);//處理root的右子樹getCodes(root.right, "1", stringBuilder);return huffmanCodes;}/*** 功能：將傳入的node結點的所有葉子結點的赫夫曼編碼得到，并放入到huffmanCodes集合* @param node傳入結點* @param code路徑： 左子結點是 0, 右子結點 1* @param stringBuilder 用于拼接路徑*/private static void getCodes(Node node,String code,StringBuilder stringBuilder){StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);//將code加入到 stringBuilder2 （拼接路徑）stringBuilder2.append(code);if (node != null){//如果node等于空，不處理//判斷當前node是葉子節點還是非葉子結點if (node.data =https://www.huyubaike.com/biancheng/= null){//非葉子節點//遞歸處理//向左遞歸getCodes(node.left,"0", stringBuilder2);//向右遞歸getCodes(node.right, "1", stringBuilder2);}else {//進入到這里說明是葉子節點 ， 找到了最后huffmanCodes.put(node.data,stringBuilder2.toString());}}}//前序遍歷的方法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();}}}

推薦閱讀