java赫夫曼編碼（含赫夫曼編碼代碼）

目錄

一：赫夫曼編碼的介紹

二：赫夫曼編碼原了解析

2.1 通信領域中資訊的處理方式1——定長編碼​

2.2 通信領域中資訊的處理方式2——變長編碼​

2.3 通信領域中資訊的處理方式3——赫夫曼編碼

三：赫夫曼編碼步驟

四：說明

五：赫夫曼編碼代碼展示

一：赫夫曼編碼的介紹

1 赫夫曼編碼也翻譯為哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式, 屬于一種程式算法。

2 赫夫曼編碼是赫哈夫曼樹在電訊通信中的經典的應用之一。

3 赫夫曼編碼廣泛地用于資料檔案壓縮。 其壓縮率通常在20%～90%之間。

4 赫夫曼碼是可變字長編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，稱之為最佳編碼。

二：赫夫曼編碼原了解析

2.1 通信領域中資訊的處理方式1——定長編碼

2.2 通信領域中資訊的處理方式2——變長編碼

2.3 通信領域中資訊的處理方式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 按照上面字元出現的次數建構一顆赫夫曼樹, 次數作為權值。

建構赫夫曼樹的步驟如下：

3.1 從小到大進行排序,每個資料都是一個節點，每個節點可以看成是一顆最簡單的二叉樹。

3.2 取出根節點權值最小的兩顆二叉樹。

3.3 組成一棵新的二叉樹, 該新的二叉樹的根節點的權值是前面兩顆二叉樹根節點權值的和。

3.4 再将這棵新的二叉樹，以根節點的權值大小再次排序，不斷重複1-2-3-4 的步驟，直到數列中，所有的資料都被處理,就得到一顆赫夫曼樹。

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 

注意：這裡使用的是無損壓縮。

6 通過赫夫曼編碼處理後，長度變為133。

四：說明

1 原來長度是359,壓縮了(359-133) / 359 = 62.9%。

2 此編碼滿足字首編碼, 即字元的編碼都不能是其他字元編碼的字首，不會造成比對的多義性。

3 赫夫曼編碼是無損處理方案。

注意

赫夫曼樹根據排序方法不同，也可能不太一樣，這樣對應的赫夫曼編碼也不完全一樣，但是 wpl 是一樣的，都是最小的,最後生成的赫夫曼編碼的長度是一樣。

比如:如果讓每次生成的新的二叉樹總是排在權值相同的二叉樹的最後一個，則生成的二叉樹為下圖。

五：赫夫曼編碼代碼展示

赫夫曼樹結點的定義

package tree;

public class HFMCode implements Comparable<HFMCode>{
	private Byte b;
	private int weight;
	
	private HFMCode left;
	private HFMCode right;
	
	public HFMCode(Byte b, int weight) {
		this.b = b;
		this.weight = weight;
	}

	public Byte getB() {
		return b;
	}

	public void setB(Byte b) {
		this.b = b;
	}

	public int getWeight() {
		return weight;
	}

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

	public HFMCode getLeft() {
		return left;
	}

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

	public HFMCode getRight() {
		return right;
	}

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

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

	@Override
	public int compareTo(HFMCode o) {
		// TODO Auto-generated method stub
		return this.weight - o.weight;
	}
	
	public void preSelect() {
		System.out.println(this);
		if(this.getLeft() != null) {
			this.getLeft().preSelect();
		}
		if(this.getRight() != null) {
			this.getRight().preSelect();
		}
	}
	
	

}
           

赫夫曼編碼

package tree;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

public class HFMCTree {
	private static Map<Byte,String> map = new HashMap<>();;
	public static void main(String[] args) {
		String str = "Im RenBiaoYu what your name";
		byte[] bytes = str.getBytes();
		HFMCode root = creatTree(counts(bytes));
		Map<Byte,String> m = creatCode(root,"",new StringBuilder());
		System.out.print(Arrays.toString(zip(m, bytes)));
		
	}
	//統計個數
	public static ArrayList<HFMCode> counts(byte[] arr){
		Map<Byte,Integer> map = new HashMap<>();
		for(byte b:arr) {
			Integer i = map.get(b);
			if(i == null) {
				map.put(b, 1);
			}else {
				map.put(b, i + 1);
			}
		}
		//壓縮到List集合中友善後序赫夫曼樹的建立
		ArrayList<HFMCode> al = new ArrayList<HFMCode>();
		for(Map.Entry<Byte, Integer> entry:map.entrySet()) {
			al.add(new HFMCode(entry.getKey(),entry.getValue()));
		}
		
		return al;
	}
	//建立赫夫曼樹
	public static HFMCode creatTree(ArrayList<HFMCode> hfmc) {
		while(hfmc.size() > 1) {
			Collections.sort(hfmc);
			HFMCode left = hfmc.get(0);
			HFMCode right = hfmc.get(1);
			
			HFMCode newCode = new HFMCode(null,left.getWeight() + right.getWeight());
			newCode.setLeft(left);
			newCode.setRight(right);
			
			hfmc.remove(left);
			hfmc.remove(right);
			hfmc.add(newCode);
		}
		return hfmc.get(0);
	}
	//赫夫曼編碼
	public static Map<Byte,String> creatCode(HFMCode node, String code, StringBuilder sb){
		StringBuilder stringCode = new StringBuilder(sb);
		stringCode.append(code);
		if(node != null) {
			if(node.getB() == null) {
				creatCode(node.getLeft(),"0",stringCode);
				creatCode(node.getRight(),"1",stringCode);
			}else{
				map.put(node.getB(), stringCode.toString());
				}
		}
		return map;
	}
	//壓縮資料
	public static byte[] zip(Map<Byte,String> m,byte[] bytes) {
		StringBuilder sb = new StringBuilder();
		for(byte b:bytes) {
			sb.append(m.get(b));
		}
		int length = 0;
		if(sb.length() % 8 == 0) {
			length = sb.length() / 8;
		}else {
			length = sb.length() / 8 + 1;
		}
		//壓縮資料的數組
		int index = 0;
		byte[] newbytes = new byte[length];
		for(int i = 0; i < sb.length(); i+=8) {
			String str = "";
			if(i + 8 > sb.length()) {
				str = sb.substring(i);
			}else {
				str = sb.substring(i, i + 8);
			}
			newbytes[index++] = (byte) Integer.parseInt(str, 2);
		}
		return newbytes;
	}

}