哈夫曼樹和哈夫曼編碼的實作和應用執行個體(壓縮和解壓)

哈夫曼樹的實作和應用執行個體(壓縮檔案)

文章目錄

• 哈夫曼樹的實作和應用執行個體(壓縮檔案)
• • 哈夫曼樹
  • • 基本介紹
    • 名詞解釋
    • 如何建立
    • 圖解
    • 代碼實作
    • 測試
  • 哈夫曼編碼
  • • 基本介紹
    • 字首編碼
    • 哈夫曼編碼的應用執行個體——字元串的壓縮和壓縮
    • 測試
  • 檔案壓縮和解壓的執行個體
  • • 測試

哈夫曼樹

基本介紹

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

名詞解釋

• 路徑和路徑長度：在一棵樹中，從一個結點往下可以達到的孩子或孫子結點之間的通路，稱為路徑。通路中分支的數目稱為路徑長度。若規定根結點的層數為1，則從根結點到第L層結點的路徑長度為L-1
• 結點的權及帶權路徑長度：若将樹中結點賦給一個有着某種含義的數值，則這個數值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積
• 樹的帶權路徑長度：樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL(weighted path length) ,權值越大的結點離根結點越近的二叉樹才是最優二叉樹

如何建立

1. 将一個序列從小到大進行排序, 将每一個資料，每個資料都是一個節點 ， 每個節點可以看成是一顆最簡單的二叉樹
2. 取出根節點權值最小的兩顆二叉樹
3. 組成一顆新的二叉樹, 該新的二叉樹的根節點的權值是前面兩顆二叉樹根節點權值的和
4. 再将這顆新的二叉樹，以根節點的權值大小 再次排序與剩餘的待處理的根節點排序
5. 不斷重複 1-2-3-4 的步驟，直到數列中，所有的資料都被處理，此時數列中隻有一個節點，該節點就是得到一顆赫夫曼樹的根節點；

圖解

代碼實作

節點類Node

的建立

package edu.hebeu.huffman.tree;

/**
 * 實作Comparable接口，保證該類能夠通過Collections的sort()方法進行排序
 * @author 13651
 *
 */
public class Node implements Comparable<Node> {
	
	/**
	 * 左子節點
	 */
	private Node left;
	
	/**
	 * 右子節點
	 */
	private Node right;

	/**
	 * 該節點的權重
	 */
	private int weight;
	
	/**
	 * 構造器
	 * @param weight 目前節點的權重
	 */
	public Node(int weight) {
		this.weight = weight;
	}
	
	/**
	 * 實作Comparable接口的方法，決定該節點在Collection集合排序時是升序 還是 降序
	 */
	@Override
	public int compareTo(Node o) {
		// 表示從小到大排序
		return this.weight - o.weight;
		// 表示從大到小排序
//		return -(this.weight - o.weight);
	}
	
	/**
	 * 前序周遊
	 */
	public void preOrder() {
		System.out.println(this);
		if (left != null) {
			left.preOrder();
		}
		if (right != null) {
			right.preOrder();
		}
	}

	public Node getLeft() {
		return left;
	}

	public void setLeft(Node left) {
		this.left = left;
	}

	public Node getRight() {
		return right;
	}

	public void setRight(Node right) {
		this.right = right;
	}

	public int getWeight() {
		return weight;
	}

	public void setWeight(int weight) {
		this.weight = weight;
	}

	@Override
	public String toString() {
		return "Node [weight=" + weight + "]";
	}
	
}

           

哈夫曼樹類HuffmanTree

的建立

package edu.hebeu.huffman.tree;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 這個類用來建立哈夫曼樹
 * 基本介紹：
 	1. 給定n個權值作為n個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度(wpl)達到最小，稱這樣的二叉樹為最優二
 	叉樹，也稱為哈夫曼樹(Huffman Tree), 還有的書翻譯為霍夫曼樹
 	2. 赫夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近
 	
 * 幾個重要的概念：
 	1. 路徑和路徑長度：在一棵樹中，從一個結點往下可以達到的孩子或孫子結點之間的通路，稱為路徑。通路中分支的
 	數目稱為路徑長度。若規定根結點的層數為1，則從根結點到第L層結點的路徑長度為L-1；
 	2. 結點的權及帶權路徑長度：若将樹中結點賦給一個有着某種含義的數值，則這個數值稱為該結點的權。結點的帶權
 	路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積；
 	3. 樹的帶權路徑長度：樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL(weighted path length) ,
 	權值越大的結點離根結點越近的二叉樹才是最優二叉樹；
 	4. WPL最小的就是赫夫曼樹
 	
 * 構成哈夫曼樹的步驟：
 	1. 從小到大進行排序, 将每一個資料，每個資料都是一個節點 ， 每個節點可以看成是一顆最簡單的二叉樹
 	2. 取出根節點權值最小的兩顆二叉樹 
 	3. 組成一顆新的二叉樹, 該新的二叉樹的根節點的權值是前面兩顆二叉樹根節點權值的和
 	4. 再将這顆新的二叉樹，以根節點的權值大小 再次排序與剩餘的待處理的根節點排序
 	5. 不斷重複  1-2-3-4 的步驟，直到數列中，所有的資料都被處理，此時數列中隻有一個節點，該節點就是得到一
 	顆赫夫曼樹的根節點

 * @author 13651
 *
 */
public class HuffmanTree {
	
	/**
	 * 哈夫曼樹的根節點
	 */
	private Node root;
	
	/**
	 * 
	 * @param weights 進行建立哈夫曼樹使用的數組(數組内的元素對應的是節點的權重)
	 */
	public HuffmanTree(int[] weights) {
		if (weights.length <= 0) {
			System.err.println("請保證有節點來建立哈夫曼樹！");
			return;
		}
		root = createHufffmanTree(weights); // 擷取建立好的哈夫曼樹的根節點
	}
	
