Huffman樹的建立
基本介紹
- 給定n個權值作為n 個葉子結點毕荐，構造一棵二叉樹舀患，若該樹的帶權路徑長度(wpl)達到最小，稱這樣的二叉樹為最優(yōu)二叉樹,也稱為哈夫曼樹(Huffman Tree)
- 赫夫曼樹是帶權路徑長度最短的樹程腹，權值較大的結點離根較近
赫夫曼樹幾個重要概念
- 路徑和路徑長度:在一棵樹中锰瘸，從一個結點往下可以達到的孩子或孫子結點之間的通路，稱為路徑蹬碧。通路中分支的數(shù)目稱為路徑長度舱禽。若規(guī)定根結點的層數(shù)為1，則從根結點到第L層結點的路徑長度為L-1
- 結點的權及帶權路徑長度:若將樹中結點賦給一個有著某種含義的數(shù)值.則這個數(shù)值稱為該結點的權恩沽。結點的帶權路徑長度為:從根結點到該結點之間的路徑長度與該結點的權的乘積
- 樹的帶權路徑長度:樹的帶權路徑長度規(guī)定為所有葉子結點的帶權路徑長度之和誊稚，記為WPL(weighted path length) ,權值越大的結點離根結點越近的二叉樹才是最優(yōu)二叉樹
- WPL最小的就是赫夫曼樹
赫夫曼樹創(chuàng)建思路
給你一個數(shù)列{13,7,8,3,29,6,1}，要求轉成一顆赫夫曼樹.構成赫夫曼樹的步驟:
- 從小到大進行排序,將每一個數(shù)據(jù)罗心，每個數(shù)據(jù)都是一個節(jié)點片吊，每個節(jié)點可以看成是一顆最簡單的二叉樹
- 取出根節(jié)點權值最小的兩顆二叉樹
- 組成一顆新的二叉樹,該新的二叉樹的根節(jié)點的權值是前面兩顆二叉樹根節(jié)點權值的和
- 再將這顆新的二叉樹，以根節(jié)點的權值大小再次排序．不斷重復1-2-3-4 的步驟协屡，直到數(shù)列中俏脊，所有的數(shù)據(jù)都被處理,就得到一顆赫夫曼樹
public class HuffmanTree {
public static void main(String[] args) {
int[] arr={13,7,8,3,29,6,1};
Node huffmanTree=createHuffmanTree(arr);
preOrder(huffmanTree);
}
//前序遍歷
public static void preOrder(Node root){
if(root!=null)
root.preOrder();
else
System.out.println("空樹，不能遍歷");
}
public static Node createHuffmanTree(int[] arr){
List<Node> nodes=new ArrayList<>();
for(int value:arr)
nodes.add(new Node(value));
while(nodes.size()>1)
{
Collections.sort(nodes);
Node leftNode=nodes.get(0);
Node rightNode=nodes.get(1);
Node parentNode=new Node(leftNode.value+rightNode.value);
parentNode.left=leftNode;
parentNode.right=rightNode;
nodes.remove(leftNode);
nodes.remove(rightNode);
nodes.add(parentNode);
}
return nodes.get(0);
}
}
class Node implements Comparable<Node>{
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
//前序遍歷
public void preOrder(){
System.out.println(this);
if(this.left!=null)
this.left.preOrder();
if(this.right!=null)
this.right.preOrder();
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
@Override
public int compareTo(Node node) {
return this.value-node.value;
}
}
赫夫曼編解碼
public class HuffmanCode {
static Map<Byte,String> huffmanCodes=new HashMap<>();
static StringBuilder stringBuilder=new StringBuilder();
public static void main(String[] args) {
String content="asdds astkk nhb sgacsw aevsbd";
byte[] contentBytes=content.getBytes();
byte[] huffmanCodeBytes=huffmanZip(contentBytes);
System.out.println(Arrays.toString(huffmanCodeBytes));
byte[] sourceBytes=decode(huffmanCodes,huffmanCodeBytes);
System.out.println(new String(sourceBytes));
}
/**
* 將一個byte轉化為一個二進制的字符串
* @param flag 表示是否需要補高位肤晓，如果是true表示需要補高位爷贫，如果是false表示不補认然，如果是最后一個字節(jié)無需補高位
* @param b
* @return
*/
public static String byteToBitString(boolean flag,byte b){
int temp=b;
if(flag)
temp|=256;
String str=Integer.toBinaryString(temp);
if(flag)
return str.substring(str.length()-8);
else
return str;
}
/**
* 解碼
* @param huffmanCodes
* @param huffmanBytes
* @return
*/
public static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){
StringBuilder stringBuilder=new StringBuilder();
for(int i=0;i<huffmanBytes.length;i++){
byte b=huffmanBytes[i];
boolean flag=(i==huffmanBytes.length-1);
stringBuilder.append(byteToBitString(!flag,b));
}
Map<String,Byte> map=new HashMap<>();
for(Map.Entry<Byte,String>entry:huffmanCodes.entrySet()){
map.put(entry.getValue(),entry.getKey());
}
List<Byte> list=new ArrayList<>();
for(int i=0;i<stringBuilder.length();){
int count=1;
boolean flag=true;
Byte b=null;
while(flag){
String key=stringBuilder.substring(i,i+count);
b=map.get(key);
if(b==null)
count++;
else
flag=false;
}
list.add(b);
i+=count;
}
byte[] b=new byte[list.size()];
for(int i=0;i<b.length;i++)
b[i]=list.get(i);
return b;
}
//封裝流程
private static byte[] huffmanZip(byte[] bytes){
List<Node> nodes=getNodes(bytes);
Node huffmanTreeRoot=createHuffmanTree(nodes);
Map<Byte,String> huffmanCodes=getCodes(huffmanTreeRoot);
byte[] huffmanCodeBytes=zip(bytes,huffmanCodes);
return huffmanCodeBytes;
}
/**
* 一、將傳入的字節(jié)數(shù)組轉為List<Node>集合
* @param bytes 傳入的字節(jié)數(shù)組
* @return List<Node>集合
*/
private static List<Node> getNodes(byte[] bytes){
ArrayList<Node> nodes=new ArrayList<>();
Map<Byte,Integer> counts=new HashMap<>();
for(byte b:bytes) {
Integer count=counts.get(b);
if(count==null)
counts.put(b,1);
else
counts.put(b,count+1);
}
for(Byte b:counts.keySet()){
Node node=new Node(b,counts.get(b));
nodes.add(node);
}
return nodes;
}
/**
* 二漫萄、構建Huffman樹
* @param nodes Node集合
* @return 根節(jié)點
*/
public static Node createHuffmanTree(List<Node> nodes){
while(nodes.size()>1)
{
Collections.sort(nodes);
Node leftNode=nodes.get(0);
Node rightNode=nodes.get(1);
Node parentNode=new Node(null,leftNode.weight+rightNode.weight);
parentNode.left=leftNode;
parentNode.right=rightNode;
nodes.remove(leftNode);
nodes.remove(rightNode);
nodes.add(parentNode);
}
return nodes.get(0);
}
//重載
public static Map<Byte,String> getCodes(Node root){
if(root==null)
return null;
else{
getCodes(root.left,"0",stringBuilder);
getCodes(root.right,"1",stringBuilder);
}
return huffmanCodes;
}
/**
* 三卷员、獲取Huffman編碼表
* @param node 節(jié)點
* @param code 路徑：左子節(jié)點為0，右子節(jié)點為1
* @param stringBuilder 拼接路徑（編碼）
*/
public static void getCodes(Node node,String code,StringBuilder stringBuilder){
StringBuilder stringBuilder2=new StringBuilder(stringBuilder);
stringBuilder2.append(code);
if(node!=null){
if(node.data==null){
getCodes(node.left,"0",stringBuilder2);
getCodes(node.right,"1",stringBuilder2);
}
else
huffmanCodes.put(node.data,stringBuilder2.toString());
}
}
/**
* 四腾务、將原始數(shù)組轉化為壓縮后的字節(jié)數(shù)組
* @param bytes 原始字節(jié)數(shù)組
* @param huffmanCodes 編碼表
* @return 壓縮后的字節(jié)數(shù)組
*/
private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCodes){
StringBuilder stringBuilder=new StringBuilder();
for(byte b:bytes){
stringBuilder.append(huffmanCodes.get(b));
}
int len=(stringBuilder.length()+7)/8;
byte[] huffmanCodeBytes=new byte[len];
int index=0;
for(int i=0;i<stringBuilder.length();i+=8){
String strByte;
if(i+8>stringBuilder.length())
strByte=stringBuilder.substring(i);
else
strByte=stringBuilder.substring(i,i+8);
huffmanCodeBytes[index]=(byte)Integer.parseInt(strByte,2);
index++;
}
return huffmanCodeBytes;
}
}
