1. 首頁 > 生活百科 > >

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

生活百科

數據壓縮的結果：

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

文章插圖
壓縮率：（40-17）/40=57.5%
3.6、使用赫夫曼編碼解碼（數據解壓）使用赫夫曼編碼來解碼數據，具體要求是
  1. 前面我們得到了赫夫曼編碼和對應的編碼byte[] , 即:[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
  2. 現在要求使用赫夫曼編碼 ，  進行解碼，又重新得到原來的字符串"i like like like java do you like a java"
在數據解壓的過程中我們需要兩個方法，一個是將壓縮后的結果轉為二進制的字符串，一個是對壓縮數據進行解碼
/** * 將一個byte 轉成一個二進制的字符串,這里需要利用二進制的原碼，反碼 ， 補碼 * @param b 傳入的 byte * @param flag 標志是否需要補高位如果是true，表示需要補高位，如果是false表示不補, 如果是最后一個字節 ， 無需補高位 * @return 是該b 對應的二進制的字符串，（注意是按補碼返回） */private static String byteToBitString(boolean flag, byte b) {//使用變量保存 bint temp = b; //將 b 轉成 int//如果是正數我們還存在補高位if(flag) {temp |= 256; //按位與 2561 0000 0000| 0000 0001 => 1 0000 0001}String str = Integer.toBinaryString(temp); //返回的是temp對應的二進制的補碼if(flag) {return str.substring(str.length() - 8);} else {return str;}}//編寫一個方法，完成對壓縮數據的解碼/** * * @param huffmanCodes 赫夫曼編碼表 map（key = value） * @param huffmanBytes 赫夫曼編碼得到的字節數組 * @return 就是原來的字符串對應的數組 */private static byte[] decode(Map<Byte,String> huffmanCodes, byte[] huffmanBytes) {//1. 先得到 huffmanBytes 對應的 二進制的字符串  ，  形式 1010100010111...StringBuilder stringBuilder = new StringBuilder();//將byte數組轉成二進制的字符串for(int i = 0; i < huffmanBytes.length; i++) {byte b = huffmanBytes[i];//判斷是不是最后一個字節boolean flag = (i == huffmanBytes.length - 1);stringBuilder.append(byteToBitString(!flag, b));}//把字符串按照指定的赫夫曼編碼進行解碼//把赫夫曼編碼表進行調換，因為反向查詢 a->100 100->aMap<String, Byte>map = new HashMap<String,Byte>();for(Map.Entry<Byte, String> entry: huffmanCodes.entrySet()) {map.put(entry.getValue(), entry.getKey());//key = value變成 value = https://www.huyubaike.com/biancheng/key}//創建要給集合，存放byteList list = new ArrayList<>();//i 可以理解成就是索引,掃描 stringBuilderfor(inti = 0; i < stringBuilder.length(); ) {int count = 1; // 小的計數器boolean flag = true;Byte b = null;while(flag) {//1010100010111...//遞增的取出 key 1(1，10,101...匹配)String key = stringBuilder.substring(i, i+count);//i 不動，讓count移動 ， 指定匹配到一個字符b = map.get(key);if(b == null) {//說明沒有匹配到count++;}else {//匹配到flag = false;}}list.add(b);i += count;//i 直接移動到 count}//當for循環結束后，我們list中就存放了所有的字符"i like like like java do you like a java"http://把list 中的數據放入到byte[] 并返回byte b[] = new byte[list.size()];for(int i = 0;i < b.length; i++) {b[i] = list.get(i);}return b;}測試
//解壓byte[] sourceBytes = decode(huffmanCodes, huffmanCodesBytes);System.out.println("(解壓后)原來的字符串="+new String(sourceBytes));
數據結構與算法【Java】08---樹結構的實際應用

文章插圖
3.6、文件壓縮我們學習了通過赫夫曼編碼對一個字符串進行編碼和解碼, 下面我們來完成對文件的壓縮和解壓， 具體要求：給你一個圖片文件，要求對其進行無損壓縮, 看看壓縮效果如何
思路：讀取文件-> 得到赫夫曼編碼表 -> 完成壓縮
首先我們創建一個圖片文件
數據結構與算法【Java】08---樹結構的實際應用

文章插圖
壓縮代碼
//編寫方法，將一個文件進行壓縮/** * * @param srcFile 你傳入的希望壓縮的文件的全路徑 * @param dstFile 我們壓縮后將壓縮文件放到哪個目錄 */public static void zipFile(String srcFile, String dstFile) {//創建輸出流OutputStream os = null;ObjectOutputStream oos = null;//創建文件的輸入流FileInputStream is = null;try {//創建文件的輸入流is = new FileInputStream(srcFile);//創建一個和源文件大小一樣的byte[]byte[] b = new byte[is.available()];//讀取文件is.read(b);//直接對源文件壓縮byte[] huffmanBytes = huffmanZip(b);//創建文件的輸出流, 存放壓縮文件os = new FileOutputStream(dstFile);//創建一個和文件輸出流關聯的ObjectOutputStreamoos = new ObjectOutputStream(os);//把 赫夫曼編碼后的字節數組寫入壓縮文件oos.writeObject(huffmanBytes);//這里我們以對象流的方式寫入 赫夫曼編碼，是為了以后我們恢復源文件時使用//注意一定要把赫夫曼編碼 寫入壓縮文件oos.writeObject(huffmanCodes);}catch (Exception e) {System.out.println(e.getMessage());}finally {try {is.close();oos.close();os.close();}catch (Exception e) {System.out.println(e.getMessage());}}}

推薦閱讀