	/**
	 * 該方法用來建立哈夫曼樹
	 * @param weights 進行建立哈夫曼樹使用的數組(數組内的元素對應的是節點的權重)
	 * @return 傳回建立好後的哈夫曼數的根節點
	 */
	private static Node createHufffmanTree(int[] weights) {
		ArrayList<Node> weightList = new ArrayList<Node>();
		
		// TODO 通過數組的元素建立對應節點并加入到ArrayList集合中
		for (int weight : weights) {
			weightList.add(new Node(weight));
		}
		// TODO 當ArrayList中的元素大于一個(即還沒有建立好哈夫曼樹)
		while (weightList.size() > 1) {
			// TODO 先将目前的ArrayList集合内的元素排序
			Collections.sort(weightList);
			// TODO 取出最小和次小的元素節點
			Node minNode = weightList.get(0);
			Node subMinNode = weightList.get(1);
			// TODO 通過最小和次小元素節點建立新的節點，并将新的節點加入到ArrayList集合，然後将這兩個元素删除
			Node newNode = new Node(minNode.getWeight() + subMinNode.getWeight());
			newNode.setLeft(minNode);
			newNode.setRight(subMinNode);
			weightList.remove(minNode);
			weightList.remove(subMinNode);
			weightList.add(newNode);
			
//			System.out.println(weightList);
		}
		// TODO 程式執行到此，說明ArrayList集合中隻有一個元素(即此元素為建構的哈夫曼樹的根節點)
		return weightList.get(0);
	}
	
	/**
	 * 前序周遊哈夫曼樹
	 * @param root
	 */
	public void preOrder() {
		if (root == null) {
			System.err.println("哈夫曼樹為空！");
			return;
		}
		root.preOrder();
	}
	
}
           

測試類Test

的建立

package edu.hebeu.huffman.tree;

/**
 * 測試建立哈夫曼樹
 * @author 13651
 *
 */
public class Test {
	
	public static void main(String[] args) {
		int data[] = { 13, 7, 8, 3, 29, 6, 1, 5, 9, 9, 78, 56, 89, 102 };
		HuffmanTree huffmanTree = new HuffmanTree(data);
		System.out.println("-----------------------------");
		huffmanTree.preOrder();
	}
}

           

測試

哈夫曼編碼

基本介紹

• 是一種編碼方式, 屬于一種程式算法；
• 是哈夫曼樹在電訊通信中的經典的應用之一
• 廣泛地用于資料檔案壓縮。其壓縮率通常在20%～90%之間
• 是

  可變字長編碼(VLC)

  的一種

字首編碼

如一個編碼表如下：

a: 1

I:10

m: 0

t: 010

y: 01001

o: 01

n: 011

g: 001

: 111

如果我們此時發送一個

I am tyong

字元串，其對應的編碼就是：1011100100100101011001(

10

111

1

010

01001

01

011

001

)

我們如果在解碼時，會發現解析

10

、

0111

、…等編碼可能會出現歧義(

10

可能對應

1

(a)

(m)，也有可能是

10

(I)、…)，此時我們會發現會比對到重複的編碼，如果不加以處理就會導緻解碼出現了歧義，如果我們能避免上述的問題的編碼就是

字首編碼

，即不能比對到重複的編碼，哈夫曼編碼就是字首編碼，

是以處理哈夫曼編碼解析原資料會更加簡單(因為不存在重複比對問題，即比對到什麼，就是什麼)

如何建立哈夫曼編碼？

在建立好哈夫曼樹後，從根節點開始，每條路徑左0右1，會得到每個節點對應的哈夫曼編碼

如上述圖解的

1節點

對應的哈夫曼編碼就是

0010

，

5節點

就是

100

，

6節點

就是

101

，…；

哈夫曼編碼的應用執行個體——字元串的壓縮和壓縮

我們通過将一個字元串轉換為哈夫曼編碼的執行個體來體會哈夫曼編碼的應用；

一、如何通過字元串生成哈夫曼編碼？

分析：生成哈夫曼編碼一定需要對應的哈夫曼樹，而哈夫曼樹的建立依賴于各個節點的權重，那權重就必須能夠展現在節點上，是以我們這裡用

Byte

類型的周遊做為節點的權重，是以我們就可以将字元串轉換成位元組數組，位元組數組的每個元素就當作建構哈夫曼樹的初始節點，以這些節點夠成哈夫曼樹，

并且将來這些節點也一定在哈夫曼樹的葉子節點上

，由此得到哈夫曼樹的葉子節點(記憶體儲了位元組)對應的哈夫曼編碼(

即哈夫曼編碼表

)，完成字元串轉換成哈夫曼編碼

二、如何通過哈夫曼編碼轉換成其對應的位元組數組(壓縮)

分析：此時我們

周遊字元串對應的位元組數組

，将每個元素(位元組)通過查詢哈夫曼編碼表得到其對應的哈夫曼編碼，然後将依次進行拼接，此時我們就得到了字元串通過哈夫曼編碼處理後的01串，然後将這些01串

每8位做為一個二進制的數進行轉換為10進制的

，這裡有個小細節(

因為位數可能不是8的位數，就導緻了再後序的解壓時最後一組01串在前後有0時可能出現缺失，是以我們将直接最後一位儲存起來，再解壓時直接與其最後一組進行替換來保證編碼的完整性

)，此時得到的

10進制位我們将其做為一個byte類型的資料(即位元組)

