哈夫曼樹以及哈夫曼編碼

哈夫曼樹

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

哈夫曼樹代碼實作

示例圖：以字元串AAABBCDDDDD為例建構哈夫曼樹

 哈夫曼節點類

public class HaffmanNode {
	int val; //值
	int weight;//權值
	char ch;//所放字元串
	HaffmanNode left;//左孩子
	HaffmanNode right;//右孩子

	public HaffmanNode(int val, char ch) {
		this.val = val;
		this.ch = ch;
	}
	@Override
	public String toString() {
		return "HaffmanNode [val=" + val + ", weight=" + weight + ", ch=" + ch + "]";
	}
}
           

哈夫曼樹實作類

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;

public class Haffman {
	HaffmanNode root;
	int count[] = new int[35];//統計字元出現的次數，這裡隻收集 A~Z的
	public void build(char[] arr) {
		//先統計字元數組中的字元出現的次數
		for (int i = 0; i < arr.length; i++) {
			count[arr[i] - 'A']++;
		}
		//建立優先隊列，預設是優先級大的，先出隊列，數值越小，優先級别越大
		//按照哈夫曼編碼最小的兩個節點先出，是以修改比較設定
		PriorityQueue<HaffmanNode> priorityQueue = new PriorityQueue<>(new Comparator<HaffmanNode>() {
			public int compare(HaffmanNode o1, HaffmanNode o2) {
				return o1.val - o2.val;
			}
		});
		//建立字元節點，并且将節點按照出現次數作為優先級放入優先隊列中
		for (int i = 0; i < count.length; i++) {
			if (count[i] != 0) {
				priorityQueue.offer(new HaffmanNode(count[i], (char) (65 + i)));
			}
		}
		//當優先隊列中的節點數大于1時，
		while (priorityQueue.size() != 1) {
			//取出兩個最小的以及第二小的節點
			HaffmanNode left = priorityQueue.poll();
			HaffmanNode right = priorityQueue.poll();
			//建立一個新的節點，放入優先隊列中，值為左孩子加右孩子的值
			HaffmanNode newHaffmanNode = new HaffmanNode(left.val + right.val, ' ');
			newHaffmanNode.left = left;
			newHaffmanNode.right = right;
			priorityQueue.add(newHaffmanNode);
		}
		//當優先隊列中隻剩一個時，此時的節點就是已經建構好的哈夫曼樹
		root = priorityQueue.poll();
	}

}
           

更新權值

//map存儲字元出現的權值
	private Map<Character, Integer> map1 = null;
	
	private void getWeight() {
		//更新權值
		map1 = new HashMap<>();
		count(root, 0);
	}
	//擷取權值
	public Integer getWeight(char ch) {
		if (map1 == null) {
			getWeight();
		}
		return map1.get(ch);
	}
	
	public void count(HaffmanNode haffmanNode, int weight) {
		//遞歸更新權值
		if (haffmanNode != null && haffmanNode.ch != ' ') {
			map1.put(haffmanNode.ch, weight);
		}
		if (haffmanNode.left != null) {
			count(haffmanNode.left, weight + 1);
		}
		if (haffmanNode.right != null) {
			count(haffmanNode.right, weight + 1);
		}
	}
           

擷取哈夫曼編碼

//存儲一個字元的哈夫曼編碼後的編碼集
	private Map<Character, String> map = new HashMap<>();

	public void bianma() {
		bianma(root, "");
	}

	private void bianma(HaffmanNode node, String str) {
		if (node.ch >= 'A' && node.ch <= 'Z') {
			//記錄字元的哈夫曼編碼
			map.put(node.ch, str);
		}
		if (node.left != null) {
			//往左側走，編碼為0
			bianma(node.left, str + "0");
		}
		if (node.right != null) {
			//往右側走，編碼為1
			bianma(node.right, str + "1");
		}
	}
           

應用

1.哈夫曼樹又稱為最優樹，樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL。

2.資料壓縮