1.介紹
①給定n個權值作為n個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度（wpl）到達最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹，還有的書翻譯為霍夫曼樹。
②赫夫曼樹 是帶權路徑最短的樹，權值較大的結點離根結點較近。
③路徑和路徑長度：在一棵樹中，從一個結點往下可以達到的孩子或孫子結點之間的通路，稱之為路徑。通路中的分支的數目稱為路徑長度，若規定根結點的層數為1，則從根節點到第L層結點到路徑長度為L-1。
④結點的權及帶權路徑長度：若将結點賦給一個有某中含義的數值，這個數值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與結點的權的乘積。
⑤樹的帶權路徑長度：樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL，權值越大的結點離根結點越近的二叉樹才是最優二叉樹。
2.建構步驟
①從小到大進行排序，将每個資料，每一個資料都是一個結點，每個結點可以看成是一棵最簡單的二叉樹。
②取出根節點權值最小的兩顆二叉樹。
③組成一棵新的二叉樹，該二叉樹的根節點的權值是前面兩顆二叉樹根節點權值的和。
④再将這顆新的二叉樹，以根結點的權值大小再排序，不斷重複1-2-3-4的步驟，直到數列中，所有的資料被處理，就得到一棵赫夫曼樹。
3.代碼實作：
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class HuffmanTree {
public static void main(String[] args) {
int arr[] = { 13, 7, 8, 3, 29, 6, 1 };
Node root = createHuffmanTree(arr);
//測試一把
preOrder(root); //
}
//編寫一個前序周遊的方法
public static void preOrder(Node root) {
if(root != null) {
root.preOrder();
}else{
System.out.println("是空樹，不能周遊~~");
}
}
// 建立赫夫曼樹的方法
/**
*
* @param arr 需要建立成哈夫曼樹的數組
* @return 建立好後的赫夫曼樹的root結點
*/
public static Node createHuffmanTree(int[]arr){
// 第一步為了操作友善
// 1. 周遊 arr 數組
// 2. 将arr的每個元素構成成一個Node
// 3. 将Node 放入到ArrayList中
List<Node> lists=new ArrayList<Node>();
for (int item:arr){
lists.add(new Node(item));
}
while (lists.size()>1){
// 将資料進行排序
Collections.sort(lists);
// 取出根節點權值最小的兩顆二叉樹
// (1) 取出權值最小的結點（二叉樹）
Node node1=lists.get(0);
// (2) 取出權值第二小的結點（二叉樹）
Node node2=lists.get(1);
//(3)建構一顆新的二叉樹
Node parent=new Node(node1.value+node2.value);
parent.left=node1;
parent.right=node2;
lists.remove(node1);
lists.remove(node2);
lists.add(parent);
}
return lists.get(0);
}
}
// 建立結點類
// 為了讓Node 對象持續排序Collections集合排序
// 讓Node 實作Comparable接口
class Node implements Comparable<Node>{
int value;// 結點權值
char c; // 字元
Node left; // 指向左節點
Node right; // 指向右結點
// 編寫一個前序周遊
public void preOrder(){
// 輸出目前結點
System.out.println(this);
if (this.left!=null){
this.left.preOrder();
}
if(this.right!=null){
this.right.preOrder();
}
}
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
@Override
public int compareTo(Node o) {
return this.value-o.value;
}
}
4.赫夫曼編碼
4.1基本介紹
①赫夫曼編碼翻譯為哈夫曼編碼，霍夫曼編碼，是一種編碼方式，屬于程式算法。
②赫夫曼編碼是赫夫曼樹在電訊通信中的經典的應用之一。
③赫夫曼編碼廣泛地用于資料檔案的壓縮。其壓縮率通常在20%~90%之間。
④赫夫曼碼是可變字長編碼（VLC）的一種。Huffman于1952年提出一種編碼方法，稱之為最佳編碼。
4.1壓縮案例
傳輸的 字元串
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) 按照上面字元出現的次數建構一顆赫夫曼樹, 次數作為權值
步驟：
構成赫夫曼樹的步驟：
1) 從小到大進行排序, 将每一個資料，每個資料都是一個節點 ， 每個節點可以看成是一顆最簡單的二叉樹
2) 取出根節點權值最小的兩顆二叉樹
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 通過赫夫曼編碼處理 長度為 133。
代碼實作：
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(contentBytes.length); //40
byte[] huffmanCodesBytes= huffmanZip(contentBytes);
System.out.println("壓縮後的結果是:" + Arrays.toString(huffmanCodesBytes) + " 長度= " + huffmanCodesBytes.length);
}
//使用一個方法，将前面的方法封裝起來，便于我們的調用.
/**
*
* @param bytes 原始的字元串對應的位元組數組
* @return 是經過 赫夫曼編碼處理後的位元組數組(壓縮後的數組)
*/
public static byte[] huffmanZip(byte[] bytes){
List<Node>list=getCode(bytes);
//根據 nodes 建立的赫夫曼樹
Node huffmanTree = createHuffmanTree(list);
//對應的赫夫曼編碼(根據 赫夫曼樹)
Map<Byte, String> codes = getCodes(huffmanTree);
//根據生成的赫夫曼編碼，壓縮得到壓縮後的赫夫曼編碼位元組數組
byte[] zip = zip(bytes, codes);
return zip;
}
//編寫一個方法，将字元串對應的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
*/
public static byte[] zip(byte[]bytes,Map<Byte,String> huffmanCodes){
//1.利用 huffmanCodes 将 bytes 轉成 赫夫曼編碼對應的字元串
StringBuilder stringBuilder = new StringBuilder();
for (byte b:bytes){
stringBuilder.append(huffmanCodes.get(b));
}
System.out.println(stringBuilder);
int len=0;
if(stringBuilder.length()%8==0){
len=stringBuilder.length()/8;
}else {
len=stringBuilder.length()/8+1;
}
byte[] huffmanCodeBytes = new byte[len];
int index=0;//記錄是第幾個byte
for(int i=0;i<stringBuilder.length();i+=8){//因為是每8位對應一個byte,是以步長 +8
String strByte;
if(i+8>stringBuilder.length()){
strByte=stringBuilder.substring(i);
}else {
strByte=stringBuilder.substring(i,i+8);
}
//将strByte 轉成一個byte,放入到 huffmanCodeBytes
huffmanCodeBytes[index]=(byte)Integer.parseInt(strByte,2);
index++;
}
return huffmanCodeBytes;
}
//生成赫夫曼樹對應的赫夫曼編碼
//思路:
//1. 将赫夫曼編碼表存放在 Map<Byte,String> 形式
// 生成的赫夫曼編碼表{32=01, 97=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();
//為了調用友善，我們重載 getCodes
public static Map<Byte, String> getCodes(Node node){
if(node==null){
return null;
}
// 處理root的左子樹
getCodes(node.left,"0",stringBuilder);
//處理root的右子樹
getCodes(node.right,"1",stringBuilder);
return huffmanCodes;
}
/**
* 功能：将傳入的node結點的所有葉子結點的赫夫曼編碼得到，并放入到huffmanCodes集合
* @param node 傳入結點
* @param code 路徑： 左子結點是 0, 右子結點 1
* @param stringBuilder 用于拼接路徑
*/
public static void getCodes(Node node,String code,StringBuilder stringBuilder){
StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
stringBuilder1.append(code);
if(node!=null){
if(node.data==null){
//遞歸處理
//向左遞歸
getCodes(node.left,"0",stringBuilder1);
// 向右遞歸
getCodes(node.right,"1",stringBuilder1);
}else {
huffmanCodes.put(node.data,stringBuilder1.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]......],
*/
public static List<Node>getCode(byte[] bytes){
//1建立一個ArrayList
List<Node>lists=new ArrayList<>();
//周遊 bytes , 統計 每一個byte出現的次數->map[key,value]
Map<Byte,Integer> map=new HashMap<>();
for(byte b:bytes){
Integer count=map.get(b);
if(count==null){// Map還沒有這個字元資料,第一次
map.put(b,1);
}else {
map.put(b,count+1);
}
}
//把每一個鍵值對轉成一個Node 對象，并加入到nodes集合
//周遊map
for(Map.Entry<Byte,Integer> entry:map.entrySet()){
lists.add(new Node(entry.getKey(),entry.getValue()));
}
return lists;
}
//可以通過List 建立對應的赫夫曼樹
public static Node createHuffmanTree(List<Node> lists){
while (lists.size()>1){
// 将資料進行排序
Collections.sort(lists);
// 取出根節點權值最小的兩顆二叉樹
// (1) 取出權值最小的結點（二叉樹）
Node node1=lists.get(0);
// (2) 取出權值第二小的結點（二叉樹）
Node node2=lists.get(1);
//(3)建構一顆新的二叉樹
Node parent=new Node(null,node1.weight+node2.weight);
parent.left=node1;
parent.right=node2;
lists.remove(node1);
lists.remove(node2);
lists.add(parent);
}
return lists.get(0);
}
}
class Node implements Comparable<Node>{
Byte data; // 存放資料(字元)本身，比如'a' => 97 ' ' => 32
int weight;
Node left;
Node right;
public Node(Byte data, int weight) {
this.data = data;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
// 從小到大排序
return this.weight-o.weight;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", weight=" + weight +
'}';
}
// 前序周遊
public void preOrder(){
System.out.println(this);
if(this.left!=null){
this.left.preOrder();
}
if(this.right!=null){
this.right.preOrder();
}
}
}
總結：上面實作的使用對字元串進行壓縮，壓縮成一個位元組數組下面是結果顯示。原來長度為40，壓縮後長度為17.