，然後将它們依次儲存到一個位元組數組中，此數組就是壓縮之後的數組(因為此時數組内的位元組明顯比原先的少了

三、如何将壓縮後的位元組數組解壓為字元串

分析：我們可以通過每個位元組擷取其對應的二進制數(

細節：對應每一個得到的二進制字元，我們應該将其與256進行按位或(因為如果是負數，得到的就是其補碼，我們就需要截取後8位；如果是正數，我們可能還需要進行補位操作！)

，當是擷取最後一個位元組的二進制編碼時，我們直接将上一步儲存的的最後一組字元串指派給它(省去了判斷是否補0，補幾個0的麻煩操作))，此時就得到了一長串的01，

它的每幾位就是哈夫曼表中的VALUE

，我們可以通過查詢哈夫曼編碼表，依次得到位元組，然後将它們儲存到一個位元組數組中，該數組就是字元串對應的位元組數組，然後通過

new String(byte[] bytes)

方法就可以得到原先的字元串，此時就完成了解壓

代碼實作：

我們建立一個

節點類Node

package edu.hebeu.huffman.code;

public class Node implements Comparable<Node>{
	
	/**
	 * 存放每個字元對應的ASCII碼
	 */
	private Byte data;
	
	/**
	 * 左子節點
	 */
	private Node left;
	
	/**
	 * 右子節點
	 */
	private Node right;
	
	/**
	 * 該節點的權重(這裡對應的就是data在壓縮的字元串中出現的次數)
	 */
	private int weight;
	
	public Node(Byte data, int weight) {
		this.data = data;
		this.weight = weight;
	}
	
	/**
	 * 前序周遊節點
	 */
	public void preOrder() {
		System.out.println(this);
		if (left != null) {
			left.preOrder();
		}
		if (right != null) {
			right.preOrder();
		}
	}

	public Byte getData() {
		return data;
	}

	public void setData(Byte data) {
		this.data = data;
	}

	public Node getLeft() {
		return left;
	}

	public void setLeft(Node left) {
		this.left = left;
	}

	public Node getRight() {
		return right;
	}

	public void setRight(Node right) {
		this.right = right;
	}

	public int getWeight() {
		return weight;
	}

	public void setWeight(int weight) {
		this.weight = weight;
	}

	@Override
	public String toString() {
		return "Node [data=" + data + ", weight=" + weight + "]";
	}

	@Override
	public int compareTo(Node o) {
		// TODO 表示Node對象升序排列
		return weight - o.weight;
	}
	
}

           

建立

哈夫曼樹類HuffmanTreeCompress

完成字元串的壓縮和解壓

package edu.hebeu.huffman.code;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 哈夫曼編碼：
 * 	是一種編碼方式, 屬于一種程式算法
 * 	是哈夫曼樹在電訊通信中的經典的應用之一
 * 	廣泛地用于資料檔案壓縮。其壓縮率通常在20%～90%之間
 * 	是可變字長編碼(VLC)的一種
 * 
 * 該類是哈夫曼編碼的應用：完成資料的壓縮和解壓
 * @author 13651
 *
 */
public class HuffmanTreeCompress {
	
	/**
	 * 哈夫曼樹的根節點
	 */
	private static Node ROOT;
	
	/**
	 * 哈夫曼樹的編碼表
	 */
	private static Map<Byte, String> HUFFMAN_CODES_TABLE;
	
	/**
	 * 用來記錄 壓縮後的最後一個位元組對應的 二進制編碼
	 */
	private static String LAST_CODE;
	
	/**
	 * 私有化構造器
	 */
	private HuffmanTreeCompress() {}
	
	/**
	 * 外部調用的壓縮方法
	 * @param content待壓縮的字元串
	 * @return 壓縮字元串完成的位元組數組
	 */
	public static byte[] zip(String content) {
		long start = System.currentTimeMillis();
		if ("".equals(content)) {
			System.err.println("請保證有内容！");
			return null;
		}
		byte[] contentBytes = content.getBytes(); // 擷取待壓縮字元串的位元組數組
		// 擷取壓縮的字元串的位元組數組中的每個元素 生成Node節點的List集合
		List<Node> nodes = getNodeList(contentBytes);
		// 建立通過上面的Node節點集合生成哈夫曼樹
		ROOT =  createHuffmanTree(nodes);
		// 生成該哈夫曼樹的哈夫曼編碼表
		generateHuffmanCodeTable();
		// 進行壓縮
		byte[] zipContentBytes = huffmanZip(contentBytes);
		
		System.out.println("壓縮前：" + contentBytes.length + "位元組，壓縮後：" +
		zipContentBytes.length + "位元組，壓縮時間：" + (System.currentTimeMillis() - start) + "ms，壓縮率：" + 
		((((float) contentBytes.length - zipContentBytes.length) / contentBytes.length) * 100) + "%");
		return zipContentBytes;
	}
	
	/**
	 * 實際的壓縮方法
	 * @param contentBytes 待壓縮字元串的位元組數組
	 * @return 将字元串對應對應的位元組數組 通過哈夫曼編碼 壓縮為對應的位元組數組
	 */
	private static byte[] huffmanZip(byte[] contentBytes) {
		// TODO 利用哈夫曼編碼表生成待壓縮字元串的位元組數組 對應的哈夫曼字元串(100110010.... 、0100110011001111...)
		StringBuilder contentHuffman = new StringBuilder();
		for (byte contentByte : contentBytes) {
			contentHuffman.append(HUFFMAN_CODES_TABLE.get(contentByte));
		}
		System.out.println("zip：" + contentHuffman + "; length = " + contentHuffman.length());
		// TODO 将上面擷取到的哈夫曼字元串(01串)每8位對應一個byte進行轉換
		int zipByteCount = 0; // 儲存上面擷取到的哈夫曼字元串 能轉換成多少個 byte
		if (contentHuffman.length() % 8 == 0) { // 如果正好8的倍數
			zipByteCount = contentHuffman.length() / 8; // 讓壓縮後的byte位元組個數為 除8
		} else { // 否則，即不是8的倍數
			zipByteCount = contentHuffman.length() / 8 + 1; // 讓壓縮後的byte位元組個數為 除8再加1
		}
		byte[] zipContentBytes = new byte[zipByteCount]; //建立zipByteCount長度的位元組數組來存放壓縮後的位元組
		int index = 0; // 記錄目前是zipContentBytes位元組數組的第幾個元素
		for (int i = 0; i < contentHuffman.length(); i = i + 8) { // 因為每8位哈夫曼字元串(01串) 對應一個byte，是以步長為8
			String subContentHuffman;
			if (contentHuffman.length() < i + 8) { // 如果此時的要截取的哈夫曼字元串長度不夠8位
				subContentHuffman = contentHuffman.substring(i); // 截取目前位後面的全部字元
			} else { // 否則，即夠8位
				subContentHuffman = contentHuffman.substring(i, i + 8); // 每次截取目前位後面的8個字元
			}
//			System.out.print("$" + (byte) Integer.parseInt(subContentHuffman, 2) + ", --" + subContentHuffman + "\n");
			zipContentBytes[index] = (byte) Integer.parseInt(subContentHuffman, 2); // 将截取到的字元串(01串)通過2進制 轉換為Integer數字(10進制)，然後将該數字做為byte加入到壓縮的位元組數組中
			
			if (contentHuffman.length() < i + 8) { // 如果此時為最後一次循環(即最後一個位元組對應的哈夫曼編碼)
//				System.err.println("--------------------------");
				LAST_CODE= subContentHuffman; // 儲存壓縮後的最後一個位元組對應的哈夫曼編碼(最後一個位元組的編碼可能會出現0位不足，這裡我們直接儲存，待解壓縮時與解壓縮的最後一個位元組的哈夫曼編碼進行替換)
			}
			index++;
		} // System.out.println();
		// 将壓縮後的位元組數組傳回
		return zipContentBytes;
	}
	
	/**
	 * 外部調用的解壓方法
	 * @param zipBytes 需要解壓的位元組數組
	 * @return 解壓後的字元串
	 */
	public static String unzip(byte[] zipBytes) {
		long start = System.currentTimeMillis();
		if (zipBytes == null || zipBytes.length <= 0) {
			System.err.println("沒有解壓的資料！");
			return null;
		}
		String content = new String(huffmanUnzip(zipBytes));
		System.out.println("解壓時間：" + (System.currentTimeMillis() - start) + "ms");
		return content; // 進行解壓并傳回
	}
	
	/**
	 * 實際的解壓方法
	 * @param zipBytes 待解壓的位元組數組
	 * @return 解壓後的位元組數組
	 */
	private static byte[] huffmanUnzip(byte[] zipBytes) {
		StringBuilder contentHuffman = new StringBuilder(); // 用來存放經過壓縮的位元組數組 生成的哈夫曼字元串(100110010.... 、0100110011001111...)
		for (int i = 0; i < zipBytes.length; i++) {
			// 表示擷取位元組數組中目前元素對應的二進制字元串(除去位元組數組的最後一個元素，其他的元素都需要進行補位操作)；然後将該串拼接到contentHuffman
			contentHuffman.append(byteToBitStr(!(i == zipBytes.length - 1), zipBytes[i]));
		}
		System.out.println("unzip：" + contentHuffman + "; length：" + contentHuffman.length());
		// 存放反轉後的哈夫曼編碼表(友善下面 使用哈夫曼字元串 通過哈夫曼編碼表 轉換成對應的(原始的，壓縮之前的)位元組數組)
		Map<String, Byte> reverseHuffmanCodeTable = new HashMap<>();
		for (Map.Entry<Byte, String> entry : HUFFMAN_CODES_TABLE.entrySet()) {
			reverseHuffmanCodeTable.put(entry.getValue(), entry.getKey());
		}
		// 存放轉換之後解壓的位元組數組轉換之後(解壓)的位元組
		List<Byte> list = new ArrayList<>();
		for (int codeStart = 0; codeStart < contentHuffman.length();) {
			int codeEnd = 1; // 辨別目前到掃描的二進制串的位置
			boolean isByte = false; // 辨別目前掃描到的二進制串(i到j)
			Byte b = null; // 存放目前解析到的位元組
			while(!isByte) {
				// 取出codeStart位置到codeEnd位置的二進制串的一個子串
//				System.out.println("codeStart = " + codeStart + "; codeEnd = " + codeEnd);
				
				String byteKey = null;
				
				byteKey = contentHuffman.substring(codeStart, codeStart + codeEnd);
				b = reverseHuffmanCodeTable.get(byteKey); // 通過截取到的子串擷取其對應的Byte
				if (b != null) { // 如果不為空，即找到了該字串對應位元組
					isByte = true;
				} else {
					codeEnd++;
				}
			}
			// 程式執行到此，說明已經找到了一個位元組
			list.add(b); // 将該位元組加入到list
			codeStart += codeEnd; // 直接讓起始的掃描位置移動到結束的掃描位置
		}
		
		// 程式執行到此，list集合中就存放了解壓之後的所有位元組了，此時我們應該将它們取出來放到位元組數組中
		byte[] contentBytes = new byte[list.size()];
		for (int i = 0; i < contentBytes.length; i++) {
			contentBytes[i] = list.get(i);
		}
		return contentBytes;
	}
	
	/**
	 * 該方法用來将一個byte轉換成 位字元串(01串)，
	 * 需要注意：
	 * 	如果byte是負數，在轉換成int後，那麼轉換成的 位字元串就是其對應的補碼；
	 * 	如果byte是正數，在轉換成int後，那麼轉換成的 位字元串就是其對應的原碼，此時我們還有可能需要進行補位；
	 * @param isRepair 是否需要補高位
	 * @param b 進行轉換的byte值
	 * @return 轉換後的二進制字元串
	 */
	private static String byteToBitStr(boolean isRepair, byte b) {
		int tmp = b; // 将byte轉換成int
		String binaryStr; // 存放轉換之後的二進制字元串
		if (isRepair) { // 如果需要進行補位 或者 為正數 時就進行補位
			tmp |= 256; // 進行 按位或操作，如 2對應的二進制就是 00000010，按位或256(256的二進制為100000000)，即 00000010 | 10000000 = 100000010
			binaryStr = Integer.toBinaryString(tmp); // 轉換為二進制字元串
//			System.out.println("binaryStr = " + binaryStr.substring(binaryStr.length() - 8));
			return binaryStr.substring(binaryStr.length() - 8); // 從第8位截取全部二進制字元串并傳回
		}
		// 程式執行到此，說明不需要補位(即是最後一位位元組的哈夫曼編碼)
		binaryStr = Integer.toBinaryString(tmp); // 轉換二進制字元串
//		System.out.println("1------" + binaryStr);
		binaryStr = LAST_CODE; // 将壓縮過程中儲存的最後一位位元組對應的哈夫曼編碼直接 指派給該變量(不用進行判斷是否添0)
//		System.out.println("2------" + binaryStr);
		return binaryStr; // 将整個二進制字元串傳回
	}
	
	/**
	 * 通過傳入的位元組數組将其轉換成對應Node節點集合
	 * @param bs 位元組數組
	 * @return 将位元組數組每個元素轉換成Node的List集合
	 */
	private static List<Node> getNodeList(byte[] bs) {
		
		// 存儲壓縮資訊對應的byte數組中每個元素對應的節點
		List<Node> nodes = new ArrayList<Node>();;
		
		// 這個Map用來存儲統計每個byte位元組出現的次數
		Map<Byte, Integer> tmpMap = new HashMap<Byte, Integer>();
		for (byte b : bs) {
			if (tmpMap.get(b) == null) { // 如果該位元組沒有在tmpMap，即第一次出現該位元組
				tmpMap.put(b, 1); // 将這個Byte位元組加入到Map
			} else { // 否則，即該位元組在tmpMap中已經存在(即已經至少出現了一次)
				Integer count = tmpMap.get(b); // 擷取該位元組在Map中的Value(即出現的次數)
				tmpMap.put(b, count + 1); // 将該位元組的值+1
			}
		}
		
		// 将上面的Map中的資訊轉換成Node并加入到nodes中
		for (Map.Entry<Byte, Integer> node : tmpMap.entrySet()) {
			nodes.add(new Node(node.getKey(), node.getValue())); // 将該KEY, VALUE對轉換成Node并添加到nodes中
		}
		return nodes;
	}
	
	/**
	 * 建立哈夫曼樹的方法
	 * @return
	 */
	private static Node createHuffmanTree(List<Node> nodes) {
		// 當nodes中的元素大于1，即哈夫曼樹還沒有建構完畢
		while (nodes.size() > 1) {
			// TODO 将nodes内的元素排序(有Node類實作Compareable接口，可以看出是從小到大排序的)
			Collections.sort(nodes);
			// TODO 取出最小和次小的元素節點
			Node minNode = nodes.get(0);
			Node subMinNode = nodes.get(1);
			// TODO 通過最小和次小元素節點建立新的節點，并将新的節點加入到ArrayList集合，然後将這兩個元素删除
			Node newNode = new Node(null, minNode.getWeight() + subMinNode.getWeight());
			newNode.setLeft(minNode);
			newNode.setRight(subMinNode);
			nodes.remove(minNode);
			nodes.remove(subMinNode);
			nodes.add(newNode);
		}
		
		return nodes.get(0); // 将nodes中的0索引位置的元素(此時一定有且僅有這一個元素了)傳回
	}
	
	/**
	 * 生成哈夫曼編碼表
	 */
	private static void generateHuffmanCodeTable() {
		if (ROOT == null) {
			System.err.println("root節點為空，生成哈夫曼編碼表失敗！");
			return;
		}
		// 執行個體化存儲哈夫曼編碼的編碼表
		HUFFMAN_CODES_TABLE = new HashMap<Byte, String>();
		// 處理root的左子樹
		generateHuffmanCodeTable(ROOT.getLeft(), "0", new StringBuilder());
//		// 處理root的右子樹
		generateHuffmanCodeTable(ROOT.getRight(), "1", new StringBuilder());
		// {32=100, 97=101, 33=1100, 101=1101, 118=1110, 105=000, 73=1111, 74=001, 107=010, 108=011}
		// 或者直接寫成如下方式
//		generateHuffmanCodeTable(root, "", new StringBuilder());
		// {32=100, 97=101, 33=1100, 101=1101, 118=1110, 105=000, 73=1111, 74=001, 107=010, 108=011}
	}
	
	/**
	 * 生成哈夫曼表的方法，通過分析，傳入的字元串對應的所有節點一定是哈夫曼樹的葉子節點
	 * @param node 目前節點
	 * @param path 路徑(左0右1)
	 * @param codeItem 用來拼接目前節點的上一條路徑path，來生成相應葉子節點的哈夫曼編碼
	 */
	private static void generateHuffmanCodeTable(Node node, String path, StringBuilder codeItem) {
		StringBuilder code = new StringBuilder(codeItem); // 接收傳來的codeItem
		code.append(path); // 将path路徑拼接到code上
		if (node != null) {
			if (node.getData() == null) { // 如果node的data為空，即該節點為非葉子節點(因為在建立哈夫曼樹時，我們隻有通過Byte位元組生成的Node才有data，其他的節點data都為null)
				// 向左遞歸
				generateHuffmanCodeTable(node.getLeft(), "0", code);
				// 向右遞歸
				generateHuffmanCodeTable(node.getRight(), "1", code);
			} else { // 否則即node的data不為空，該節點為葉子節點
				HUFFMAN_CODES_TABLE.put(node.getData(), code.toString()); // 将該節點的data(即Byte)和其對應的編碼code存入哈夫曼編碼表
			}
		}
	}

	public static Node getRoot() {
		return ROOT;
	}

	public static Map<Byte, String> getCodeTable() {
		return HUFFMAN_CODES_TABLE;
	}
	
}
           

測試類的編寫

public class Test {
	public static void main(String[] args) {
		String content = "你好，哈夫曼編碼";
		byte[] zipContentBytes = HuffmanTreeCompress.zip(content);
		
		System.out.println("原始位元組數組：" + Arrays.toString(content.getBytes()));
		System.out.println("壓縮後的位元組數組：" + Arrays.toString(zipContentBytes));
		
		System.out.println("解壓之後：" + HuffmanTreeCompress.unzip(zipContentBytes));
	}
}
           

測試

檔案壓縮和解壓的執行個體

通過上面的執行個體，我們已經看到裡哈夫曼編碼的強大之處，那麼如何進行檔案的壓縮呢？無非就是：

壓縮時：将

待壓縮的檔案通過位元組輸入流讀入

，将

壓縮後的内容和其對應的哈夫曼表以及最後一組01串通過對象輸出流輸出(序列化)

解壓時将

待解壓的檔案通過對象輸入流讀入(反序列化)

，得到

待解壓檔案的位元組數組、哈夫曼編碼表、最後一組01串得到，然後将其解壓後的内容通過位元組輸出流輸出

我們在上面的類上進行改寫，

Node節點類不變

，隻改變

HuffmanTreeCompress類

實作檔案壓縮和解壓的執行個體，如下：

package edu.hebeu.huffman.code;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 哈夫曼編碼：
 * 	是一種編碼方式, 屬于一種程式算法
 * 	是哈夫曼樹在電訊通信中的經典的應用之一
 * 	廣泛地用于資料檔案壓縮。其壓縮率通常在20%～90%之間
 * 	是可變字長編碼(VLC)的一種
 * 
 * 該類是哈夫曼編碼的應用：完成資料的壓縮和解壓
 * @author 13651
 *
 */
public class HuffmanTreeCompress {
	
	/**
	 * 哈夫曼樹的根節點
	 */
	private static Node ROOT;
	
	/**
	 * 哈夫曼樹的編碼表
	 */
	private static Map<Byte, String> HUFFMAN_CODES_TABLE;
	
	/**
	 * 用來記錄 壓縮後的最後一個位元組對應的 二進制編碼
	 */
	private static String LAST_CODE;
	
	/**
	 * 私有化構造器
	 */
	private HuffmanTreeCompress() {}
	
	/**
	 * 外部調用的壓縮方法
	 * @param content待壓縮的字元串
	 * @return 壓縮字元串完成的位元組數組
	 */
	public static byte[] zip(String content) {
		long start = System.currentTimeMillis();
		if ("".equals(content)) {
			System.err.println("請保證有内容！");
			return null;
		}
		byte[] contentBytes = content.getBytes(); // 擷取待壓縮字元串的位元組數組
		// 擷取壓縮的字元串的位元組數組中的每個元素 生成Node節點的List集合
		List<Node> nodes = getNodeList(contentBytes);
		// 建立通過上面的Node節點集合生成哈夫曼樹
		ROOT =  createHuffmanTree(nodes);
		// 生成該哈夫曼樹的哈夫曼編碼表
		generateHuffmanCodeTable();
		// 進行壓縮
		byte[] zipContentBytes = huffmanZip(contentBytes);
		
		System.out.println("壓縮前：" + contentBytes.length + "位元組，壓縮後：" +
		zipContentBytes.length + "位元組，壓縮時間：" + (System.currentTimeMillis() - start) + "ms，壓縮率：" + 
		((((float) contentBytes.length - zipContentBytes.length) / contentBytes.length) * 100) + "%");
		return zipContentBytes;
	}
	
	/**
	 * 壓縮檔案的方法
	 * @param sourcePath 壓縮的檔案路徑
	 * @param targetFile 壓縮後的檔案存儲路徑
	 */
	public static void zipFile(String sourcePath, String targetFile) {
		long start = System.currentTimeMillis();
		
		FileInputStream fis = null;
		FileOutputStream fos = null;
		ObjectOutputStream oos = null;
		
		try {
			fis = new FileInputStream(sourcePath);
			byte[] sourceFileBytes = new byte[fis.available()];
			fis.read(sourceFileBytes); // 将源檔案讀取到sourceFileBytes位元組數組中
//			System.out.println("--" + Arrays.toString(sourceFileBytes));
			
			// 擷取壓縮的檔案對應的位元組數組中的每個元素 生成Node節點的List集合
			List<Node> nodes = getNodeList(sourceFileBytes);
			// 建立通過上面的Node節點集合生成哈夫曼樹
			ROOT =  createHuffmanTree(nodes);
			// 生成該哈夫曼樹的哈夫曼編碼表
			generateHuffmanCodeTable();
			
			// 進行壓縮
			byte[] zipFileBytes = huffmanZip(sourceFileBytes);
			fos = new FileOutputStream(targetFile); // 檔案輸出流對象，将檔案輸出到targetFile
			// 将壓縮的檔案進行序列化
			oos = new ObjectOutputStream(fos);
			oos.writeObject(zipFileBytes); // 将壓縮後的檔案位元組數組序列化
			oos.writeObject(HUFFMAN_CODES_TABLE); // 将該檔案壓縮和解壓需要的哈夫曼表序列化
			oos.writeObject(LAST_CODE); // 将壓縮的位元組數組 的最後一個原始對應的二進制編碼值序列化
			
			System.out.println("壓縮前：" + sourceFileBytes.length + "位元組，壓縮後：" +
					zipFileBytes.length + "位元組，壓縮時間：" + (System.currentTimeMillis() - start) + "ms，壓縮率：" + 
					((((float) sourceFileBytes.length - zipFileBytes.length) / sourceFileBytes.length) * 100) + "%");
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} finally {
			if (fis != null) {
				try {
					fis.close();
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			if (fos != null) {
				try {
					fos.close();
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			if (oos != null) {
				try {
					oos.close();
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
		}
	}
	
	/**
	 * 實際的壓縮方法
	 * @param contentBytes 待壓縮字元串的位元組數組
	 * @return 将字元串對應對應的位元組數組 通過哈夫曼編碼 壓縮為對應的位元組數組
	 */
	private static byte[] huffmanZip(byte[] contentBytes) {
		// TODO 利用哈夫曼編碼表生成待壓縮字元串的位元組數組 對應的哈夫曼字元串(100110010.... 、0100110011001111...)
		StringBuilder contentHuffman = new StringBuilder();
		for (byte contentByte : contentBytes) {
			contentHuffman.append(HUFFMAN_CODES_TABLE.get(contentByte));
		}
//		System.out.println("zip：" + contentHuffman + "; length = " + contentHuffman.length());
		// TODO 将上面擷取到的哈夫曼字元串(01串)每8位對應一個byte進行轉換
		int zipByteCount = 0; // 儲存上面擷取到的哈夫曼字元串 能轉換成多少個 byte
		if (contentHuffman.length() % 8 == 0) { // 如果正好8的倍數
			zipByteCount = contentHuffman.length() / 8; // 讓壓縮後的byte位元組個數為 除8
		} else { // 否則，即不是8的倍數
			zipByteCount = contentHuffman.length() / 8 + 1; // 讓壓縮後的byte位元組個數為 除8再加1
		}
		byte[] zipContentBytes = new byte[zipByteCount]; //建立zipByteCount長度的位元組數組來存放壓縮後的位元組
		int index = 0; // 記錄目前是zipContentBytes位元組數組的第幾個元素
		for (int i = 0; i < contentHuffman.length(); i = i + 8) { // 因為每8位哈夫曼字元串(01串) 對應一個byte，是以步長為8
			String subContentHuffman;
			if (contentHuffman.length() < i + 8) { // 如果此時的要截取的哈夫曼字元串長度不夠8位
				subContentHuffman = contentHuffman.substring(i); // 截取目前位後面的全部字元
			} else { // 否則，即夠8位
				subContentHuffman = contentHuffman.substring(i, i + 8); // 每次截取目前位後面的8個字元
			}
//			System.out.print("$" + (byte) Integer.parseInt(subContentHuffman, 2) + ", --" + subContentHuffman + "\n");
			zipContentBytes[index] = (byte) Integer.parseInt(subContentHuffman, 2); // 将截取到的字元串(01串)通過2進制 轉換為Integer數字(10進制)，然後将該數字做為byte加入到壓縮的位元組數組中
			
			if (contentHuffman.length() < i + 8) { // 如果此時為最後一次循環(即最後一個位元組對應的哈夫曼編碼)
//				System.err.println("--------------------------");
				LAST_CODE= subContentHuffman; // 儲存壓縮後的最後一個位元組對應的哈夫曼編碼(最後一個位元組的編碼可能會出現0位不足，這裡我們直接儲存，待解壓縮時與解壓縮的最後一個位元組的哈夫曼編碼進行替換)
			}
			index++;
		} // System.out.println();
		// 将壓縮後的位元組數組傳回
		return zipContentBytes;
	}
	
	/**
	 * 外部調用的解壓方法
	 * @param zipBytes 需要解壓的位元組數組
	 * @return 解壓後的字元串
	 */
	public static String unzip(byte[] zipBytes) {
		long start = System.currentTimeMillis();
		if (zipBytes == null || zipBytes.length <= 0) {
			System.err.println("沒有解壓的資料！");
			return null;
		}
		String content = new String(huffmanUnzip(zipBytes));
		System.out.println("解壓時間：" + (System.currentTimeMillis() - start) + "ms");
		return content; // 進行解壓并傳回
	}
	
	/**
	 * 進行解壓檔案的方法
	 * @param sourceFile 源檔案路徑(待壓縮檔案路徑)
	 * @param targetFile 目标檔案路徑(壓縮到哪個路徑)
	 */
	public static void UnzipFile(String sourceFile, String targetFile) {
		long start = System.currentTimeMillis();
		
		FileInputStream fis = null;
		FileOutputStream fos = null;
		ObjectInputStream ois = null;
		
		try {
			fis = new FileInputStream(sourceFile);
			ois = new ObjectInputStream(fis);
			
			byte[] zipBytes = (byte[]) ois.readObject(); // 反序列化得到壓縮的位元組數組
			HUFFMAN_CODES_TABLE = (Map<Byte, String>) ois.readObject(); // 反序列化得到哈夫曼編碼表
			LAST_CODE = (String) ois.readObject(); // 反序列化得到壓縮的位元組數組中最後一個元素對應的二進制編碼串
			
			// 進行解壓
			byte[] contentBytes = huffmanUnzip(zipBytes);
			
			fos = new FileOutputStream(targetFile);
			fos.write(contentBytes); // 将解壓得到的位元組流寫到指定位置
			System.out.println("解壓時間：" + (System.currentTimeMillis() - start) + "ms");
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (ClassNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} finally {
			if (fis != null) {
				try {
					fis.close();
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			if (fos != null) {
				try {
					fos.close();
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			if (ois != null) {
				try {
					ois.close();
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
		}
	}
	
	/**
	 * 實際的解壓方法
	 * @param zipBytes 待解壓的位元組數組
	 * @return 解壓後的位元組數組
	 */
	private static byte[] huffmanUnzip(byte[] zipBytes) {
		StringBuilder contentHuffman = new StringBuilder(); // 用來存放經過壓縮的位元組數組 生成的哈夫曼字元串(100110010.... 、0100110011001111...)
		for (int i = 0; i < zipBytes.length; i++) {
			// 表示擷取位元組數組中目前元素對應的二進制字元串(除去位元組數組的最後一個元素，其他的元素都需要進行補位操作)；然後将該串拼接到contentHuffman
			contentHuffman.append(byteToBitStr(!(i == zipBytes.length - 1), zipBytes[i]));
		}
//		System.out.println("unzip：" + contentHuffman + "; length：" + contentHuffman.length());
		// 存放反轉後的哈夫曼編碼表(友善下面 使用哈夫曼字元串 通過哈夫曼編碼表 轉換成對應的(原始的，壓縮之前的)位元組數組)
		Map<String, Byte> reverseHuffmanCodeTable = new HashMap<>();
		for (Map.Entry<Byte, String> entry : HUFFMAN_CODES_TABLE.entrySet()) {
			reverseHuffmanCodeTable.put(entry.getValue(), entry.getKey());
		}
		// 存放轉換之後解壓的位元組數組轉換之後(解壓)的位元組
		List<Byte> list = new ArrayList<>();
		for (int codeStart = 0; codeStart < contentHuffman.length();) {
			int codeEnd = 1; // 辨別目前到掃描的二進制串的位置
			boolean isByte = false; // 辨別目前掃描到的二進制串(i到j)
			Byte b = null; // 存放目前解析到的位元組
			while(!isByte) {
				// 取出codeStart位置到codeEnd位置的二進制串的一個子串
//				System.out.println("codeStart = " + codeStart + "; codeEnd = " + codeEnd);
				
				String byteKey = null;
				
				byteKey = contentHuffman.substring(codeStart, codeStart + codeEnd);
				b = reverseHuffmanCodeTable.get(byteKey); // 通過截取到的子串擷取其對應的Byte
				if (b != null) { // 如果不為空，即找到了該字串對應位元組
					isByte = true;
				} else {
					codeEnd++;
				}
			}
			// 程式執行到此，說明已經找到了一個位元組
			list.add(b); // 将該位元組加入到list
			codeStart += codeEnd; // 直接讓起始的掃描位置移動到結束的掃描位置
		}
		
		// 程式執行到此，list集合中就存放了解壓之後的所有位元組了，此時我們應該将它們取出來放到位元組數組中
		byte[] contentBytes = new byte[list.size()];
		for (int i = 0; i < contentBytes.length; i++) {
			contentBytes[i] = list.get(i);
		}
		return contentBytes;
	}
	
	/**
	 * 該方法用來将一個byte轉換成 位字元串(01串)，
	 * 需要注意：
	 * 	如果byte是負數，在轉換成int後，那麼轉換成的 位字元串就是其對應的補碼；
	 * 	如果byte是正數，在轉換成int後，那麼轉換成的 位字元串就是其對應的原碼，此時我們還有可能需要進行補位；
	 * @param isRepair 是否需要補高位
	 * @param b 進行轉換的byte值
	 * @return 轉換後的二進制字元串
	 */
	private static String byteToBitStr(boolean isRepair, byte b) {
		int tmp = b; // 将byte轉換成int
		String binaryStr; // 存放轉換之後的二進制字元串
		if (isRepair) { // 如果需要進行補位 或者 為正數 時就進行補位
			tmp |= 256; // 進行 按位或操作，如 2對應的二進制就是 00000010，按位或256(256的二進制為100000000)，即 00000010 | 10000000 = 100000010
			binaryStr = Integer.toBinaryString(tmp); // 轉換為二進制字元串
//			System.out.println("binaryStr = " + binaryStr.substring(binaryStr.length() - 8));
			return binaryStr.substring(binaryStr.length() - 8); // 從第8位截取全部二進制字元串并傳回
		}
		// 程式執行到此，說明不需要補位(即是最後一位位元組的哈夫曼編碼)
		binaryStr = Integer.toBinaryString(tmp); // 轉換二進制字元串
//		System.out.println("1------" + binaryStr);
		binaryStr = LAST_CODE; // 将壓縮過程中儲存的最後一位位元組對應的哈夫曼編碼直接 指派給該變量(不用進行判斷是否添0)
//		System.out.println("2------" + binaryStr);
		return binaryStr; // 将整個二進制字元串傳回
	}
	
	/**
	 * 通過傳入的位元組數組将其轉換成對應Node節點集合
	 * @param bs 位元組數組
	 * @return 将位元組數組每個元素轉換成Node的List集合
	 */
	private static List<Node> getNodeList(byte[] bs) {
		
		// 存儲壓縮資訊對應的byte數組中每個元素對應的節點
		List<Node> nodes = new ArrayList<Node>();;
		
		// 這個Map用來存儲統計每個byte位元組出現的次數
		Map<Byte, Integer> tmpMap = new HashMap<Byte, Integer>();
		for (byte b : bs) {
			if (tmpMap.get(b) == null) { // 如果該位元組沒有在tmpMap，即第一次出現該位元組
				tmpMap.put(b, 1); // 将這個Byte位元組加入到Map
			} else { // 否則，即該位元組在tmpMap中已經存在(即已經至少出現了一次)
				Integer count = tmpMap.get(b); // 擷取該位元組在Map中的Value(即出現的次數)
				tmpMap.put(b, count + 1); // 将該位元組的值+1
			}
		}
		
		// 将上面的Map中的資訊轉換成Node并加入到nodes中
		for (Map.Entry<Byte, Integer> node : tmpMap.entrySet()) {
			nodes.add(new Node(node.getKey(), node.getValue())); // 将該KEY, VALUE對轉換成Node并添加到nodes中
		}
		return nodes;
	}
	
	/**
	 * 建立哈夫曼樹的方法
	 * @return
	 */
	private static Node createHuffmanTree(List<Node> nodes) {
		// 當nodes中的元素大于1，即哈夫曼樹還沒有建構完畢
		while (nodes.size() > 1) {
			// TODO 将nodes内的元素排序(有Node類實作Compareable接口，可以看出是從小到大排序的)
			Collections.sort(nodes);
			// TODO 取出最小和次小的元素節點
			Node minNode = nodes.get(0);
			Node subMinNode = nodes.get(1);
			// TODO 通過最小和次小元素節點建立新的節點，并将新的節點加入到ArrayList集合，然後将這兩個元素删除
			Node newNode = new Node(null, minNode.getWeight() + subMinNode.getWeight());
			newNode.setLeft(minNode);
			newNode.setRight(subMinNode);
			nodes.remove(minNode);
			nodes.remove(subMinNode);
			nodes.add(newNode);
		}
		
		return nodes.get(0); // 将nodes中的0索引位置的元素(此時一定有且僅有這一個元素了)傳回
	}
	
	/**
	 * 生成哈夫曼編碼表
	 */
	private static void generateHuffmanCodeTable() {
		if (ROOT == null) {
			System.err.println("root節點為空，生成哈夫曼編碼表失敗！");
			return;
		}
		// 執行個體化存儲哈夫曼編碼的編碼表
		HUFFMAN_CODES_TABLE = new HashMap<Byte, String>();
		// 處理root的左子樹
		generateHuffmanCodeTable(ROOT.getLeft(), "0", new StringBuilder());
//		// 處理root的右子樹
		generateHuffmanCodeTable(ROOT.getRight(), "1", new StringBuilder());
		// {32=100, 97=101, 33=1100, 101=1101, 118=1110, 105=000, 73=1111, 74=001, 107=010, 108=011}
		// 或者直接寫成如下方式
//		generateHuffmanCodeTable(root, "", new StringBuilder());
		// {32=100, 97=101, 33=1100, 101=1101, 118=1110, 105=000, 73=1111, 74=001, 107=010, 108=011}
	}
	
	/**
	 * 生成哈夫曼表的方法，通過分析，傳入的字元串對應的所有節點一定是哈夫曼樹的葉子節點
	 * @param node 目前節點
	 * @param path 路徑(左0右1)
	 * @param codeItem 用來拼接目前節點的上一條路徑path，來生成相應葉子節點的哈夫曼編碼
	 */
	private static void generateHuffmanCodeTable(Node node, String path, StringBuilder codeItem) {
		StringBuilder code = new StringBuilder(codeItem); // 接收傳來的codeItem
		code.append(path); // 将path路徑拼接到code上
		if (node != null) {
			if (node.getData() == null) { // 如果node的data為空，即該節點為非葉子節點(因為在建立哈夫曼樹時，我們隻有通過Byte位元組生成的Node才有data，其他的節點data都為null)
				// 向左遞歸
				generateHuffmanCodeTable(node.getLeft(), "0", code);
				// 向右遞歸
				generateHuffmanCodeTable(node.getRight(), "1", code);
			} else { // 否則即node的data不為空，該節點為葉子節點
				HUFFMAN_CODES_TABLE.put(node.getData(), code.toString()); // 将該節點的data(即Byte)和其對應的編碼code存入哈夫曼編碼表
			}
		}
	}
	
	/**
	 * 前序周遊哈夫曼樹的方法
	 */
	public static void preOrder() {
		if (ROOT == null) {
			System.err.println("哈夫曼樹為空！");
		} else {
			ROOT.preOrder();
		}
	}

	public static Node getRoot() {
		return ROOT;
	}

	public static Map<Byte, String> getCodeTable() {
		return HUFFMAN_CODES_TABLE;
	}
	
}

           

測試類的編寫

package edu.hebeu.huffman.code;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.UnsupportedEncodingException;
import java.util.Arrays;

public class Test {
	public static void main(String[] args) {
		testZipFile(); // 壓縮使用
		// testUnzipFile(); // 解壓使用
	}
	
	/**
	 * 測試壓縮檔案
	 */
	public static void testZipFile() {
		HuffmanTreeCompress.zipFile("data/dataFile", "data/zipFile.hufm");
	}
	
	/**
	 * 測試解壓檔案
	 */
	public static void testUnzipFile() {
		HuffmanTreeCompress.UnzipFile("data/zipFile.hufm", "data/unzipFile");
	}
	
}

           

測試

壓縮：

解壓：